C语言快速排序

《C语言快速排序》由会员分享，可在线阅读，更多相关《C语言快速排序（6页珍藏版）》请在装配图网上搜索。

1、快速排序(一)概述快速排序(QuickSort)是一种有效的排序算法。虽然算法在最坏的情况下运行时间为0(2),但由于平均运行时间为O(nlogn)，并且在内存使用、程序实现复杂性上表现优秀，尤其是对快速排序算法进行随机化的可能，使得快速排序在一般情况下是最实用的排序方法之一。快速排序被认为是当前最优秀的内部排序方法。(二) 实现快速排序的实现基于分治法，具体分为三个步骤。假设待排序的序列为Lm.n。分解：序列Lm.n被划分成两个可能为空的子序列Lm.pivot-1和Lpivot+1.n，使Lm.pivot-1的每个元素均小于或等于Lpivot，同时Lpivot+1.n的每个元素均大于Lpiv

2、ot。其中Lpivot称为这一趟分割中的主元(也称为枢轴、支点)。解决：通过递归调用快速排序，对子序列Lm.pivot-1和Lpivot+1.r排序。合并：由于两个子序列是就地排序的，所以对它们的合并不需要操作，整个序列Lm.n已排好序。(三) 性质内部排序快速排序是一种内部排序方法。也就是说快速排序的排序对象是读入内存的数据。比较排序快速排序确定元素位置的方法基于元素之间关键字大小的比较。所有基于比较方法的排序方法的时间下界不会低于O(nlgn)。这个结论的具体证明，请参考有关算法的书籍，例如算法导论(第一版)第8章(第二版在第七章QuickSort)。在理想情况下，能严格地达到O(nlgn

3、)的下界。一般情况下，快速排序与随机化快速排序的平均情况性能都达到了O(nlgn)。不稳定性快速排序是一种不稳定的排序方法。简单地说，元素a1,a2的关键字有a1.key=a2.key,则不稳定的排序方法不能保证a1,a2在排序后维持原来的位置先后关系。原地排序在排序的具体操作过程中，除去程序运行实现的空间消费(例如递归栈)，快速排序算法只需消耗确定数量的空间(即S(1)，常数级空间)。这个性质的意义，在于在内存空间受到限制的系统(例如MCU)中，快速排序也能够很好地工作。(四) 时空复杂度快速排序每次将待排序数组分为两个部分，在理想状况下，每一次都将待排序数组划分成等长两个部分，则需要log

4、n次划分。而在最坏情况下，即数组已经有序或大致有序的情况下，每次划分只能减少一个元素，快速排序将不幸退化为冒泡排序，所以快速排序时间复杂度下界为O(nlogn)，最坏情况为0(2)。在实际应用中，快速排序的平均时间复杂度为O(nlogn)。快速排序在对序列的操作过程中只需花费常数级的空间。空间复杂度S(1)。但需要注意递归栈上需要花费最少logn最多n的空间。(五) 随机化算法快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情况下虽然最坏情

5、况仍然是0(2),但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上,随机化快速排序得到理论最坏情况的可能性仅为1/(2九)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结：“随机化快速排序可以满足一个人一辈子的人品需求。”随机化快速排序的唯一缺点在于，一旦输入数据中有很多的相同数据，随机化的效果将直接减弱。对于极限情况，即对于n个相同的数排序，随机化快速排序的时间复杂度将毫无疑问的降低到O(2)。(六) 减少递归栈使用的优化快速排序的实现需要消耗递归栈的空间，而大多数情况下都会通过使用系统递归栈来完成递归求解。在元素数

6、量较大时，对系统栈的频繁存取会影响到排序的效率。一种常见的办法是设置一个阈值，在每次递归求解中，如果元素总数不足这个阈值，则放弃快速排序，调用一个简单的排序过程完成该子序列的排序。这样的方法减少了对系统递归栈的频繁存取，节省了时间的消费。一般的经验表明，阈值取一个较小的值，排序算法采用选择、插入等紧凑、简洁的排序。一个可以参考的具体方案：阈值T=10,排序算法用选择排序。阈值不要太大，否则省下的存取系统栈的时间，将会被简单排序算法较多的时间花费所抵消。另一个可以参考的方法,是自行建栈模拟递归过程。但实际经验表明,收效明显不如设置阈值。(七) C例程以下是C语言权威TheCProgramming

7、Language中的例程，在这个例程中，对于数组v的left到right号元素以递增顺序排序。/Qsort.cbyTydus.#includeintarr=14,10,11,5,6,15,0,15,16,14,0,8,17,15,7,19,17,1,18,7;/*swap函数：交换vk与vj的值*/inlinevoidswap(intv,intk,intj)inttemp;temp=vk;vk=vj;vj=temp;voidqsort(intv,intleft,intright)intj,last;if(left=right)/*若数组包含的元素个数少于两个*/return;/*则不执行任何操

8、作*/swap(v,left,(left+right)/2);/*将划分子集的元素移动到V0*/last=left;/*用last记录中比关键字小间的最右位置*/for(j=left+1;j=right;j+)/*划分子集*/if(vjvleft)swap(v,last+,j);/*小小。关键字大大大大*/qsort(v,left,last-1);qsort(v,last+1,right);voidmain()intj;qsort(arr,0,19);for(j=0;j=19;j+)printf(%d,arrj);printf(n);(八) 消除递归的快速排序传统的快速排序是递归的，这就会受到

