快速排序(QuickSort)是一種有效的排序算法。雖然算法在最壞的情況下運(yùn)行時間為O(n^2)，但由于平均運(yùn)行時間為O(nlogn)，并且在內(nèi)存使用、程序?qū)崿F(xiàn)復(fù)雜性上表現(xiàn)優(yōu)秀，尤其是對快速排序算法進(jìn)行隨機(jī)化的可能，使得快速排序在一般情況下是最實(shí)用的排序方法之一。快速排序被認(rèn)為是當(dāng)前最優(yōu)秀的內(nèi)部排序方法。

快速排序_快速排序 -實(shí)現(xiàn)

快速排序的實(shí)現(xiàn)基于分治法，具體分為三個步驟。假設(shè)待排序的序列為L[m..n]。
分解：序列L[m..n]被劃分成兩個可能為空的子序列L[m..pivot-1]和L[pivot+1..n]，使L[m..pivot-1]的每個元素均小于或等于L[pivot]，同時L[pivot+1..n]的每個元素均大于L[pivot]。其中L[pivot]稱為這一趟分割中的主元（也稱為樞軸、支點(diǎn)）。
解決：通過遞歸調(diào)用快速排序，對子序列L[m..pivot-1]和L[pivot 1..r]排序。
合并：由于兩個子序列是就地排序的，所以對它們的合并不需要操作，整個序列L[m..n]已排好序。

快速排序_快速排序 -性質(zhì)

內(nèi)部排序
快速排序是一種內(nèi)部排序方法。也就是說快速排序的排序?qū)ο笫亲x入內(nèi)存的數(shù)據(jù)。
比較排序
快速排序確定元素位置的方法基于元素之間關(guān)鍵字大小的比較。
所有基于比較方法的排序方法的時間下界不會低于O(nlgn)。這個結(jié)論的具體證明，請參考有關(guān)算法的書籍，例如《算法導(dǎo)論》第8章。
快速排序在理想情況下，能嚴(yán)格地達(dá)到O(nlgn)的下界。一般情況下，快速排序與隨機(jī)化快速排序的平均情況性能都達(dá)到了O(nlgn)。
不穩(wěn)定性
快速排序是一種不穩(wěn)定的排序方法。簡單地說，元素a1,a2的關(guān)鍵字有a1.key=a2.key，則不穩(wěn)定的排序方法不能保證a1,a2在排序后維持原來的位置先后關(guān)系。
原地排序
在排序的具體操作過程中，除去程序運(yùn)行實(shí)現(xiàn)的空間消費(fèi)（例如遞歸棧），快速排序算法只需消耗確定數(shù)量的空間（即S(1)，常數(shù)級空間）。
這個性質(zhì)的意義，在于在內(nèi)存空間受到限制的系統(tǒng)（例如MCU）中，快速排序也能夠很好地工作。

快速排序_快速排序 -時空復(fù)雜度

快速排序每次將待排序數(shù)組分為兩個部分，在理想狀況下，每一次都將待排序數(shù)組劃分成等長兩個部分，則需要logn次劃分。
而在最壞情況下，即數(shù)組已經(jīng)有序或大致有序的情況下，每次劃分只能減少一個元素，快速排序?qū)⒉恍彝嘶癁槊芭菖判?，所以快速排序時間復(fù)雜度下界為O(nlogn)，最壞情況為O(n^2)。在實(shí)際應(yīng)用中，快速排序的平均時間復(fù)雜度為O(nlogn)。
快速排序在對序列的操作過程中只需花費(fèi)常數(shù)級的空間?？臻g復(fù)雜度S(1)。
但需要注意遞歸棧上需要花費(fèi)最少logn最多n的空間。

快速排序_快速排序 -隨機(jī)化算法

快速排序的最壞情況基于每次劃分對主元的選擇?；镜目焖倥判蜻x取第一個元素作為主元。這樣在數(shù)組已經(jīng)有序的情況下，每次劃分將得到最壞的結(jié)果。一種比較常見的優(yōu)化方法是隨機(jī)化算法，即隨機(jī)選取一個元素作為主元。這種情況下雖然最壞情況仍然是O(n^2)，但最壞情況不再依賴于輸入數(shù)據(jù)，而是由于隨機(jī)函數(shù)取值不佳。實(shí)際上，隨機(jī)化快速排序得到理論最壞情況的可能性僅為1/(2^n)。所以隨機(jī)化快速排序可以對于絕大多數(shù)輸入數(shù)據(jù)達(dá)到O(nlogn)的期望時間復(fù)雜度。一位前輩做出了一個精辟的總結(jié)：“隨機(jī)化快速排序可以滿足一個人一輩子的人品需求?！?br>隨機(jī)化快速排序的唯一缺點(diǎn)在于，一旦輸入數(shù)據(jù)中有很多的相同數(shù)據(jù)，隨機(jī)化的效果將直接減弱。對于極限情況，即對于n個相同的數(shù)排序，隨機(jī)化快速排序的時間復(fù)雜度將毫無疑問的降低到O(n^2)。

