/* 快速排序的思想: 通过一趟排序将记录分割成独立的两部分, 其中的一部分记录的关键字比另一部分记录 的关键字小,然后分别对这两部分进行排序 */ #include<cstdio> #define MAX 1000 typedef struct seqlist { int Array[MAX]; int length; }SeqList; void Swap(SeqList *L,int i,int j) { int temp=L->Array[i]; L->Array[i]=L->Array[j]; L->Array[j]=temp; } int Partition(SeqList *L,int low,int high) { int pivotkey; int m; m=low+(high-low)/2;//三段取中法,取一个合适的关键字 if(L->Array[low]>L->Array[high]) Swap(L,low,high); if(L->Array[m]>L->Array[high]) Swap(L,m,high); if(L->Array[low]>L->Array[m]) Swap(L,low,m); pivotkey=L->Array[low]; while(low<high) { while(low<high&&L->Array[high]>=pivotkey) high--; Swap(L,low,high); while(low<high&&L->Array[low]<=pivotkey) low++; Swap(L,low,high); } return low; } void Qsort(SeqList *L,int low,int high) { int pivot; if(low<high) { pivot=Partition(L,low,high);//算出枢轴值 Qsort(L,low,pivot-1);//对低数组排序 Qsort(L,pivot+1,high);//对高数组排序 } } void QuickSort(SeqList *L) { Qsort(L,1,L->length); } int main(int argc,char *argv[]) { int i; SeqList L; scanf("%d",&L.length); for(i=1;i<=L.length;i++) scanf("%d",&L.Array[i]); QuickSort(&L); printf("After Sort:\n"); for(i=1;i<=L.length;i++) printf("%4d",L.Array[i]); printf("\n"); return 0; }
原文:http://blog.csdn.net/u012736084/article/details/18899903