C語言快速排序

1、快速排序(一)概述快速排序(QuickSort)是一種有效的排序算法。雖然算法在最壞的情況下運行時間為0(2),但由于平均運行時間為O(nlogn)，并且在內存使用、程序實現(xiàn)復雜性上表現(xiàn)優(yōu)秀，尤其是對快速排序算法進行隨機化的可能，使得快速排序在一般情況下是最實用的排序方法之一。快速排序被認為是當前最優(yōu)秀的內部排序方法。實現(xiàn)快速排序的實現(xiàn)基于分治法，具體分為三個步驟。假設待排序的序列為Lm.n。分解：序列Lm.n被劃分成兩個可能為空的子序列Lm.pivot-1和Lpivot+1.n，使Lm.pivot-1的每個元素均小于或等于Lpivot，同時Lpivot+1.n的每個元素均大于Lpivot。其

2、中Lpivot稱為這一趟分割中的主元(也稱為樞軸、支點)。解決：通過遞歸調用快速排序，對子序列Lm.pivot-1和Lpivot+1.r排序。合并：由于兩個子序列是就地排序的，所以對它們的合并不需要操作，整個序列Lm.n已排好序。性質內部排序快速排序是一種內部排序方法。也就是說快速排序的排序對象是讀入內存的數(shù)據(jù)。比較排序快速排序確定元素位置的方法基于元素之間關鍵字大小的比較。所有基于比較方法的排序方法的時間下界不會低于O(nlgn)。這個結論的具體證明，請參考有關算法的書籍，例如算法導論(第一版)第8章(第二版在第七章QuickSort)。在理想情況下，能嚴格地達到O(nlgn)的下界。一般情

3、況下，快速排序與隨機化快速排序的平均情況性能都達到了O(nlgn)。不穩(wěn)定性快速排序是一種不穩(wěn)定的排序方法。簡單地說，元素a1,a2的關鍵字有a1.key=a2.key,則不穩(wěn)定的排序方法不能保證a1,a2在排序后維持原來的位置先后關系。原地排序在排序的具體操作過程中，除去程序運行實現(xiàn)的空間消費(例如遞歸棧)，快速排序算法只需消耗確定數(shù)量的空間(即S(1)，常數(shù)級空間)。這個性質的意義，在于在內存空間受到限制的系統(tǒng)(例如MCU)中，快速排序也能夠很好地工作。時空復雜度快速排序每次將待排序數(shù)組分為兩個部分，在理想狀況下，每一次都將待排序數(shù)組劃分成等長兩個部分，則需要logn次劃分。而在最壞情況下

4、，即數(shù)組已經有序或大致有序的情況下，每次劃分只能減少一個元素，快速排序將不幸退化為冒泡排序，所以快速排序時間復雜度下界為O(nlogn)，最壞情況為0(2)。在實際應用中，快速排序的平均時間復雜度為O(nlogn)?？焖倥判蛟趯π蛄械牟僮鬟^程中只需花費常數(shù)級的空間?？臻g復雜度S(1)。但需要注意遞歸棧上需要花費最少logn最多n的空間。隨機化算法快速排序的最壞情況基于每次劃分對主元的選擇?；镜目焖倥判蜻x取第一個元素作為主元。這樣在數(shù)組已經有序的情況下，每次劃分將得到最壞的結果。一種比較常見的優(yōu)化方法是隨機化算法，即隨機選取一個元素作為主元。這種情況下雖然最壞情況仍然是0(2),但最壞情況不再

5、依賴于輸入數(shù)據(jù)，而是由于隨機函數(shù)取值不佳。實際上,隨機化快速排序得到理論最壞情況的可能性僅為1/(2九)。所以隨機化快速排序可以對于絕大多數(shù)輸入數(shù)據(jù)達到O(nlogn)的期望時間復雜度。一位前輩做出了一個精辟的總結：“隨機化快速排序可以滿足一個人一輩子的人品需求?！彪S機化快速排序的唯一缺點在于，一旦輸入數(shù)據(jù)中有很多的相同數(shù)據(jù)，隨機化的效果將直接減弱。對于極限情況，即對于n個相同的數(shù)排序，隨機化快速排序的時間復雜度將毫無疑問的降低到O(2)。減少遞歸棧使用的優(yōu)化快速排序的實現(xiàn)需要消耗遞歸棧的空間，而大多數(shù)情況下都會通過使用系統(tǒng)遞歸棧來完成遞歸求解。在元素數(shù)量較大時，對系統(tǒng)棧的頻繁存取會影響到排序

6、的效率。一種常見的辦法是設置一個閾值，在每次遞歸求解中，如果元素總數(shù)不足這個閾值，則放棄快速排序，調用一個簡單的排序過程完成該子序列的排序。這樣的方法減少了對系統(tǒng)遞歸棧的頻繁存取，節(jié)省了時間的消費。一般的經驗表明，閾值取一個較小的值，排序算法采用選擇、插入等緊湊、簡潔的排序。一個可以參考的具體方案：閾值T=10,排序算法用選擇排序。閾值不要太大，否則省下的存取系統(tǒng)棧的時間，將會被簡單排序算法較多的時間花費所抵消。另一個可以參考的方法,是自行建棧模擬遞歸過程。但實際經驗表明,收效明顯不如設置閾值。C例程以下是C語言權威TheCProgrammingLanguage中的例程，在這個例程中，對于數(shù)組