快速排序_快速排序 -減少遞歸棧使用的優(yōu)化

快速排序的實(shí)現(xiàn)需要消耗遞歸棧的空間，而大多數(shù)情況下都會通過使用系統(tǒng)遞歸棧來完成遞歸求解。在元素數(shù)量較大時，對系統(tǒng)棧的頻繁存取會影響到排序的效率。
一種常見的辦法是設(shè)置一個閾值，在每次遞歸求解中，如果元素總數(shù)不足這個閾值，則放棄快速排序，調(diào)用一個簡單的排序過程完成該子序列的排序。這樣的方法減少了對系統(tǒng)遞歸棧的頻繁存取，節(jié)省了時間的消費(fèi)。
一般的經(jīng)驗(yàn)表明，閾值取一個較小的值，排序算法采用選擇、插入等緊湊、簡潔的排序。一個可以參考的具體方案：閾值T=10，排序算法用選擇排序。
閾值不要太大，否則省下的存取系統(tǒng)棧的時間，將會被簡單排序算法較多的時間花費(fèi)所抵消。

另一個可以參考的方法，是自行建棧模擬遞歸過程。但實(shí)際經(jīng)驗(yàn)表明，收效明顯不如設(shè)置閾值。

快速排序_快速排序 -C例程

以下是C語言權(quán)威《TheCProgrammingLanguage》中的例程，在這個例程中，對于數(shù)組v的left到right號元素以遞增順序排序。

//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與v[j]的值*/
inlinevoidswap(intv[],inti,INTJ)
{
int temp = 0;

temp = v;
v = v[j];
v[j] = temp;
}

voidqsort(intv[],intleft,intright)
{
inti = 0

int last = 0;
voidswap(intv[],inti,intj);

if(left >= right)/*若數(shù)組包含的元素個數(shù)少于兩個*/
return;/*則不執(zhí)行任何操作*/
swap(v,left,(left right) / 2);/*將劃分子集的元素*/
last = left;/*移動到v[0]*/
for(i = left 1; i <= right; i )/*劃分子集*/
if(vswap(v, last,i);
swap(v,left,last);/*恢復(fù)劃分的元素*/
qsort(v,left,last - 1);
qsort(v,last 1,right);
}

intmain(void)

{
qsort(arr,0,19);
inti = 0;
for(i = 0; i <= 19; printf("%d",arr[i ]));
scanf("n");

return 0;
}

快速排序_快速排序 -使用C 標(biāo)準(zhǔn)庫的快速排序函數(shù)

C 的標(biāo)準(zhǔn)庫stdlib.h中提供了快速排序函數(shù)。
請在使用前加入對stdlib.h的引用：#include或#include
qsort(void*base,size_tnum,size_twidth,int(*)compare(constvoid*elem1,constvoid*elem2))

參數(shù)表
*base:待排序的元素（數(shù)組，下標(biāo)0起）。
num:元素的數(shù)量。
width:每個元素的內(nèi)存空間大?。ㄒ宰止?jié)為單位）。可用sizeof()測得。
int(*)compare:指向一個比較函數(shù)。*elem1*elem2:指向待比較的數(shù)據(jù)。
比較函數(shù)的返回值
返回值是int類型，確定elem1與elem2的相對位置。
elem1在elem2右側(cè)返回正數(shù)，elem1在elem2左側(cè)返回負(fù)數(shù)。
控制返回值可以確定升序/降序。

一個升序排序的例程：
intCompare(constvoid*elem1,constvoid*elem2)
{
return*((int*)(elem1))-*((int*)(elem2));
}
intmain()
{
inta[100];
qsort(a,100,sizeof(int),Compare);
return0;
}

快速排序_快速排序 -算法基本思想

快速排序的基本思想是基于分治策略的。對于輸入的子序列L【p..r】，如果規(guī)模足夠小則直接進(jìn)行排序（比如用前述的冒泡、選擇、插入排序均可），否則分三步處理：