9、递归栈深度的限制。比如在一台普通的PC上，当待排序元素达到10人6以上时，传统的递归快排会导致栈溢出异常，或者一个莫名其妙的错误结果。所以，对于巨大的数据规模，将快速排序消除递归是十分必要的。而消除递归，又将带来巨大的性能提升，把系统级的消耗降到最低。消除递归的方法，就是模拟栈操作。但是从代码可以看出，这种模拟的消耗几乎可以忽略不计。因此消除递归的快排的效率是有保障的。(虽然下面的代码没有使用随机化，但经过测试，它是目前所有快排编写方法中，效率最高，速度最快的！)/#defineMAXARRAY10000#definePUSH(A,B)slsp=A;srsp=B;sp+;#definePOP(

10、A,B)sp-;A=slsp;B=srsp;voidquicksort(inta,intl,intr)staticintslMAXARRAY,srMAXARRAY,sp;inti,j,p,t;sp=0;PUSH(l,r);while(sp)POP(l,r);i=l;j=r;p=a(i+j)/2;while(i=j)while(aip)j-;if(i=j)t=ai;ai=aj;aj=t;i+;j-;if(lj)PUSH(l,j);if(ir)PUSH(i,r);/(九)C+例程以下是一个用C+编写的快速排序程序。虽然C标准库中提供了快速排序，但作为快速排序的介绍，原理程序的代码更加有助于对快速排

11、序运行过程的分析。在这个例程中，对于数组x的0n-1号元素的排序，初始调用为：quicksorts,0,n-1);intquicksort_partition(intL,intLbb,intUbb)/随机化intiRndPivID;srand(unsigned(time(0);iRndPivID=(rand()%(Ubb-Lbb+1)+Lbb;swap(LiRndPivID,LUbb);/快排intiPivValue;inti;intiPivPos;iPivValue=LUbb;iPivPos=Lbb-1;for(i=Lbb;i=Ubb-1;i+)if(Li=iPivValue)iPivPos

12、+;swap(LiPivPos,Li);iPivPos+;swap(LiPivPos,LUbb);returniPivPos;voidquicksort(intL,intLbb,intUbb)intiPiv;if(Lbb或#includevstdlib.hqsort(void*base,size_tnum,size_twidth,int(*)compare(constvoid*elem1,constvoid*elem2)参数表*base:待排序的元素(数组，下标0起)。num:元素的数量。width:每个元素的内存空间大小(以字节为单位)。可用sizeof()测得。int(*)compare:

13、指向一个比较函数。*eleml*elem2:指向待比较的数据。比较函数的返回值返回值是int类型，确定elem1与elem2的相对位置。elem1在elem2右侧返回正数，elem1在elem2左侧返回负数。控制返回值可以确定升序/降序。一个升序排序的例程：intCompare(constvoid*elem1,constvoid*elem2)return*(int*)(elem1)-*(int*)(elem2);intmain()inta100;qsort(a,100,sizeof(int),Compare);return0;(十一)PASCAL例程1.基本思想：在当前无序区R1.H中任取一个

14、数据元素作为比较的基准(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R1.I-1和RI+1.H，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R1.I-1WX.KeyWRI+1.H(1WlWH),当R1.I-1和RI+1.H均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。2.排序过程：【示例】：初始关键字10584615472(n为10)第一次交换后2544516810第二次交换后2144556810第三次交换后1244556810最后的排序结果1244556810

15、typexxx=array1.1000000oflongint;vara,n;longint;x:xxx;procedureqsort(varx:xxx;l,r:longint);x为要排序的数组，1为数组的要排序部分的起始位置，r为数组的要排序部分的终点位置varn,i,j,mid:1ongint;begini:=l;右边起点值j:=r;左边终点值mid:=x(i+j)div2;基准数(用随机化更快)repeatwhile(iv=j)and(xvmid)doinc(i);若左边的数比基准数小且左、右区未定，保留在左边while(imid)dodec(j);若右边的数比基准数大且左、右区未定，

16、保留在右边ifij;直到左右区已定(即左边终点j小于右边起点i)ifilthenqsort(x,l,j);若左边多于一个数，快排左边end;beginreadln(n);读入要排序的数的个数fora:=1tondoread(xa);读入要排序的书writeln;qsort(x,1,n);排序程序fora:=1ton-1dowrite(xa,);输出排好序得数writeln(xn);end.(十二)C语言随机化快排模块化代码#includestdio.h#includestdlib.h#includetime.hLocation(int*a,intlow,inthigh)intkey,temp,

17、x;srand(unsigned)time(0);x=rand()%(high-low+1)+low;key=ax;while(lowhigh)while(xhigh&key=ahigh)high-;temp=ahigh;ahigh=key;ax=temp;x=high;while(low=alow)low+;temp=alow;alow=key;ax=temp;x=low;returnlow;Qsort(int*a,intlow,inthigh)intlocat,i;if(low=high)return0;locat=Location(a,low,high);Qsort(a,low,loca

18、t-1);Qsort(a,locat+1,high);(十三)快速排序的JAVA实现importjava.util.Arrays;publicclassQuickSortpublicstaticvoidquickSort(intarray)quickSort(array,0,array.length-1);privatestaticvoidquickSort(intarray,intlow,inthigh)if(lowhigh)intp=partition(array,low,high);quickSort(array,low,p-1);quickSort(array,p+1,high);pr

19、ivatestaticintpartition(intarray,intlow,inthigh)ints=arrayhigh;inti=low-1;for(intj=low;jhigh;j+)if(arrayjs)i+;swap(array,i,j);swap(array,+i,high);returni;privatestaticvoidswap(intarray,inti,intj)inttemp;temp=arrayi;arrayi=arrayj;arrayj=temp;/*paramargs*/publicstaticvoidmain(Stringargs)intarr=12,3,5,4,78,67,1,33,1,1,1;quickSort(arr);System.out.println(Arrays.toString(arr);