看似青銅實則王者

很多人提起快排和二分都覺得很容易的樣子，但是讓現場Code很多就翻車了，就算可以寫出個遞歸版本的代碼，但是對其中的復雜度分析、邊界條件的考慮、非遞歸改造、代碼優化等就無從下手，填鴨背誦基本上分分鐘就被面試官擺平了。

那年初識快速排序

快速排序Quicksort又稱劃分交換排序partition-exchange sort，簡稱快排，一種排序算法。最早由東尼·霍爾(C. A. R. Hoare)教授在1960年左右提出，在平均狀況下，排序n個項目要O(nlogn)次比較。
在最壞狀況下則需要O(n^2)次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他算法更快，因為它的內部循環可以在大部分的架構上很有效率地達成。

快速排序的核心思想

在計算機科學中，分治法(Divide&Conquer)是建基于多項分支遞歸的一種很重要的算法范式，快速排序是分治思想在排序問題上的典型應用。

所謂分治思想D&C就是把一個較大規模的問題拆分為若干小規模且相似的問題。再對小規模問題進行求解，最終合并所有小問題的解，從而形成原來大規模問題的解。

字面上的解釋是"分而治之"，這個技巧是很多高效算法的基礎，如排序算法（歸并排序、快速排序）、傅立葉變換（快速傅立葉變換）。

分治法中最重要的部分是循環遞歸的過程，每一層遞歸有三個具體步驟：

分解：將原問題分解為若干個規模較小，相對獨立，與原問題形式相同的子問題。
解決：若子問題規模較小且易于解決時，則直接解。否則，遞歸地解決各子問題。
合并：將各子問題的解合并為原問題的解。

快速排序的基本過程

快速排序使用分治法來把一個序列分為小于基準值和大于基準值的兩個子序列。

遞歸地排序兩個子序列，直至最小的子序列長度為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++實現

#include<IOStream>
using namespace std;

template <typename T>
void quick_sort_recursive(T arr[], int start, int end) {
 if (start >= end)
 return;
 T mid = arr[end];
 int left = start, right = end - 1;
 //整個范圍內搜尋比樞紐值小或大的元素，然后左側元素與右側元素交換
 while (left < right) {
 //試圖在左側找到一個比樞紐元更大的元素
 while (arr[left] < mid && left < right)
 left++;
 //試圖在右側找到一個比樞紐元更小的元素
 while (arr[right] >= mid && left < right)
 right--;
 //交換元素
 std::swap(arr[left], arr[right]);
 }
 //這一步很關鍵
 if (arr[left] >= arr[end])
 std::swap(arr[left], arr[end]);
 else
 left++;
 quick_sort_recursive(arr, start, left - 1);
 quick_sort_recursive(arr, left + 1, end);
}

//模板化
template <typename T> 
void quick_sort(T arr[], int len) {
 quick_sort_recursive(arr, 0, len - 1);
}

int main()
{
 int a[9]={5,1,9,6,7,11,3,8,4};
 int len = sizeof(a)/sizeof(int);
 quick_sort(a,len-1);
 for(int i=0;i<len-1;i++)
 cout<<a[i]<<endl;
}

兩個版本均可正確運行，但代碼有一點差異:

版本一使用雙指針交替從左(右)兩邊分別開始尋找大于基準值(小于基準值)，然后與基準值交換，直到最后左右指針相遇。
版本二使用雙指針向中間集合，左指針遇到大于基準值時則停止，等待右指針，右指針遇到小于基準值時則停止，與左指針指向的元素交換，最后基準值放到合適位置。

過程說起來比較抽象，穩住別慌！靈魂畫手大白會畫圖來演示這兩個過程。

快速排序的遞歸演示

版本一遞歸代碼的排序過程示意圖：

以第一次遞歸循環為例:

步驟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;
}