分解(Divide)：將待排序列L【p..r】劃分為兩個非空子序列L【p..q】和L【q 1..r】，使L【p..q】中任一元素的值不大于L【q 1..r】中任一元素的值。具體可通過這樣的途徑實(shí)現(xiàn)：在序列L【p..r】中選擇數(shù)據(jù)元素L【q】，經(jīng)比較和移動后，L【q】將處于L【p..r】中間的適當(dāng)位置，使得數(shù)據(jù)元素L【q】的值小于L【q 1..r】中任一元素的值。

遞歸求解(Conquer)：通過遞歸調(diào)用快速排序算法，分別對L【p..q】和L【q 1..r】進(jìn)行排序。

合并(Merge)：由于對分解出的兩個子序列的排序是就地進(jìn)行的，所以在L【p..q】和L【q 1..r】都排好序后不需要執(zhí)行任何計算L【p..r】就已排好序，即自然合并。

這個解決流程是符合分治法的基本步驟的。因此，快速排序法是分治法的經(jīng)典應(yīng)用實(shí)例之一。

快速排序_快速排序 -區(qū)別

快速排序法是對冒泡排序法的一種改進(jìn)，也是基于交換排序的一種算法。因此，被稱為"分區(qū)交換排序"。
在待排序序列中按某種方法選取一個元素K，以它為分界點(diǎn)，用交換的方法將序列分為兩個部分：比該值小的放在左邊，否則在右邊。形成"{左子序列}K{右子序列}"。再分別對左、右兩部分實(shí)施上述分解過程，直到各子序列長度為1，即有序?yàn)橹埂?br>分界點(diǎn)元素值K的選取方法不同，將構(gòu)成不同的排序法，也將影響排序的效率：例如，可取左邊第1個元素為分界點(diǎn)、取中點(diǎn)A【（left right）/2】為分界點(diǎn)、或選取最大和最小值的平均值為分界點(diǎn)等。

快速排序_快速排序 -偽代碼

非隨機(jī)

