摘自：http://netair.heha.net/VC/article/alldoc/D_178.htm
作者：黄振余
数据的排序是学习C语言经常碰到的问题?所谓排序是指把一组杂乱无章的数按照大小顺序排列。包括整数、实数、字符及字符串排序。C语言编程中排序的方法很多，?这里归纳较常用的几种排序方法。它们同样适合于其他高级语言。
Shell排序
Shell排序是以发明者命名的一种较快的排序方法。Shell排序基本算法思想是：将整个无序序列分割成若干小的子序分别进行插入排序。
子序列的分割方法为：将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，?最后当h减到1时，进行一次插入排序，排序就完成。
在本函数中，增量序列取 ht=2t－1，1 tlog2n其中n为待排序序列的长度。
例：（/＊ 将输入的数据排序后,输出一个测试Shell排序的主函数＊/）
＃define SIZE 10
main() {
void shell();
int d[SIZE],i;
printf(“Input ％d numbers\n",SIZE);
for(i=0;i
scanf(“％d",＆d[i]);
shell(d,SIZE);
printf(“After sort:\n")
for(i=0;i
printf(“％5d",d[i]);
printf(“\n");}
/＊把数组V的元素按增序排序＊/
void shell(v,n)
int v[],n;
{int gap,i,j,temp;
for(gap=n/2;gap>0;gap/=2)
for(i=gap;i
for(j=i－gap;j>=0 ＆＆ v[j])
v[j＋gap];j－=gap)
{ temp=v[j];
v[j]=v[j＋gap];
v[j＋gap]=temp; }
注：这里，数组作为函数参数，参数组中元素值的改变就会反过来影响到实参数组。
选择排序
选择排序基本算法思想：首先找出最小的元素，然后把这个元素与第一个元素互换，这样值最小的元素就放到了第一个位置；接着，再从剩下的元素中找值最小的，把它和第二个元素互换，使得第二小的元素放在第二个位置上，依此类推，直到所有的值由小到大排列为止。
例： ＃ define NUM 10
main()
{int a[NUM],i,j,r,temp;
printf(“Please input ％d number\n",NUM)
for (i=0;i
scanf("％d",＆a[i]);
for(i=0;i
r=i;
for(i=i＋1;j
if(a[i]
r=j;
if(r!=i)
temp=a[i];a[i]=a[r];a[r]=temp;} }
printf("The array after sort:\n")
for(i=0;i
printf("％5d",a[i]);
printf("\n"); }
快速排序
快速排序是目前使用较好的排序算法，它是由C.A.Hoare发明并命名的。快速排序基本算法思想：通过一次分割，将无序序列分成两部分，其中前一部分的元素值均不大于后一部分的元素值。然后对每一部分利用同样的方法进行分割，这个过程一直做到每一个子序列的长度小于某个值m为止。
对序列p的分割过程： 首先，在序列的第一个、中间一个及最后一个元素中选取中项，得p（k），并将p（k）赋给t；再将序列中的第一个元素移到p（k）的位置上；然后设置两个指针i和j分别指向序列的起始和最后的位置。
例： void quick(v,n)
int v[],n;
{ void qs();
qs(v,0,n－1);
/＊快速排序，数组方案＊/
void qs(v,left,right)
int v[],left,ringt;
{ int i,j,x,temp;
i=left;
v=v[(left＋right)/2];
while (i
while([i]
j－－;
if(i<=j){
temp=v[i];
v[i]=v[j];
v[j]=temp;
i＋＋;
j－－; } }
if (left
qs(v,left,j);
if(i
qs(v,i,right); }
注：在这个递归函数例子中，数组V既做为形参数，又做为实际参数。
冒泡排序
冒泡排序基本算法思想：从前到后扫描序列，比较相邻两个项目的大小，若发现逆序进行交换，最后使最大者换到序列的最后；然后再从后到前扫描剩下的序列，比较相邻两个项目的大小，若发现逆序则进行交换，最后使最小者换到序列的最前面。对剩下的序列重复上述过程，直到剩下的序列为空止。
例：void ma(p,n)
int P[],n;
{ int m,k,j,i,d;
k=0;m=n－1;
while (k
{ j=m－1;m=0;
for(ik;i<=;i＋＋)
if(p[i]>p[i＋1])
{ d=p[i];p[i]=p[i＋1];
p[i＋1]=d;m=i;}
j=k＋1;k=0;
for(i=m;i>=j;i－－)
if (p[i－1]>p[i])
{d=p[i－1];p[i]=p[i－1];
p[i－1]=d;k=i;} }
return; }
在实际运用上，还常用到堆排序，这里限于篇幅，不再赘述。
