排序问题很经典，这里总结了5种可以参考。
#include <stdio.h> #include<time.h> #include<stdlib.h> #define Leftchild(i)(2*(i)+1)//堆排序中对左孩子计算 #define Cutoff 3 #define maxn 1000 #define N 10//更改数组长度 #define Q 1//更改数字下限 #define P 100//更改数字上限 int a[maxn]; //int ShellList[]={1,5,41,109};//Sedgwick增量O(N的七分之六次方(亚二次时间)) void InPut(int a[],int n) { time_t t; int i; srand((unsigned)time(&t)); for(i=0;i<n;i++) a[i]=rand()%P+Q; } void OutPut(int a[],int n) { int i; for(i=0;i<n;i++) printf(" %d ",a[i]); printf("\n"); } void Swap(int *a,int *b) { int temp; temp=*a; *a=*b; *b=temp; } //插入排序 void InsertSort(int a[],int n) { int i,j; for(i=1;i<n;i++) { int temp=a[i]; for(j=i;j&&a[j-1]>temp;j--) a[j]=a[j-1]; a[j]=temp; } } //希尔排序 void ShellSort(int a[],int n) { int i,j,increment; int temp; // for(increment=ShellList[i=0];i<4;i++)//Sedgwick增量 for(increment=n/2;increment>0;increment/=2)//Hibbard增量O(N的五分之四次方) for(i=increment;i<n;i++) { temp=a[i]; for(j=i;(j-increment)&&a[j-increment]>temp;j-=increment) a[j]=a[j-increment]; a[j]=temp; } } //堆排序 void PerDown(int a[],int i,int n)//二叉堆插入函数 { int child; int temp; for(temp=a[i];Leftchild(i)<n;i=child) { child=Leftchild(i); if(child!=n-1&&a[child+1]>a[child]) child++; if(temp<a[child]) a[i]=a[child]; else break; } a[i]=temp; } void HeapSort(int a[],int n) { int i; for(i=n/2;i>=0;i--)//建造堆 PerDown(a,i,n); for(i=n-1;i>0;i--) { int tmp=a[0];//最大元素和头元素交换(哑信息) a[0]=a[i]; a[i]=tmp; PerDown(a,0,i); } } //归并排序 void Merge(int a[],int TemArray[],int lpos,int rpos,int rightEnd)//lpos=左半部分的开始，rpos=右半部分的开始。 { int i,leftEnd,Numelements,TmpPos; leftEnd=rpos-1; TmpPos=lpos; Numelements=rightEnd-lpos+1; while(lpos<=leftEnd&&rpos<=rightEnd) if(a[lpos]<=a[rpos]) TemArray[TmpPos++]=a[lpos++]; else TemArray[TmpPos++]=a[rpos++]; while(lpos<=leftEnd) TemArray[TmpPos++]=a[lpos++]; while(rpos<=rightEnd) TemArray[TmpPos++]=a[rpos++]; for(i=0;i<Numelements;i++,rightEnd--) a[rightEnd]=TemArray[rightEnd]; } void MSort(int a[],int TempArray[],int left,int right) { int mid; if(left<right) { mid=(left+right)/2; MSort(a,TempArray,left,mid); MSort(a,TempArray,mid+1,right); Merge(a,TempArray,left,mid+1,right); } } void MergeSort(int a[],int n) { int *TemArray; TemArray=malloc(n*sizeof(int)); if(TemArray!=NULL) { MSort(a,TemArray,0,n-1); free(TemArray); } else printf("no"); } //快速排序 int Median3(int a[],int left,int right) { int mid=(left+right)/2; if(a[left]>a[mid]) Swap(&a[left],&a[mid]); if(a[left]>a[right]) Swap(&a[left],&a[right]); if(a[mid]>a[right]) Swap(&a[mid],&a[right]); Swap(&a[mid],&right-1); return a[right-1]; } void Qsort(int a[],int left,int right) { int i,j; int pivot; if(left+Cutoff<=right) { pivot=Median3(a,left,right); i=left;j=right-1; for(;;) { while(a[++i]<pivot){} while(a[--j]>pivot){} if(i<j) Swap(&a[i],&a[j]); else break; } Swap(&a[i],&a[right-1]); Qsort(a,left,i-1); Qsort(a,i+1,right); } else InsertSort(a+left,right-left+1); } void QuickSort(int a[],int n) { Qsort(a,0,n-1); } //主函数 int main() { int n=N; // printf("Count number:"); // scanf("%d",&n); InPut(a,n); printf("Before_Sort:\n"); OutPut(a,n); InsertSort(a,n); printf("1.After_InsertSort:\n"); OutPut(a,n); ShellSort(a,n); printf("2.After_ShellSort:\n"); OutPut(a,n); HeapSort(a,n); printf("3.After_HeapSort:\n"); OutPut(a,n); MergeSort(a,n); printf("4.After_MergeSort:\n"); OutPut(a,n); QuickSort(a,n); printf("5.After_QuickSort:\n"); OutPut(a,n); return 0; }