本文首發於：
微信公眾號：後端技術指南針
持續乾貨 歡迎關注！
看似青銅實則王者
很多人提起快排和二分都覺得很容易的樣子，但是讓現場Code很多就翻車了，就算可以寫出個遞歸版本的代碼，但是對其中的複雜度分析、邊界條件的考慮、非遞歸改造、代碼優化等就無從下手，填鴨背誦基本上分分鐘就被面試官擺平了。
那年初識快速排序
快速排序Quicksort又稱劃分交換排序partition-exchange sort，簡稱快排，一種排序算法。最早由東尼·霍爾(C. A. R. Hoare)教授在1960年左右提出，在平均狀況下，排序n個項目要O(nlogn)次比較。
在最壞狀況下則需要O(n^2)次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他算法更快，因為它的內部循環可以在大部分的架構上很有效率地達成。
快速排序的核心思想
在計算機科學中，分治法(Divide&Conquer)是建基於多項分支遞歸的一種很重要的算法範式，快速排序是分治思想在排序問題上的典型應用。
所謂分治思想D&C就是把一個較大規模的問題拆分為若干小規模且相似的問題。再對小規模問題進行求解，最終合併所有小問題的解，從而形成原來大規模問題的解。
字面上的解釋是”分而治之”，這個技巧是很多高效算法的基礎，如排序算法（歸併排序、快速排序）、傅立恭弘=叶 恭弘變換（快速傅立恭弘=叶 恭弘變換）。
分治法中最重要的部分是循環遞歸的過程，每一層遞歸有三個具體步驟：
- 分解：將原問題分解為若干個規模較小，相對獨立，與原問題形式相同的子問題。
- 解決：若子問題規模較小且易於解決時，則直接解。否則，遞歸地解決各子問題。
- 合併：將各子問題的解合併為原問題的解。
快速排序的發明者
查爾斯·安東尼·理查德·霍爾爵士(Sir Charles Antony Richard Hoare縮寫為C. A. R. Hoare，1934年1月11日－），昵稱為東尼·霍爾(Tony Hoare)，生於大英帝國錫蘭可倫坡（今斯里蘭卡），英國計算機科學家，圖靈獎得主。
他設計了快速排序算法、霍爾邏輯、交談循序程式。在操作系統中，他提出哲學家就餐問題，併發明用來作為同步程序的監視器（Monitors）以解決這個問題。他同時證明了監視器與信號標（Semaphore）在邏輯上是等價的。
1980年獲頒圖靈獎、1982年成為英國皇家學會院士、2000年因為他在計算機科學與教育方面的傑出貢獻，獲得英國王室頒贈爵士頭銜、2011年獲頒約翰·馮諾依曼獎，現為牛津大學榮譽教授，並在劍橋微軟研究院擔任研究員。
快速排序的基本過程
快速排序使用分治法來把一個序列分為小於基準值和大於基準值的兩個子序列。
遞歸地排序兩個子序列，直至最小的子序列長度為0或者1，整個遞歸過程結束，詳細步驟為：
- 挑選基準值: 從數列中挑出一個元素稱為基準pivot，選取基準值有數種具體方法，此選取方法對排序的時間性能有決定性影響。
- 基準值分割: 重新排序數列，所有比基準值小的元素擺放在基準前面,所有比基準值大的元素擺在基準後面，與基準值相等的數可以到任何一邊,在這個分割結束之後，對基準值的排序就已經完成。
- 遞歸子序列: 遞歸地將小於基準值元素的子序列和大於基準值元素的子序列排序，步驟同上兩步驟,遞歸終止條件是序列大小是0或1，因為此時該數列顯然已經有序。
快速排序的遞歸實現
- 版本一 C實現
#include<stdio.h> int a[9]={5,1,9,6,7,11,3,8,4}; void exchange(int *p,int *q){ int temp=*p; *p=*q; *q=temp; } int quicksort(int left,int right){ if(left>=right){ return 0; } int i,j,temp; temp=a[left]; i=left; j=right; while(i!=j){ while(i<j&&a[j]>=temp){ j--; } exchange(&a[i],&a[j]); while(i<j&&a[i]<=temp){ i++; } exchange(&a[i],&a[j]); } quicksort(i+1,right); quicksort(left,i-1); } int main(){ quicksort(0,8); for(int i=0;i<=8;i++){ printf("%d ",a[i]); } }
- 版本二 C++實現
1 #include<iostream> 2 using namespace std; 3 4 template <typename T> 5 void quick_sort_recursive(T arr[], int start, int end) { 6 if (start >= end) 7 return; 8 T mid = arr[end]; 9 int left = start, right = end - 1; 10 //整個範圍內搜尋比樞紐值小或大的元素，然後左側元素與右側元素交換 11 while (left < right) { 12 //試圖在左側找到一個比樞紐元更大的元素 13 while (arr[left] < mid && left < right) 14 left++; 15 //試圖在右側找到一個比樞紐元更小的元素 16 while (arr[right] >= mid && left < right) 17 right--; 18 //交換元素 19 std::swap(arr[left], arr[right]); 20 } 21 //這一步很關鍵 22 if (arr[left] >= arr[end]) 23 std::swap(arr[left], arr[end]); 24 else 25 left++; 26 quick_sort_recursive(arr, start, left - 1); 27 quick_sort_recursive(arr, left + 1, end); 28 } 29 30 //模板化 31 template <typename T> 32 void quick_sort(T arr[], int len) { 33 quick_sort_recursive(arr, 0, len - 1); 34 } 35 36 int main() 37 { 38 int a[9]={5,1,9,6,7,11,3,8,4}; 39 int len = sizeof(a)/sizeof(int); 40 quick_sort(a,len-1); 41 for(int i=0;i<len-1;i++) 42 cout<<a[i]<<endl; 43 }
兩個版本均可正確運行，但代碼有一點差異:
- 版本一 使用雙指針交替從左(右)兩邊分別開始尋找大於基準值(小於基準值)，然後與基準值交換，直到最後左右指針相遇。
- 版本二 使用雙指針向中間集合，左指針遇到大於基準值時則停止，等待右指針，右指針遇到小於基準值時則停止，與左指針指向的元素交換，最後基準值放到合適位置。
過程說起來比較抽象，穩住別慌！靈魂畫手大白會畫圖來演示這兩個過程。
快速排序的遞歸演示
- 版本一遞歸代碼的排序過程示意圖：
以第一次遞歸循環為例:
步驟1: 選擇第一個元素為基準值pivot=a[left]=5,right指針指向尾部元素，此時先由right自右向左掃描直至遇到<5的元素，恰好right起步元素4<5，因此需要將4與5互換位置；
步驟2: 4與5互換位置之後，輪到left指針從左向右掃描，注意一下left的起步指針指向了由步驟1交換而來的4，新元素4不滿足停止條件，因此left由綠色虛箭頭4位置遊走到元素9的位置，此時left找到9>5，因此將此時left和right指向的元素互換，也就是元素5和元素9互換位置；
步驟3: 互換之後right指針繼續向左掃描，從藍色虛箭頭9位置遊走到3的位置，此時right發現3<5，因此將此時left和right指向的元素互換，也就是元素3和元素5互換位置；
步驟4: 互換之後left指針繼續向右掃描，從綠色虛箭頭3位置遊走到6的位置，此時left發現6>5，因此將此時left和right指向的元素互換，也就是元素6和元素5互換位置；
步驟5: 互換之後right指針繼續向左掃描，從藍色虛箭頭6位置一直遊走到與left指針相遇，此時二者均停留在了pivot=5的新位置上，且左右兩邊分成了兩個相對於pivot值的子序列；
循環結束：至此出現了以5為基準值的左右子序列，接下來就是對兩個子序列實施同樣的遞歸步驟。
以第二次和第三次左子序列遞歸循環為例:
步驟1-1：選擇第一個元素為基準值pivot=a[left]=4，right指針指向尾部元素，此時先由right指針向左掃描，恰好起步元素3<4，因此將3和4互換；
步驟1-2：互換之後left指針從元素3開始向右掃描，一直遊走到與right指針相遇，此時本次循環停止，特別注意這種情況下可以看到基準值4隻有左子序列，無右子序列，這種情況是一種退化，就像冒泡排序每次循環都將基準值放置到最後，因此效率將退化為冒泡的O(n^2);
步驟1-3：選擇第一個元素為基準值pivot=a[left]=3，right指針指向尾部元素，此時先由right指針向左掃描，恰好起步元素1<3，因此將1和3互換；
步驟1-4：互換之後left指針從1開始向右掃描直到與right指針相遇，此時注意到pivot=3無右子序列且左子序列len=1，達到了遞歸循環的終止條件，此時可以認為由第一次循環產生的左子序列已經全部有序。
循環結束：至此左子序列已經排序完成，接下來對右子序列實施同樣的遞歸步驟，就不再演示了，聰明的你一定get到了。
特別注意:
以上過程中left和right指針在某個元素相遇，這種情況在代碼中是不會出現的，因為外層限制了i!=j，圖中之所以放到一起是為了直觀表達終止條件。
- 版本二C++版本動畫演示：
分析一下:
個人覺得這個版本雖然同樣使用D&C思想但是更加簡潔，從動畫可以看到選擇pivot=a[end]，然後左右指針分別從index=0和index=end-1向中間靠攏。
過程中掃描目標值並左右交換，再繼續向中間靠攏，直到相遇，此時再根據a[left]和a[right]以及pivot的值來進行合理置換，最終實現基於pivot的左右子序列形式。
腦補場景:
上述過程讓我覺得很像統帥命令左右兩路軍隊從兩翼會和，並且在會和過程中消滅敵人有生力量(認為是交換元素)，直到兩路大軍會師。
此時再將統帥王座擺到正確的位置，此過程中沒有統帥王座的反覆變換，只有最終會師的位置，以王座位中心形成了左翼子序列和右翼子序列。
再重複相同的過程，直至完成大一統。
腦補不過癮 於是湊圖一張:
快速排序的多種版本
吃瓜時間：
印象中2017年初換工作的時候去CBD一家公司面試手寫快排，我就使用C++模板化的版本二實現的，但是面試官質疑說這不是快排，爭辯之下讓我們彼此都覺得對方很Low，於是很快就把我送出門SayGoodBye了^_^。
我想表達的意思是，雖然快排的遞歸版本是基於D&C實現的，但是由於pivot值的選擇不同、交換方式不同等諸多因素，造成了多種版本的遞歸代碼。
並且內層while循環裏面判斷>=還是>(即是否等於的問題)，外層循環判斷本序列循環終止條件等寫法都會不同，因此在寫快排時切忌死記硬背，要不然邊界條件判斷不清楚很容易就死循環了。
看下上述我貼的兩個版本的代碼核心部分：
//版本一寫法 while(i!=j){ while(i<j&&a[j]>=temp){ j--; } exchange(&a[i],&a[j]); while(i<j&&a[i]<=temp){ i++; } exchange(&a[i],&a[j]); } //版本二寫法 while (left < right) { while (arr[left] < mid && left < right) left++; while (arr[right] >= mid && left < right) right--; std::swap(arr[left], arr[right]); }
覆蓋or交換:
代碼中首先將pivot的值引入局部變量保存下來，這樣就認為A[L]這個位置是個坑，可以被其他元素覆蓋，最終再將pivot的值填到最後的坑裡。
這種做法也沒有問題，因為你只要畫圖就可以看到，每次坑的位置是有相同元素的位置，也就是被備份了的元素。
個人感覺 與其叫坑不如叫備份，但是如果你代碼使用的是基於指針或者引用的swap，那麼就沒有坑的概念了。
這就是覆蓋和交換的區別，本文的例子都是swap實現的，因此沒有坑位被最後覆蓋一次的過程。
快速排序的迭代實現
所謂迭代實現就是非遞歸實現一般使用循環來實現，我們都知道遞歸的實現主要是藉助系統內的棧來實現的。
如果調用層級過深需要保存的臨時結果和關係會非常多，進而造成StackOverflow棧溢出。
Stack一般是系統分配空間有限內存連續速度很快，每個系統架構默認的棧大小不一樣，筆者在x86-CentOS7.x版本使用ulimit -s查看是8192Byte。
避免棧溢出的一種辦法是使用循環，以下為筆者驗證的使用STL的stack來實現的循環版本，代碼如下：
#include <stack> #include <iostream> using namespace std; template<typename T> void qsort(T lst[], int length) { std::stack<std::pair<int, int> > mystack; //將數組的首尾下標存儲 相當於第一輪循環 mystack.push(make_pair(0, length - 1)); while (!mystack.empty()) { //使用棧頂元素而後彈出 std::pair<int,int> top = mystack.top(); mystack.pop(); //獲取當前需要處理的子序列的左右下標 int i = top.first; int j = top.second; //選取基準值 T pivot = lst[i]; //使用覆蓋填坑法 而不是交換哦 while (i < j) { while (i < j and lst[j] >= pivot) j--; lst[i] = lst[j]; while (i < j and lst[i] <= pivot) i++; lst[j] = lst[i]; } //注意這個基準值回填過程 lst[i] = pivot; //向下一個子序列進發 if (i > top.first) mystack.push(make_pair(top.first, i - 1)); if (j < top.second) mystack.push(make_pair(j + 1, top.second)); } } int main() { int a[9]={5,1,9,6,7,11,3,8,4}; int len = sizeof(a)/sizeof(int); qsort(a,len); for(int i=0;i<len-1;i++) cout<<a[i]<<endl; }
下期精彩
由於篇幅原因，目前文章已經近6000字，因此筆者決定將快排算法的優化放到另外一篇文章中，不過可以提前預告一下會有哪些內容：
- 基準值選擇對性能的影響
- 基準值選擇的多種策略
- 尾遞歸的概念原理和優勢
- 基於尾遞歸實現快速排序
- STL中sort函數的底層實現
- glibc中快速排序的實現
參考資料
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】
※USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能
※高價3c回收,收購空拍機,收購鏡頭,收購 MACBOOK-更多收購平台討論專區
※評比前十大台北網頁設計、台北網站設計公司知名案例作品心得分享
※收購3c瘋!各款手機、筆電、相機、平板,歡迎來詢價!
※智慧手機時代的來臨，RWD網頁設計已成為網頁設計推薦首選