C語(yǔ)言快速排序算法

C語(yǔ)言快速排序算法概述快速排序(QuickSort)是一種有效的排序算法。雖然算法在最壞的情況下運(yùn)行時(shí)間為 0(nA2)，但由于平均運(yùn)行時(shí)間為0(nlogn)，并且在內(nèi)存使用、程序?qū)崿F(xiàn)復(fù)雜性上表現(xiàn)優(yōu)秀，尤其是對(duì)快速排序算法進(jìn)行隨機(jī)化的可能，使得快速排序在一般情況下是最實(shí)用的排序方法之一?？焖倥判虮徽J(rèn)為是當(dāng)前最優(yōu)秀的內(nèi)部排序方法。實(shí)現(xiàn)快速排序的實(shí)現(xiàn)基于分治法，具體分為三個(gè)步驟。假設(shè)待排序的序列為 L[m..n]。分解：序列L[m..n]被劃分成兩個(gè)可能為空的子序列 L[m..pivot-1]和L[pivot+1..n]，使L[m..pivot-1]的每個(gè)元素均小于或等于L[pivot]，同時(shí)L[pivot+1..n]的每個(gè)元素均大于L[pivot]。其中L[pivot]稱(chēng)為這一趟分割中的主元(也稱(chēng)為樞軸、支點(diǎn))。解決：通過(guò)遞歸調(diào)用快速排序，對(duì)子序列 L[m..pivot-1]和L[pivot+1..r]排序。合并：由于兩個(gè)子序列是就地排序的，所以對(duì)它們的合并不需要操作，整個(gè)序列 L[m..n]已排好序。性質(zhì)內(nèi)部排序快速排序是一種內(nèi)部排序方法。也就是說(shuō)快速排序的排序?qū)ο笫亲x入內(nèi)存的數(shù)據(jù)。比較排序快速排序確定元素位置的方法基于元素之間關(guān)鍵字大小的比較。所有基于比較方法的排序方法的時(shí)間下界不會(huì)低于 O(nlgn)。這個(gè)結(jié)論的具體證明， 請(qǐng)參考有關(guān)算法的書(shū)籍， 例如《算法導(dǎo)論》(第一版)第8章(第二版在第七章 QuickSort)。在理想情況下，能?chē)?yán)格地達(dá)到O(nlgn)的下界。一般情況下，快速排序與隨機(jī)化快速排序的平均情況性能都達(dá)到了O(nign)。不穩(wěn)定性快速排序是一種不穩(wěn)定的排序方法。簡(jiǎn)單地說(shuō)，元素 a1,a2的關(guān)鍵字有a1.key=a2.key，則不穩(wěn)定的排序方法不能保證a1,a2在排序后維持原來(lái)的位置先后關(guān)系。原地排序在排序的具體操作過(guò)程中，除去程序運(yùn)行實(shí)現(xiàn)的空間消費(fèi)(例如遞歸棧) ，快速排序算法只需消耗確定數(shù)量的空間(即S(1)，常數(shù)級(jí)空間)。這個(gè)性質(zhì)的意義，在于在內(nèi)存空間受到限制的系統(tǒng)(例如 MCU)中，快速排序也能夠很好地工作。時(shí)空復(fù)雜度快速排序每次將待排序數(shù)組分為兩個(gè)部分，在理想狀況下，每一次都將待排序數(shù)組劃分成等長(zhǎng)兩個(gè)部分，則需要logn次劃分。而在最壞情況下，即數(shù)組已經(jīng)有序或大致有序的情況下，每次劃分只能減少一個(gè)元素，快速排序?qū)⒉恍彝嘶癁槊芭菖判?，所以快速排序時(shí)間復(fù)雜度下界為 O(nlogn)，最壞情況為0(n人2)。在實(shí)際應(yīng)用中，快速排序的平均時(shí)間復(fù)雜度為0(nlogn)?？焖倥判蛟趯?duì)序列的操作過(guò)程中只需花費(fèi)常數(shù)級(jí)的空間?？臻g復(fù)雜度 S(1)。但需要注意遞歸棧上需要花費(fèi)最少 logn最多n的空間。隨機(jī)化算法快速排序的最壞情況基于每次劃分對(duì)主元的選擇?；镜目焖倥判蜻x取第一個(gè)元素作為主元。這樣在數(shù)組已經(jīng)有序的情況下，每次劃分將得到最壞的結(jié)果。一種比較常見(jiàn)的優(yōu)化方法是隨機(jī)化算法，即隨機(jī)選取一個(gè)元素作為主元。這種情況下雖然最壞情況仍然是 0(nA2)，但最壞情況不再依賴于輸入數(shù)據(jù)，而是由于隨機(jī)函數(shù)取值不佳。實(shí)際上，隨機(jī)化快速排序得到理論最壞情況的可能性僅為 1/(2An)。所以隨機(jī)化快速排序可以對(duì)于絕大多數(shù)輸入數(shù)據(jù)達(dá)到O(nlogn)的期望時(shí)間復(fù)雜度。一位前輩做出了一個(gè)精辟的總結(jié)：“隨機(jī)化快速排序可以滿足一個(gè)人一輩子的人品需求。隨機(jī)化快速排序的唯一缺點(diǎn)在于，一旦輸入數(shù)據(jù)中有很多的相同數(shù)據(jù)，隨機(jī)化的效果將直接減弱。對(duì)于極限情況，即對(duì)于n個(gè)相同的數(shù)排序，隨機(jī)化快速排序的時(shí)間復(fù)雜度將毫無(wú)疑問(wèn)的降低到 O(nA2)。減少遞歸棧使用的優(yōu)化快速排序的實(shí)現(xiàn)需要消耗遞歸棧的空間，而大多數(shù)情況下都會(huì)通過(guò)使用系統(tǒng)遞歸棧來(lái)完成遞歸求解。在元素?cái)?shù)量較大時(shí)，對(duì)系統(tǒng)棧的頻繁存取會(huì)影響到排序的效率。一種常見(jiàn)的辦法是設(shè)置一個(gè)閾值，在每次遞歸求解中，如果元素總數(shù)不足這個(gè)閾值，則放棄快速排序，調(diào)用一個(gè)簡(jiǎn)單的排序過(guò)程完成該子序列的排序。這樣的方法減少了對(duì)系統(tǒng)遞歸棧的頻繁存取，節(jié)省了時(shí)間的消費(fèi)。一般的經(jīng)驗(yàn)表明，閾值取一個(gè)較小的值，排序算法采用選擇、插入等緊湊、簡(jiǎn)潔的排序。一個(gè)可以參考的具體方案：閾值T=10,排序算法用選擇排序。閾值不要太大，否則省下的存取系統(tǒng)棧的時(shí)間，將會(huì)被簡(jiǎn)單排序算法較多的時(shí)間花費(fèi)所抵消。另一個(gè)可以參考的方法，是自行建棧模擬遞歸過(guò)程。但實(shí)際經(jīng)驗(yàn)表明，收效明顯不如設(shè)置閾值。C例程以下是C語(yǔ)言權(quán)威《TheCProgrammingLanguage》中的例程，在這個(gè)例程中，對(duì)于數(shù)組 v的left到right號(hào)元素以遞增順序排序。//Qsort.cbyTydus.#include<stdio.h>intarr[]={14,10,11,5,6,15,0,15,16,14,0,8,17,15,7,19,17,1,18,7};/*swap函數(shù)：交換v[k]與v[j]的值*/inlinevoidswap(intv[],intk,intj){inttemp;temp=v[k];v[k]=v[j];v[j]=temp;}voidqsort(intv[],intleft,intright){intj,last;TOC\o"1-5"\h\zif(left>=right)/* 若數(shù)組包含的元素個(gè)數(shù)少于兩個(gè) */return;/*則不執(zhí)行任何操作 */swap(v,left,(left+right)/2);/* 將劃分子集的元素移動(dòng)到 V[0]*/last=left;/*用last記錄中比關(guān)鍵字小間的最右位置 */for(j=left+1;j<=right;j++)/*劃分子集*/{if(v[j]<v[left]){swap(v,last++,j);}}/*小小。。。關(guān)鍵字大大大大*/qsort(v,left,last-1);qsort(v,last+1,right);}voidmain(){intj;qsort(arr,0,19);for(j=0;j<=19;j++){printf("%d",arr[j]);}printf("\n");}消除遞歸的快速排序10A6傳統(tǒng)的快速排序是遞歸的，這就會(huì)受到遞歸棧深度的限制。比如在一臺(tái)普通的 10A6以上時(shí)，傳統(tǒng)的遞歸快排會(huì)導(dǎo)致棧溢出異常，或者一個(gè)莫名其妙的錯(cuò)誤結(jié)果。所以，對(duì)于巨大的數(shù)據(jù)規(guī)模，將快速排序消除遞歸是十分必要的。而消除遞歸，又將帶來(lái)巨大的性能提升，把系統(tǒng)級(jí)的消耗降到最低。消除遞歸的方法，就是模擬棧操作。但是從代碼可以看出，這種模擬的消耗幾乎可以忽略不計(jì)。因此消除遞歸的快排的效率是有保障的。(雖然下面的代碼沒(méi)有使用隨機(jī)化，但經(jīng)過(guò)測(cè)試，它是目前所有快排編寫(xiě)方法中，效率最高，速度最快的！////////////////////////////////////////////////////////////////////////////////#defineMAXARRAY10000#definePUSH(A,B){sl[sp]=A;sr[sp]=B;sp++;}#definePOP(A,B){sp--;A=sl[sp];B=sr[sp];}voidquicksort^nta[],intl,intr){staticintsl[MAXARRAY],sr[MAXARRAY],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(a[i]<p)i++;while(a[j]>p)j--;if(i<=j){t=a[i];a[i]=a[j];a[j]=t;i++;j--;}}if(l<j)PUSH(l,j);if(i<r)PUSH(i,r);}}//////////////////////////////////////////////////////////////////////////////////(十二)C語(yǔ)言隨機(jī)化快排模塊化代碼#include"stdio.h"#include"stdlib.h"#include"time.h"Location(int*a,intlow,inthigh){intkey,temp,x;srand((unsigned)time(0));x=rand()%(high-low+1)+low;key=a[x];while(low<high){while(x<high&&key<=a[high])high--;temp=a[high];a[high]=key;a[x]=temp;x=high;while(low<x&&key>=a[low])low++;temp=a[low];a[low]=key;a[x]=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);}(十三)快速排序的JAVA實(shí)現(xiàn)importjava.util.Arrays;publicclassQuickSort{publicstaticvoidquickSort(int[]array){quickSort(array,0,array.length-1);}privatestaticvoidquickSort(int[]array,intlow,inthigh){if(low<high){intp=partition(array,low,high);quickSort(array,low,p-1);quickSort(array,p+1,high);}}privatestaticintpartition(int[]array,intlow,inthigh){ints=array[high];inti=low-1;for(intj=low;j<high;j++){if(array[j]<s){i++;swap(array,i,j);}}swap(array,++i,high);returni;}privatestaticvoidswap(int[]array,inti,