QUICKSORT(A，p，r)
1ifp<r
2thenq←PARTITION(A，p，r)
3QUICKSORT(A，p，q-1)
4QUICKSORT(A，q+1，r)
為排序一個完整的數(shù)組A，最初的調(diào)用是QUICKSORT(A，1，length[A]）。
快速排序算法的關(guān)鍵是PARTITION過程，它對子數(shù)組A[p..r]進(jìn)行就地重排：
PARTITION(A，p，r)
1x←A[r]
2i←p-1
3forj←ptor-1
4doifA[j]≤x
5theni←i+1
6exchangeA[i]←→A[j]
7exchangeA[i+1]←→A[r]
8returni+1[2]

隨機(jī)

對PARTITION和QUICKSORT所作的改動比較小。在新的劃分過程中，我們在真正進(jìn)行劃分之前實(shí)現(xiàn)交換：
（其中PARTITION過程同快速排序偽代碼（非隨機(jī)））
RANDOMIZED-PARTITION(A，p，r)
1i←RANDOM(p，r)
2exchangeA[r]←→A[i]
3returnPARTITION(A，p，r)
新的快速排序過程不再調(diào)用PARTITION，而是調(diào)用RANDOMIZED-PARTITION。
RANDOMIZED-QUICKSORT(A，p，r)
1ifp<r
2thenq←RANDOMIZED-PARTITION(A，p，r)
3RANDOMIZED-QUICKSORT(A，p，q-1)
4RANDOMIZED-QUICKSORT(A，q+1，r)[2]

性能分析

這里為方便起見，我們假設(shè)算法Quick_Sort的范圍閾值為1（即一直將線性表分解到只剩一個元素），這對該算法復(fù)雜性的分析沒有本質(zhì)的影響。
我們先分析函數(shù)partition的性能，該函數(shù)對于確定的輸入復(fù)雜性是確定的。觀察該函數(shù)，我們發(fā)現(xiàn)，對于有n個元素的確定輸入L[p..r]，該函數(shù)運(yùn)行時間顯然為θ（n）。
最壞情況
無論適用哪一種方法來選擇pivot，由于我們不知道各個元素間的相對大小關(guān)系（若知道就已經(jīng)排好序了），所以我們無法確定pivot的選擇對劃分造成的影響。因此對各種pivot選擇法而言，最壞情況和最好情況都是相同的。
我們從直覺上可以判斷出最壞情況發(fā)生在每次劃分過程產(chǎn)生的兩個區(qū)間分別包含n-1個元素和1個元素的時候（設(shè)輸入的表有n個元素）。下面我們暫時認(rèn)為該猜測正確，在后文我們再詳細(xì)證明該猜測。
對于有n個元素的表L[p..r]，由于函數(shù)Partition的計算時間為θ（n），所以快速排序在序壞情況下的復(fù)雜性有遞歸式如下：
T(1)=θ(1),T(n)=T(n-1)+T(1)+θ(n)(1)
用迭代法可以解出上式的解為T(n)=θ（n2）。
這個最壞情況運(yùn)行時間與插入排序是一樣的。
下面我們來證明這種每次劃分過程產(chǎn)生的兩個區(qū)間分別包含n-1個元素和1個元素的情況就是最壞情況。
設(shè)T(n）是過程Quick_Sort作用于規(guī)模為n的輸入上的最壞情況的時間，則
T(n)=max(T(q)+T(n-q))+θ（n)，其中1≤q≤n-1(2)
我們假設(shè)對于任何k<n，總有T(k）≤ck，其中c為常數(shù)；顯然當(dāng)k=1時是成立的。
將歸納假設(shè)代入（2），得到：
T(n）≤max(cq2+c(n-q)2)+θ（n)=c*max(q2+(n-q)2)+θ（n)
因?yàn)樵赱1,n-1]上q2+(n-q)2關(guān)于q遞減，所以當(dāng)q=1時q2+(n-q)2有最大值n2-2(n-1）。于是有：
T(n）≤cn2-2c(n-1)+θ（n）≤cn2
只要c足夠大，上面的第二個小于等于號就可以成立。于是對于所有的n都有T(n）≤cn。
這樣，排序算法的最壞情況運(yùn)行時間為θ（n2），且最壞情況發(fā)生在每次劃分過程產(chǎn)生的兩個區(qū)間分別包含n-1個元素和1個元素的時候。
時間復(fù)雜度為o（n2）。
最好情況
如果每次劃分過程產(chǎn)生的區(qū)間大小都為n/2，則快速排序法運(yùn)行就快得多了。這時有：
T(n)=2T(n/2)+θ（n),T(1)=θ（1)(3)
解得：T(n)=θ（nlogn)
快速排序法最佳情況下執(zhí)行過程的遞歸樹如下圖所示，圖中l(wèi)gn表示以10為底的對數(shù)，而本文中用logn表示以2為底的對數(shù).
由于快速排序法也是基于比較的排序法，其運(yùn)行時間為Ω（nlogn)，所以如果每次劃分過程產(chǎn)生的區(qū)間大小都為n/2，則運(yùn)行時間θ（nlogn）就是最好情況運(yùn)行時間。
但是，是否一定要每次平均劃分才能達(dá)到最好情況呢？要理解這一點(diǎn)就必須理解對稱性是如何在描述運(yùn)行時間的遞歸式中反映的。我們假設(shè)每次劃分過程都產(chǎn)生9:1的劃分，乍一看該劃分很不對稱。我們可以得到遞歸式：
T(n)=T(n/10)+T(9n/10)+θ（n),T(1)=θ（1)(4)
請注意樹的每一層都有代價n，直到在深度log10n=θ（logn）處達(dá)到邊界條件，以后各層代價至多為n。遞歸于深度log10/9n=θ（logn）處結(jié)束。這樣，快速排序的總時間代價為T(n)=θ（nlogn），從漸進(jìn)意義上看就和劃分是在中間進(jìn)行的一樣。事實(shí)上，即使是99:1的劃分時間代價也為θ（nlogn）。其原因在于，任何一種按常數(shù)比例進(jìn)行劃分所產(chǎn)生的遞歸樹的深度都為θ（nlogn），其中每一層的代價為O(n），因而不管常數(shù)比例是什么，總的運(yùn)行時間都為θ（nlogn），只不過其中隱含的常數(shù)因子有所不同。（關(guān)于算法復(fù)雜性的漸進(jìn)階，請參閱算法的復(fù)雜性)

