首页 > 代码库 > 让算法会说话之快速排序
让算法会说话之快速排序
转载请注明出处:http://blog.csdn.net/ruoyunliufeng/article/details/30729523
快速排序是由东尼.霍尔所发展的一种排序算法。在平均状况下,排序n 个项目要O(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。
一.排序步骤总结:
快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。
1.用三数中值分割法找出枢纽元(基准)。
2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
二.快速排序算法
/*************************************************************** *版权所有 (C)2014,公司名称。 * *文件名称:快速排序法 *内容摘要:无 *其它说明:无 *当前版本:V1.0 *作 者:若云流风 *完成日期:2014.6.14 ***************************************************************/ #include <stdio.h> #define N (14) #define cutoff (3) //截止范围小于等于3 void disp(void); int a[N]={8,14,3,12,10,7,5,1,9,4,11,13,2,6}; /*交换函数*/ void Swap(int *a, int *b) { int t; t = *a; *a = *b; *b = t; } /*三种值分割*/ int Median3(int a[], int left, int right) { //取数据的头、尾和中间三个数,并对他们进行排序 //排序结果直接保存在数组中 int centre = (left + right)/2; if(a[left] > a[centre]) Swap(&a[left], &a[centre]); if(a[left] > a[right]) Swap(&a[left], &a[right]); if(a[centre] > a[right]) Swap(&a[centre], &a[right]); //把中值,即枢纽与数组倒数第二个元素交换 Swap(&a[centre], &a[right - 1]); return a[right - 1];//返回枢纽 } /*快速排序程序*/ void QSort(int a[], int left, int right) { //如果需要排序的数据大于3个则使用快速排序 if(right - left >= cutoff) { //取得枢纽的值 int centre = Median3(a, left, right); int i = left; int j = right - 1; while(1) { /*向后扫描数组,找出大于枢纽元素的元素 * 由于在选择枢纽时,已经把比枢纽值大的数据放在right位置 * 所以不会越界 */ while(a[++i] < centre); //当i大于等于中枢元素时候跳出循环 /*向前扫描数组,找出小于枢纽元素的元素 * 由于在选择枢纽时,已经把比枢纽值小的数据放在left位置 * 所以不会越界 */ while(a[--j] > centre); //把比枢纽小的数据放在前部,大的放到后部 if(i < j) { Swap(&a[i], &a[j]); printf("\n快速排序结果: "); disp(); //打印 } else { //disp(); break; } } Swap(&a[i], &a[right - 1]); //还原枢纽元素 printf("\n 还原枢纽元素后结果: "); disp(); QSort(a, left, i - 1); QSort(a, i + 1, right); } else //如果要排序的数据很少,少于等于3个,则直接使用冒泡排序 { InsertionSort(a+left, right - left + 1); } } /*插入排序*/ int InsertionSort(int a[],int M) { int j,p,temp; for(p=1;p<M;p++) { temp=a[p]; //a[p]和左面的有序数列去比较 /*j>0保证不溢出,因为当j=0时啊a[j-1]非法,用a[p]分别与左面的值相比较 **如果a[p]小的话则互换位置, */ for(j=p; j>0 && a[j-1]>temp;j--) { a[j]=a[j-1]; } a[j]=temp; } printf("\n插入排序结果: "); disp(); } /*输出函数*/ void disp(void) { int i; printf("\n排序结果: \n"); for(i=0;i<N;i++) { printf("%d", a[i]); printf(" "); } } int main(void) { QSort(a , 0, N-1); // disp(); return 0; }
三.算法会说话
1.输出结果
2.总体过程分析
a.三数中值分割法
8,14,3,12,10,7,5,1,9,4,11,13,2,6
红色的三个数字按照大小顺序排好,中间的那个元素叫做中枢元,将中枢元和倒数第二个元素互换位置后返回。
5,14,3,12,10,7,2,1,9,4,11,13,6,8
b.快速排序
5,14,3,12,10,7,2,1,9,4,11,13,6,8
(找出比中枢元大的) i --> <--j(找出比中枢元小的)
5,14,3,12,10,7,2,1,9,4,11,13,6,8
i <--交换--> j
i <--交换--> j
i <--> j
j i i>j退出
还原枢纽元素
注意此时产生的结果就是以枢纽元素为分界线,左面的全部小于枢纽元素,右面的全部大于枢纽元素
先对6前面的排序:
5, 4, 3, 1, 2
2, 4, 1, 3, 5
i j
2,1(插入排序) 3 4 ,5(插入排序)
6后面的排序和前面类似,故不再具体分析。
参考:1.维基百科
2.数据结构与算法分析---C语言描述 Mark Allen Weiss 著