原文出處： 寒江獨釣 歡迎分享原創(chuàng )到伯樂(lè )頭條
上篇文章介紹了時(shí)間復雜度為O(nlgn)的合并排序，本篇文章介紹時(shí)間復雜度同樣為O(nlgn)但是排序速度比合并排序更快的快速排序(Quick Sort)。
快速排序是20世紀科技領(lǐng)域的十大算法之一 ，他由C. A. R. Hoare于1960年提出的一種劃分交換排序。
快速排序也是一種采用分治法解決問(wèn)題的一個(gè)典型應用。在很多編程語(yǔ)言中，對數組，列表進(jìn)行的非穩定排序在內部實(shí)現中都使用的是快速排序。而且快速排序在面試中經(jīng)常會(huì )遇到。
本文首先介紹快速排序的思路，算法的實(shí)現、分析、優(yōu)化及改進(jìn)，最后分析了.NET 中列表排序的內部實(shí)現。
快速排序的基本思想如下：
如上圖所示快速排序的一個(gè)重要步驟是對序列進(jìn)行以中軸數進(jìn)行劃分，左邊都小于這個(gè)中軸數，右邊都大于該中軸數，然后對左右的子序列繼續這一步驟直到子序列長(cháng)度為1。
下面來(lái)看某一次劃分的步驟，如下圖：
上圖中的劃分操作可以分為以下5個(gè)步驟：
劃分過(guò)程的代碼實(shí)現如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | /// <summary>/// 快速排序中的劃分過(guò)程/// </summary>/// <param name="array">待劃分的數組</param>/// <param name="lo">最左側位置</param>/// <param name="hi">最右側位置</param>/// <returns>中間元素位置</returns>private static int Partition(T[] array, int lo, int hi){ int i = lo, j = hi + 1; while (true) { //從左至右掃描，如果碰到比基準元素array[lo]小，則該元素已經(jīng)位于正確的分區，i自增，繼續比較i+1； //否則，退出循環(huán)，準備交換 while (array[++i].CompareTo(array[lo]) < 0) { //如果掃描到了最右端，退出循環(huán) if (i == hi) break; } //從右自左掃描，如果碰到比基準元素array[lo]大，則該元素已經(jīng)位于正確的分區，j自減，繼續比較j-1 //否則，退出循環(huán)，準備交換 while (array[--j].CompareTo(array[lo]) > 0) { //如果掃描到了最左端，退出循環(huán) if (j == lo) break; } //如果相遇，退出循環(huán) if (i >= j) break; //交換左a[i],a[j]右兩個(gè)元素，交換完后他們都位于正確的分區 Swap(array, i, j); } //經(jīng)過(guò)相遇后，最后一次a[i]和a[j]的交換 //a[j]比a[lo]小，a[i]比a[lo]大，所以將基準元素與a[j]交換 Swap(array, lo, j); //返回掃描相遇的位置點(diǎn) return j;} |
劃分前后，元素在序列中的分布如下圖：
與合并算法基于合并這一過(guò)程一樣，快速排序基于分割(Partition)這一過(guò)程。只需要遞歸調用Partition這一操作，每一次以Partition返回的元素位置來(lái)劃分為左右兩個(gè)子序列，然后繼續這一過(guò)程直到子序列長(cháng)度為1，代碼的實(shí)現如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | public class QuickSort<T> where T : IComparable<T>{ public static void Sort(T[] array) { Sort(array, 0, array.Length - 1); } private static void Sort(T[] array, int lo, int hi) { //如果子序列為1，則直接返回 if (lo >= hi) return; //劃分，劃分完成之后，分為左右序列，左邊所有元素小于array[index]，右邊所有元素大于array[index] int index = Partition(array, lo, hi); //對左右子序列進(jìn)行排序完成之后，整個(gè)序列就有序了 //對左邊序列進(jìn)行遞歸排序 Sort(array, lo, index - 1); //對右邊序列進(jìn)行遞歸排序 Sort(array, index + 1, hi); }} |
下圖說(shuō)明了快速排序中，每一次劃分之后的結果：
一般快速排序的動(dòng)畫(huà)如下：
然后，對于N為N-1的情況：
兩式相減，然后整理得到：
然后左右兩邊同時(shí)除以N(N+1)，得到:
可以看到，這是一個(gè)遞歸式，我們將
然后處理一下得到：
對一般快速排序進(jìn)行一些改進(jìn)可以提高其效率。
1. 當劃分到較小的子序列時(shí)，通?？梢允褂貌迦肱判蛱娲焖倥判?/p>
對于較小的子序列（通常序列元素個(gè)數為10個(gè)左右），我們就可以采用插入排序直接進(jìn)行排序而不用繼續遞歸，算法改造如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | private const int CUTTOFF = 10;private static void Sort(T[] array, int lo, int hi){ //如果子序列為1，則直接返回 if (lo >= hi) return; //對于小序列，直接采用插入排序替代 if (hi - lo <= CUTTOFF - 1) { Sort<int>.InsertionSort(array, lo, hi); return; } //劃分，劃分完成之后，分為左右序列，左邊所有元素小于array[index]，右邊所有元素大于array[index] int index = Partition(array, lo, hi); //對左右子序列進(jìn)行排序完成之后，整個(gè)序列就有序了 //對左邊序列進(jìn)行遞歸排序 Sort(array, lo, index - 1); //對右邊序列進(jìn)行遞歸排序 Sort(array, index + 1, hi);} |
2. 三平均分區法(Median of three partitioning)
在一般的的快速排序中，選擇的是第一個(gè)元素作為中軸(pivot),這會(huì )出現某些分區嚴重不均的極端情況，比如劃分為了1和n-1兩個(gè)序列，從而導致出現最壞的情況。三平均分區法與一般的快速排序方法不同，它并不是選擇待排數組的第一個(gè)數作為中軸，而是選用待排數組最左邊、最右邊和最中間的三個(gè)元素的中間值作為中軸。這一改進(jìn)對于原來(lái)的快速排序算法來(lái)說(shuō)，主要有兩點(diǎn)優(yōu)勢：
（1） 首先，它使得最壞情況發(fā)生的幾率減小了。
（2） 其次，未改進(jìn)的快速排序算法為了防止比較時(shí)數組越界，在最后要設置一個(gè)哨點(diǎn)。如果在分區排序時(shí)，中間的這個(gè)元素（也即中軸）是與最右邊數過(guò)來(lái)第二個(gè)元素進(jìn)行交換的話(huà)，那么就可以省略與這一哨點(diǎn)值的比較。
對于三平均分區法還可以進(jìn)一步擴展，在選取中軸值時(shí)，可以從由左中右三個(gè)中選取擴大到五個(gè)元素中或者更多元素中選取，一般的，會(huì )有（2t＋1）平均分區法（median-of-(2t+1)。常用的一個(gè)改進(jìn)是，當序列元素小于某個(gè)閾值N時(shí)，采用三平均分區，當大于時(shí)采用5平均分區。
采用三平均分區法對快速排序的改進(jìn)如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | private static void Sort(T[] array, int lo, int hi){ //對于小序列，直接采用插入排序替代 if (hi - lo <= CUTTOFF - 1) { //Sort<int>.InsertionSort(array, lo, hi); return; } //采用三平均分區法查找中軸 int m = MedianOf3(array, lo, lo + (hi - lo) / 2, hi); Swap(array, lo, m); //劃分，劃分完成之后，分為左右序列，左邊所有元素小于array[index]，右邊所有元素大于array[index] int index = Partition(array, lo, hi); //對左右子序列進(jìn)行排序完成之后，整個(gè)序列就有序了 //對左邊序列進(jìn)行遞歸排序 Sort(array, lo, index - 1); //對右邊序列進(jìn)行遞歸排序 Sort(array, index + 1, hi);}/// <summary>/// 查找三個(gè)元素中位于中間的那個(gè)元素/// </summary>/// <param name="array"></param>/// <param name="lo"></param>/// <param name="center"></param>/// <param name="hi"></param>/// <returns></returns>private static int MedianOf3(T[] array, int lo, int center, int hi){ return (Less(array[lo], array[center]) ? (Less(array[center], array[hi]) ? center : Less(array[lo], array[hi]) ? hi : lo) : (Less(array[hi], array[center]) ? center : Less(array[hi], array[lo]) ? hi : lo));}private static bool Less(T t1, T t2){ return t1.CompareTo(t2) < 0;} |
使用插入排序對小序列進(jìn)行排序以及使用三平均分區法對一般快速排序進(jìn)行改進(jìn)后運行結果示意圖如下：
3. 三分區(3-way partitioning) 快速排序
通常，我們的待排序的序列關(guān)鍵字中會(huì )有很多重復的值，比如我們想對所有的學(xué)生按照年齡進(jìn)行排序，按照性別進(jìn)行排序等，這樣每一類(lèi)別中會(huì )有很多的重復的值。理論上，這些重復的值只需要處理一次就行了。但是一般的快速排序會(huì )遞歸進(jìn)行劃分，因為一般的快速排序只是將序列劃分為了兩部分，小于或者大于等于這兩部分。
既然要利用連續、相等的元素不需要再參與排序這個(gè)事實(shí)，一個(gè)直接的想法就是通過(guò)劃分讓相等的元素連續地擺放：
然后只對左側小于V的序列和右側大于V對的序列進(jìn)行排序。這種三路劃分與計算機科學(xué)中無(wú)處不在，它與Dijkstra提出的“荷蘭國旗問(wèn)題”(The Dutch National Flag Problem)非常相似。
Dijkstra的方法如上圖：
從左至右掃描數組，維護一個(gè)指針lt使得[lo…lt-1]中的元素都比v小，一個(gè)指針gt使得所有[gt+1….hi]的元素都大于v，以及一個(gè)指針i，使得所有[lt…i-1]的元素都和v相等。元素[i…gt]之間是還沒(méi)有處理到的元素，i從lo開(kāi)始，從左至右開(kāi)始掃描：
· 如果a[i]<v: 交換a[lt]和a[i],lt和i自增
· 如果a[i]>v:交換a[i]和a[gt], gt自減
· 如果a[i]=v: i自增
下面是使用Dijkstra的三分區快速排序代碼：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | private static void Sort(T[] array, int lo, int hi){ //對于小序列，直接采用插入排序替代 if (hi - lo <= CUTTOFF - 1) { Sort<int>.InsertionSort(array, lo, hi); return; } //三分區 int lt = lo, i = lo + 1, gt = hi; T v = array[lo]; while (i<=gt) { int cmp = array[i].CompareTo(v); if (cmp < 0) Swap(array, lt++, i++); else if (cmp > 0) Swap(array, i, gt--); else i++; } //對左邊序列進(jìn)行遞歸排序 Sort(array, lo, lt - 1); //對右邊序列進(jìn)行遞歸排序 Sort(array, gt + 1, hi);} |
三分區快速排序的每一步如下圖所示：
三分區快速排序的示意圖如下：
Dijkstra的三分區快速排序雖然在快速排序發(fā)現不久后就提出來(lái)了，但是對于序列中重復值不多的情況下，它比傳統的2分區快速排序需要更多的交換次數。
Bentley 和D. McIlroy在普通的三分區快速排序的基礎上，對一般的快速排序進(jìn)行了改進(jìn)。在劃分過(guò)程中，i遇到的與v相等的元素交換到最左邊，j遇到的與v相等的元素交換到最右邊，i與j相遇后再把數組兩端與v相等的元素交換到中間
這個(gè)方法不能完全滿(mǎn)足只掃描一次的要求，但它有兩個(gè)好處：首先，如果數據中沒(méi)有重復的值，那么該方法幾乎沒(méi)有額外的開(kāi)銷(xiāo)；其次，如果有重復值，那么這些重復的值不會(huì )參與下一趟排序，減少了無(wú)用的劃分。
下面是采用 Bentley&D. McIlroy 三分區快速排序的算法改進(jìn)：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | private static void Sort(T[] array, int lo, int hi){ //對于小序列，直接采用插入排序替代 if (hi - lo <= CUTTOFF - 1) { Sort<int>.InsertionSort(array, lo, hi); return; } // Bentley-McIlroy 3-way partitioning int i = lo, j = hi + 1; int p = lo, q = hi + 1; T v = array[lo]; while (true) { while (Less(array[++i], v)) if (i == hi) break; while (Less(v, array[--j])) if (j == lo) break; // pointers cross if (i == j && Equal(array[i], v)) Swap(array, ++p, i); if (i >= j) break; Swap(array, i, j); if (Equal(array[i], v)) Swap(array, ++p, i); if (Equal(array[j], v)) Swap(array, --q, j); } //將相等的元素交換到中間 i = j + 1; for (int k = lo; k <= p; k++) Swap(array, k, j--); for (int k = hi; k >= q; k--) Swap(array, k, i++); Sort(array, lo, j); Sort(array, i, hi);} |
三分區快速排序的動(dòng)畫(huà)如下：
4.并行化
和前面討論對合并排序的改進(jìn)一樣，對所有使用分治法解決問(wèn)題的算法其實(shí)都可以進(jìn)行并行化，快速排序的并行化改進(jìn)我在之前的淺談并發(fā)與并行這篇文章中已經(jīng)有過(guò)介紹，這里不再贅述。
快速排序作為一種優(yōu)秀的排序算法，在很多編程語(yǔ)言的元素內部排序中均有實(shí)現，比如Java中對基本數據類(lèi)型(primitive type)的排序,C++，Matlab，Python，FireFox Javascript等語(yǔ)言中均將快速排序作為其內部元素排序的算法。同樣.NET中亦是如此。
.NET這種對List<T>數組元素進(jìn)行排序是通過(guò)調用Sort方法實(shí)現的，其內部則又是通過(guò)Array.Sort實(shí)現，MSDN上說(shuō)在.NET 4.0及之前的版本，Array.Sort采用的是快速排序，然而在.NET 4.5中，則對這一算法進(jìn)行了改進(jìn)，采用了名為Introspective sort 的算法，即保證在一般情況下達到最快排序速度，又能保證能夠在出現最差情況是進(jìn)行優(yōu)化。他其實(shí)是一種混合算法：
有了Reflector這一神器，我們可以查看.NET中的ArraySort的具體實(shí)現:
Array.Sort這一方法在mscorlib這一程序集中，具體的實(shí)現方法有分別針對泛型和普通類(lèi)型的SortedGenericArray和SortedObjectArray，里面的實(shí)現大同小異，我們以SortedGenericArray這個(gè)類(lèi)來(lái)作為例子看:
首先要看的是Sort方法，其實(shí)現如下：
該方法中，首先判斷運行的.NET對的版本，如果是4.5及以上版本，則用IntrospectiveSort算法，否則采用限定深度的快速排序算法DepthLimitedQuickSort。先看IntrospectiveSort：
該方法第一個(gè)元素為數組的最左邊元素位置，第二個(gè)參數為最右邊元素位置，第三個(gè)參數為2*log2N，繼續看方法內部：
可以看到，當num<=16時(shí)，如果元素個(gè)數為1,2,3，則直接調用SwapIfGreaterWithItem進(jìn)行排序了。否則直接調用InsertSort進(jìn)行插入排序。
這里面也是一個(gè)循環(huán)，每循環(huán)一下depthLimit就減小1個(gè)，如果為0表示劃分的次數超過(guò)了2logN，則直接調用基排序(HeapSort)，這里面的劃分方法PickPivortAndPartitin的實(shí)現如下：
它其實(shí)是一個(gè)標準的三平均快速排序?？梢钥吹皆?NET 4.5中對Quick進(jìn)行優(yōu)化的部分主要是在元素個(gè)數比較少的時(shí)候采用選擇插入，并且在遞歸深度超過(guò)2logN的時(shí)候，采用基排序。
下面再來(lái)看下在.NET 4.0及以下平臺下排序DepthLimitedQuickSort方法的實(shí)現：
從名稱(chēng)中可以看出這是限定深度的快速排序，在第三個(gè)參數傳進(jìn)去的是0×20，也就是32。
可以看到，當劃分的次數大于固定的32次的時(shí)候，采用了基排序，其他的部分是普通的快速排序。
由于快速排序在排序算法中具有排序速度快，而且是就地排序等優(yōu)點(diǎn)，使得在許多編程語(yǔ)言的內部元素排序實(shí)現中采用的就是快速排序，本問(wèn)首先介紹了一般的快速排序，分析了快速排序的時(shí)間復雜度，然后就分析了對快速排序的幾點(diǎn)改進(jìn)，包括對小序列采用插入排序替代，三平均劃分，三分區劃分等改進(jìn)方法。最后介紹了.NET不同版本下的對元素內部排序的實(shí)現。
快速排序很重要，希望本文對您了解快速排序有所幫助。
聯(lián)系客服