快速排序的平均運(yùn)行時間為θ(nlogn)。
我們對平均情況下的性能作直覺上的分析。
要想對快速排序的平均情況有個較為清楚的概念，我們就要對遇到的各種輸入作個假設(shè)。通常都假設(shè)輸入數(shù)據(jù)的所有排列都是等可能的。后文中我們要討論這個假設(shè)。
當(dāng)我們對一個隨機(jī)的輸入數(shù)組應(yīng)用快速排序時，要想在每一層上都有同樣的劃分是不太可能的。我們所能期望的是某些劃分較對稱，另一些則很不對稱。事實(shí)上，我們可以證明，如果選擇L[p..r]的第一個元素作為支點(diǎn)元素，Partition所產(chǎn)生的劃分80%以上都比9:1更對稱，而另20%則比9:1差，這里證明從略。
平均情況下，Partition產(chǎn)生的劃分中既有“好的”，又有“差的”。這時，與Partition執(zhí)行過程對應(yīng)的遞歸樹中，好、差劃分是隨機(jī)地分布在樹的各層上的。為與我們的直覺相一致，假設(shè)好、差劃分交替出現(xiàn)在樹的各層上，且好的劃分是最佳情況劃分，而差的劃分是最壞情況下的劃分。在根節(jié)點(diǎn)處，劃分的代價為n，劃分出來的兩個子表的大小為n-1和1，即最壞情況。在根的下一層，大小為n-1的子表按最佳情況劃分成大小各為（n-1)/2的兩個子表。這兒我們假設(shè)含1個元素的子表的邊界條件代價為1。
在一個差的劃分后接一個好的劃分后，產(chǎn)生出三個子表，大小各為1，（n-1)/2和（n-1)/2，代價共為2n-1=θ（n）。一層劃分就產(chǎn)生出大小為（n-1)/2+1和（n-1)/2的兩個子表，代價為n=θ（n）。這種劃分差不多是完全對稱的，比9:1的劃分要好。從直覺上看，差的劃分的代價θ（n）可被吸收到好的劃分的代價θ（n）中去，結(jié)果是一個好的劃分。這樣，當(dāng)好、差劃分交替分布劃分都是好的一樣：仍是θ（nlogn），但θ記號中隱含的常數(shù)因子要略大一些。關(guān)于平均情況的嚴(yán)格分析將在后文給出。
在前文從直覺上探討快速排序的平均性態(tài)過程中，我們已假定輸入數(shù)據(jù)的所有排列都是等可能的。如果輸入的分布滿足這個假設(shè)時，快速排序是對足夠大的輸入的理想選擇。但在實(shí)際應(yīng)用中，這個假設(shè)就不會總是成立。
解決的方法是，利用隨機(jī)化策略，能夠克服分布的等可能性假設(shè)所帶來的問題。
一種隨機(jī)化策略是：與對輸入的分布作“假設(shè)”不同的是對輸入的分布作“規(guī)定”。具體地說，在排序輸入的線性表前，對其元素加以隨機(jī)排列，以強(qiáng)制的方法使每種排列滿足等可能性。事實(shí)上，我們可以找到一個能在O(n）時間內(nèi)對含n個元素的數(shù)組加以隨機(jī)排列的算法。這種修改不改變算法的最壞情況運(yùn)行時間，但它卻使得運(yùn)行時間能夠獨(dú)立于輸入數(shù)據(jù)已排序的情況。
另一種隨機(jī)化策略是：利用前文介紹的選擇支點(diǎn)元素pivot的第四種方法，即隨機(jī)地在L[p..r]中選擇一個元素作為支點(diǎn)元素pivot。實(shí)際應(yīng)用中通常采用這種方法。
快速排序的隨機(jī)化版本有一個和其他隨機(jī)化算法一樣的有趣性質(zhì)：沒有一個特別的輸入會導(dǎo)致最壞情況性態(tài)。這種算法的最壞情況性態(tài)是由隨機(jī)數(shù)產(chǎn)生器決定的。你即使有意給出一個壞的輸入也沒用，因?yàn)殡S機(jī)化排列會使得輸入數(shù)據(jù)的次序?qū)λ惴ú划a(chǎn)生影響。只有在隨機(jī)數(shù)產(chǎn)生器給出了一個很不巧的排列時，隨機(jī)化算法的最壞情況性態(tài)才會出現(xiàn)。事實(shí)上可以證明幾乎所有的排列都可使快速排序接近平均情況性態(tài)，只有非常少的幾個排列才會導(dǎo)致算法的近最壞情況性態(tài)。
一般來說，當(dāng)一個算法可按多條路子做下去，但又很難決定哪一條保證是好的選擇時，隨機(jī)化策略是很有用的。如果大部分選擇都是好的，則隨機(jī)地選一個就行了。通常，一個算法在其執(zhí)行過程中要做很多選擇。如果一個好的選擇的獲益大于壞的選擇的代價，那么隨機(jī)地做一個選擇就能得到一個很有效的算法。我們在前文已經(jīng)了解到，對快速排序來說，一組好壞相雜的劃分仍能產(chǎn)生很好的運(yùn)行時間[2]。因此我們可以認(rèn)為該算法的隨機(jī)化版本也能具有較好的性態(tài)。

愛華網(wǎng)本文地址 » http://www.klfzs.com/a/8103370103/74833.html