7、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函數(shù)：交換vk與vj的值*/inlinevoidswap(intv,intk,intj)inttemp;temp=vk;vk=vj;vj=temp;voidqsort(intv,intleft,intright)intj,last;if(left=right)/*若數(shù)組包含的元素個數(shù)少于兩個*/return;/*則不執(zhí)行任何操作*/swap(v,left,(left+rig

8、ht)/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);消除遞歸的快速排序傳統(tǒng)的快速排序是遞歸的，這就會受到遞歸棧深度的限制。比如在一臺普通的PC上，當待排序元素達

9、到10人6以上時，傳統(tǒng)的遞歸快排會導致棧溢出異常，或者一個莫名其妙的錯誤結果。所以，對于巨大的數(shù)據(jù)規(guī)模，將快速排序消除遞歸是十分必要的。而消除遞歸，又將帶來巨大的性能提升，把系統(tǒng)級的消耗降到最低。消除遞歸的方法，就是模擬棧操作。但是從代碼可以看出，這種模擬的消耗幾乎可以忽略不計。因此消除遞歸的快排的效率是有保障的。(雖然下面的代碼沒有使用隨機化，但經過測試，它是目前所有快排編寫方法中，效率最高，速度最快的！)/#defineMAXARRAY10000#definePUSH(A,B)slsp=A;srsp=B;sp+;#definePOP(A,B)sp-;A=slsp;B=srsp;voidqu

10、icksort(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標準庫中提供了快速排序，但作為快速排序的介紹，原理程序的代碼更加有助于對快速排序運行過程的分析。在這個例程中，對于數(shù)組x的0n-1號元

11、素的排序，初始調用為：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+;swap(LiPivPos,Li);iPivPos+

12、;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)參數(shù)表*base:待排序的元素(數(shù)組，下標0起)。num:元素的數(shù)量。width:每個元素的內存空間大小(以字節(jié)為單位)?？捎胹izeof()測得。int(*)compare:指向一個比較函數(shù)。*eleml*elem2:指向待比較的

13、數(shù)據(jù)。比較函數(shù)的返回值返回值是int類型，確定elem1與elem2的相對位置。elem1在elem2右側返回正數(shù)，elem1在elem2左側返回負數(shù)?？刂品祷刂悼梢源_定升序/降序。一個升序排序的例程：intCompare(constvoid*elem1,constvoid*elem2)return*(int*)(elem1)-*(int*)(elem2);intmain()inta100;qsort(a,100,sizeof(int),Compare);return0;(十一)PASCAL例程1.基本思想：在當前無序區(qū)R1.H中任取一個數(shù)據(jù)元素作為比較的基準(不妨記為X)，用此基準將當前無序

14、區(qū)劃分為左右兩個較小的無序區(qū)：R1.I-1和RI+1.H，且左邊的無序子區(qū)中數(shù)據(jù)元素均小于等于基準元素，右邊的無序子區(qū)中數(shù)據(jù)元素均大于等于基準元素，而基準X則位于最終排序的位置上，即R1.I-1WX.KeyWRI+1.H(1WlWH),當R1.I-1和RI+1.H均非空時，分別對它們進行上述的劃分過程，直至所有無序子區(qū)中的數(shù)據(jù)元素均已排序為止。2.排序過程：【示例】：初始關鍵字10584615472(n為10)第一次交換后2544516810第二次交換后2144556810第三次交換后1244556810最后的排序結果1244556810typexxx=array1.1000000oflong

15、int;vara,n;longint;x:xxx;procedureqsort(varx:xxx;l,r:longint);x為要排序的數(shù)組，1為數(shù)組的要排序部分的起始位置，r為數(shù)組的要排序部分的終點位置varn,i,j,mid:1ongint;begini:=l;右邊起點值j:=r;左邊終點值mid:=x(i+j)div2;基準數(shù)(用隨機化更快)repeatwhile(iv=j)and(xvmid)doinc(i);若左邊的數(shù)比基準數(shù)小且左、右區(qū)未定，保留在左邊while(imid)dodec(j);若右邊的數(shù)比基準數(shù)大且左、右區(qū)未定，保留在右邊ifij;直到左右區(qū)已定(即左邊終點j小于右邊

16、起點i)ifilthenqsort(x,l,j);若左邊多于一個數(shù)，快排左邊end;beginreadln(n);讀入要排序的數(shù)的個數(shù)fora:=1tondoread(xa);讀入要排序的書writeln;qsort(x,1,n);排序程序fora:=1ton-1dowrite(xa,);輸出排好序得數(shù)writeln(xn);end.(十二)C語言隨機化快排模塊化代碼#includestdio.h#includestdlib.h#includetime.hLocation(int*a,intlow,inthigh)intkey,temp,x;srand(unsigned)time(0);x=r

17、and()%(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,locat-1);Qsort(a,locat+1,high);(

18、十三)快速排序的JAVA實現(xiàn)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);privatestaticintpartition(intarray,intlow,inthigh)ints=arrayhigh;inti=low-1;for(intj=low;