快速排序深度优化详解
正如它的名字所體現(xiàn)，快速排序是在實踐中最快的已知排序算法，平均運行時間為O(NlogN)，最壞的運行時間為O(N^2)。算法的基本思想很簡單，然而想要寫出一個高效的快速排序算法并不是那么簡單。基準(zhǔn)的選擇，元素的分割等都至關(guān)重要，如果你不清楚如何優(yōu)化快速排序算法，本文你不該錯過。
算法思想
快速排序利用了分治的策略。而分治的基本基本思想是：將原問題劃分為若干與原問題類似子問題，解決這些子問題，將子問題的解組成原問題的解。
那么如何利用分治的思想對數(shù)據(jù)進行排序呢？假如有一個元素集合A：
- 選擇A中的任意一個元素pivot，該元素作為基準(zhǔn)
- 將小于基準(zhǔn)的元素移到左邊，大于基準(zhǔn)的元素移到右邊（分區(qū)操作）
- A被pivot分為兩部分，繼續(xù)對剩下的兩部分做同樣的處理
- 直到所有子集元素不再需要進行上述步驟
可以看到算法思想比較簡單，然而上述步驟實際又該如何處理呢？
如何選擇基準(zhǔn)
實際上無論怎么選擇基準(zhǔn)，都不會影響排序結(jié)果，但是不同的選擇卻可能影響整體排序時間，因為基準(zhǔn)選擇不同，會導(dǎo)致分割的兩個集合大小不同，如果分割之后，兩個集合大小是幾乎相等的，那么我們整體分割的次數(shù)顯然也會減少，這樣整體耗費的時間也相應(yīng)降低。我們來看一下有哪些可選擇策略。
選擇第一個或者最后一個
如果待排序數(shù)是隨機的，那么選擇第一個或者最后一個作基準(zhǔn)是沒有什么問題的，這也是我們最常見到的選擇方案。但如果待排序數(shù)據(jù)已經(jīng)排好序的，就會產(chǎn)生一個很糟糕的分割。幾乎所有的數(shù)據(jù)都被分割到一個集合中，而另一個集合沒有數(shù)據(jù)。這樣的情況下，時間花費了，卻沒有做太多實事。而它的時間復(fù)雜度就是最差的情況O(N^2)。因此這種策略是絕對不推薦的。
隨機選擇
隨機選擇基準(zhǔn)是一種比較安全的做法。因為它不會總是產(chǎn)生劣質(zhì)的分割。
C語言實現(xiàn)參考：
選擇三數(shù)中值
從前面的描述我們知道，如果能夠選擇到數(shù)據(jù)的中值，那是最好的，因為它能夠?qū)⒓辖醯确譃槎５呛芏鄷r候很難算出中值，并且會耗費計算時間。因此我們隨機選取三個元素，并用它們的中值作為整個數(shù)據(jù)中值的估計值。在這里，我們選擇最左端，最右端和中間位置的三個元素的中值作為基準(zhǔn)。
假如有以下數(shù)組：
1 9 10 3 8 7 6 2 4左端元素為1，位置為0，右端元素為4，位置為8，則中間位置為[0+8]/2=4，中間元素為8。那么三數(shù)中值就為4（1，4，8的中值）。
如何將元素移動到基準(zhǔn)兩側(cè)
選好基準(zhǔn)之后，如何將元素移動到基準(zhǔn)兩側(cè)呢？通常的做法如下：
- 將基準(zhǔn)元素與最后的元素交換，使得基準(zhǔn)元素不在被分割的數(shù)據(jù)范圍
- i和j分別從第一個元素和倒數(shù)第二個元素開始。i在j的左邊時，將i右移，直到發(fā)現(xiàn)大于等于基準(zhǔn)的元素，然后將j左移，直到發(fā)現(xiàn)小于等于基準(zhǔn)的元素。i和j停止時，元素互換。這樣就把大于等于基準(zhǔn)的移到了右邊，小于等于基準(zhǔn)的移到了左邊
- 重復(fù)上面的步驟，直到i和j交錯
- 將基準(zhǔn)元素與i所指向的元素交換，使得基準(zhǔn)元素將整個元素集合分割為小于基準(zhǔn)和大于基準(zhǔn)的元素集合
在們采用三數(shù)中值得方法選擇基準(zhǔn)的情況下，既然基準(zhǔn)是中值，實際上只要保證左端，右端，中間值是從小到大即可。還是以前面提到的數(shù)組為例，我們找到三者后，對三者進行排序如下：
排序前
| 1 | 9 | 10 | 3 | 8 | 7 | 6 | 2 | 4 |
排序后
| 1 | 9 | 10 | 3 | 4 | 7 | 6 | 2 | 8 |
如果是這樣的情況，那么實際上不需要把基準(zhǔn)元素和最后一個元素交換，而只需要和倒數(shù)第二個元素交換即可，因為最后一個元素肯定大于基準(zhǔn)，這樣可以減少交換次數(shù)。
如果前面的描述還不清楚，我們看一看實際中一趟完整的流程是什么樣的。
第一步，將左端，右端和中間值排序，中值作為基準(zhǔn)：
| 1 | 9 | 10 | 3 | 4 | 7 | 6 | 2 | 8 |
| 基準(zhǔn) |
第二步，將中值與倒數(shù)第二個數(shù)交換位置：
| ↓ | ↓ | |||||||
| 1 | 9 | 10 | 3 | 2 | 7 | 6 | 4 | 8 |
| 基準(zhǔn) |
第三步，i向右移動，直到發(fā)現(xiàn)大于等于基準(zhǔn)的元素9：
| 1 | 9 | 10 | 3 | 2 | 7 | 6 | 4 | 8 |
| ↑ | ↑ | ↑ | ||||||
| i | j | 基準(zhǔn) |
第四步，j向左移動，直到發(fā)現(xiàn)小于等于基準(zhǔn)的元素2：
| 1 | 9 | 10 | 3 | 2 | 7 | 6 | 4 | 8 |
| ↑ | ↑ | ↑ | ||||||
| i | j | 基準(zhǔn) |
第五步，交換i和j：
| 1 | 2 | 10 | 3 | 9 | 7 | 6 | 4 | 8 |
| ↑ | ↑ | ↑ | ||||||
| i | 交 | 換 | j | 基準(zhǔn) |
第六步，重復(fù)上述步驟，i右移，j左移：
| 1 | 2 | 10 | 3 | 9 | 7 | 6 | 4 | 8 |
| ↑ | ↑ | ↑ | ||||||
| i | j | 基準(zhǔn) |
第七步，交換i和j指向的值：
| 1 | 2 | 3 | 10 | 9 | 7 | 6 | 4 | 8 |
| ↑ | ↑ | ↑ | ||||||
| i | j | 基準(zhǔn) |
第八步，重復(fù)上述步驟，i右移，j左移，此時i和j已經(jīng)交錯：
| 1 | 2 | 3 | 10 | 9 | 7 | 6 | 4 | 8 |
| ↑ | ↑ | ↑ | ||||||
| j | i | 基準(zhǔn) |
第九步，i和j已經(jīng)交錯，因此最后將基準(zhǔn)元素與i所指元素交換：
| 1 | 2 | 3 | 4 | 9 | 7 | 6 | 10 | 8 |
| ↑ | ||||||||
| i |
到這一步的時候，我們發(fā)現(xiàn)i的左邊都是小于i指向的元素，而右邊都是大于i的元素。最后在對子集進行同樣的操作即可。
如何對子集進行排序
遞歸法
最常見的便是遞歸法了。遞歸的好處是代碼簡潔易懂，但是不可忽略的是，當(dāng)遞歸嵌套過深時，它的效率問題以及棧溢出的風(fēng)險可能會迫使你選擇非遞歸法。在前面對整個集合一分為二之后，對剩下的兩個集合遞歸調(diào)用，直到完成排序。簡單描述如下(非可運行代碼)：
void Qsort(int A[],int left,int right) {/*分區(qū)操作*/int i = partition(A,left,right);/*對子集遞歸調(diào)用*/Qsort(A,left,i-1);Qsort(A,i+1,right); }遞歸最需要注意的便是遞歸結(jié)束調(diào)用，否則會產(chǎn)生無限遞歸，從而發(fā)生棧溢出。
后面我們會看到，遞歸法的代碼非常簡潔。（相關(guān)閱讀《重新看遞歸》）
尾遞歸
在遞歸版本中，Qsort分別遞歸調(diào)用計算左右兩個子集合，而第二個遞歸其實并非必須，完全可以用循環(huán)來替代，以下代碼模擬實現(xiàn)了尾遞歸，（并非是真的尾遞歸）：
void Qsort(ElementType A[],int left,int right) {int i = 0;while(left < right){/*分割操作*/i = partition(A,left,right);/*遞歸調(diào)用*/Qsort(A,left,i-1);/*右半部分通過循環(huán)實現(xiàn)*/left = i + 1;} }非遞歸法
那么有沒有方法可以不用遞歸呢？既然遞歸每次都進行壓棧操作，那么我們能不能分區(qū)后僅僅將區(qū)間信息存儲到棧里，然后從棧中取出區(qū)間再繼續(xù)分區(qū)呢？顯然是可以的。實際上我們每次分區(qū)時，只需要知道區(qū)間即可，那么將這些區(qū)間信息存儲起來，就可以不用遞歸了，按照分好的區(qū)間不斷分區(qū)即可。
例如對于前面提到的數(shù)組，首先對區(qū)間[0,8]進行分區(qū)操作，之后得到兩個新的分區(qū)，1,2,3和9，7，6，10，8，假設(shè)兩個區(qū)間仍然可以使用快速排序，那么需要將區(qū)間[0,2]和[5,8]的其中一個壓棧，另一個繼續(xù)分區(qū)操作。
按照這種思路，代碼簡單描述如下（非可運行代碼）：
void Qsort(A,left,right) { while(STACK_IS_NOT_EMPTY){/*分區(qū)操作*/POP(lo,hi);int mid = partition(A,lo,hi);/*存儲新的邊界*/PUSH(lo,mid-1);PUSH(mid+1,hi);} }當(dāng)然這里面沒有體現(xiàn)分區(qū)終止條件。我們需要在數(shù)據(jù)量小于一定值的時候，就不再繼續(xù)進行分區(qū)操作了，而是選擇插入排序（為什么？）。
那么問題來了，如何選擇棧的大小呢？查看qsort.c的源碼發(fā)現(xiàn)，它選擇了如下的值：
#define STACK_SIZE (8* sizeof(unsigned long int));為什么會是這個值呢？設(shè)想一下，假設(shè)待排序數(shù)組長度使用unsigned long int來表示，并且假設(shè)每次都將集合分為二等分。那么即便數(shù)組長度達到最大值，實際上最多只需要分割8 *(sizeof(unsigned long int))次，也就將它分割完了。然而由于以下幾個原因，需要存儲在棧中的區(qū)間信息很難超出棧空間，因為：
- 數(shù)組長度不會接近unsigned long int，否則內(nèi)存也撐不住了
- 區(qū)間足夠小時，不采用快速排序
- 每做一個分區(qū)，只會增加一個區(qū)間PUSH到棧中，增長速度慢
注意事項
至此，快速排序所有的主要步驟已經(jīng)介紹完畢。但是有以下注意事項：
- 有大量重復(fù)元素時避免產(chǎn)生糟糕分區(qū)，因此在發(fā)現(xiàn)大于等于基準(zhǔn)或者小于等于基準(zhǔn)時，便停止掃描。
- 通常會將基準(zhǔn)一開始移動到最后位置或倒數(shù)第二個位置，避免基準(zhǔn)在待分區(qū)區(qū)間。
- 對于很小的數(shù)組（N<=20），插入排序要比快速排序更好。因為快速排序有遞歸開銷，并且插入排序是穩(wěn)定排序。
- 如果函數(shù)本身的局部變量很少，那么遞歸帶來的開銷也就越小；如果遞歸發(fā)生棧溢出了，首先需要排除代碼設(shè)計問題。因此如果你設(shè)計的非遞歸版本效率低于遞歸版本，也不要驚訝。
注：假定在待排序的記錄序列中，存在多個具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。–來自百科
遞歸版代碼實現(xiàn)
完整可運行代碼可訪問快速排序優(yōu)化詳解
C語言代碼部分實現(xiàn)如下：
尾遞歸版代碼實現(xiàn)
略。
非遞歸版代碼實現(xiàn)
非遞歸版與遞歸版大部分代碼相同，Qsort函數(shù)有所不同，并且增加棧相關(guān)內(nèi)容定義：
//公眾號：【編程珠璣】，博客：https://www.yanbinghu.com /*存儲區(qū)間信息*/ typedef struct stack_node_t {int lo;int hi; }struct_node; /*最大棧長度*/ #define STACK_SIZE 8 * sizeof(unsigned int)/*入棧，出棧*/ #define STACK_PUSH( low, hig ) ( (top->lo = low), (top->hi = hig), top++) #define STACK_POP( low, hig ) (top--, (low = top->lo), (hig = top->hi) )/*快速排序*/ void Qsort( ElementType A[], int left, int right ) {if(NULL == A)return;/*使用寄存器指針*/register ElementType *arr = A;if ( right - left >= MAX_THRESH ){struct_node stack[STACK_SIZE] = { { 0 } };register struct_node *top = stack;/*最大區(qū)間壓棧*/int lo = left;int hi = right;STACK_PUSH( 0, 0);int mid = 0;while ( stack < top ){/*出棧，取出一個區(qū)間進行分區(qū)操作*/mid = partition( arr, lo, hi );/*分情況處理，左邊小于閾值*/if ( (mid - 1 - lo) <= MAX_THRESH){/* 左右兩個數(shù)據(jù)段的元素都小于閾值，取出棧中數(shù)據(jù)段進行劃分*/if ( (hi - (mid+1)) <= MAX_THRESH)/* 都小于閾值，從棧中取出數(shù)據(jù)段 */STACK_POP (lo, hi);else/* 只有右邊大于閾值，右邊繼續(xù)分區(qū)*/lo = mid -1 ;}/*右邊小于閾值，繼續(xù)計算左邊*/else if ((hi - (mid+1)) <= MAX_THRESH)hi = mid - 1;/*左右兩邊都大于閾值，且左邊大于右邊，左邊入棧，右邊繼續(xù)分區(qū)*/else if ((mid -1 - lo) > (hi - (mid + 1))){STACK_PUSH (lo, mid - 1);lo = mid + 1;}/*左右兩邊都大于閾值，且右邊大于左邊，右邊入棧，左邊繼續(xù)分區(qū)*/else{STACK_PUSH (mid + 1, hi);hi = mid -1;}}}/*最后再使用插入排序，對于接近有序狀態(tài)的數(shù)據(jù)，插入排序速度很快*/insertSort(arr,right-left+1);}運行結(jié)果
我們隨機產(chǎn)生1億個整數(shù)，并對其進行排序：
$ gcc -o qsort qsort.c $ time ./qsort 100000000遞歸版運行結(jié)果：
sort for 100000000 numbers before sort:too much，will not print after sort:too much，will not printreal 0m16.753s user 0m16.623s sys 0m0.132s非遞歸版結(jié)果：
sort for 100000000 numbers before sort:too much，will not print after sort:too much，will not printreal 0m16.556s user 0m16.421s sys 0m0.137s可以看到，實際上兩種方法的效率差距并不是很大。至于原因，前面我們已經(jīng)說過了。
總結(jié)
本文所寫的示例實現(xiàn)與glibc的實現(xiàn)相比，還有很多可優(yōu)化的地方，例如，本文實現(xiàn)僅對int類型實現(xiàn)了排序或交換值，如果待排序內(nèi)容是其他類型，就顯得力不從心，讀者可參考《高級指針話題函數(shù)指針》思考如何實現(xiàn)對任意數(shù)據(jù)類型進行排序，。但快速排序的優(yōu)化主要從以下幾個方面考慮：
- 優(yōu)化基準(zhǔn)選擇
- 優(yōu)化小數(shù)組排序效率
- 優(yōu)化交換次數(shù)
- 優(yōu)化遞歸
- 優(yōu)化最差情況，避免糟糕分區(qū)
- 元素聚合
有興趣地也可以進一步閱讀qsort源碼，進一步了解其中喪心病狂的優(yōu)化。
思考
- 為什么要在遇到相同元素時就進行掃描？
- 插入排序最好的情況時間復(fù)雜度是多少，在什么情況下出現(xiàn)？
- 文中實現(xiàn)的代碼還有哪些可以優(yōu)化的地方？
練習(xí)
- 采用第一種基準(zhǔn)選擇策略實現(xiàn)快速排序，并測試對有序數(shù)組的排序性能
- 實現(xiàn)通用快速排序算法，參考《C語言函數(shù)指針》
參考
- 《數(shù)據(jù)結(jié)構(gòu)與算法分析》
- 《算法導(dǎo)論》
- glibc qsort.c源碼
最新內(nèi)容地址：快速排序優(yōu)化詳解
微信公眾號【編程珠璣】：專注但不限于分享計算機編程基礎(chǔ)，Linux，C語言，C++，算法，數(shù)據(jù)庫等編程相關(guān)[原創(chuàng)]技術(shù)文章，號內(nèi)包含大量經(jīng)典電子書和視頻學(xué)習(xí)資源。歡迎一起交流學(xué)習(xí)，一起修煉計算機“內(nèi)功”，知其然，更知其所以然。
總結(jié)
以上是生活随笔為你收集整理的快速排序深度优化详解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： [linux小水滴]工具安装与使用
- 下一篇： 用户画像 | 标签数据存储之Elasti