很多人提起快排和二分都覺得很容易的樣子，但是讓現(xiàn)場Code很多就翻車了，就算可以寫出個遞歸版本的代碼，但是對其中的復(fù)雜度分析、邊界條件的考慮、非遞歸改造、代碼優(yōu)化等就無從下手，填鴨背誦基本上分分鐘就被面試官擺平了。
快速排序Quicksort又稱劃分交換排序partition-exchange sort，簡稱快排，一種排序算法。最早由東尼·霍爾(C. A. R. Hoare)教授在1960年左右提出，在平均狀況下，排序n個項目要O(nlogn)次比較。
在最壞狀況下則需要O(n^2)次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他算法更快，因為它的內(nèi)部循環(huán)可以在大部分的架構(gòu)上很有效率地達(dá)成。
在計算機科學(xué)中，分治法(Divide&Conquer)是建基于多項分支遞歸的一種很重要的算法范式，快速排序是分治思想在排序問題上的典型應(yīng)用。
所謂分治思想D&C就是把一個較大規(guī)模的問題拆分為若干小規(guī)模且相似的問題。再對小規(guī)模問題進(jìn)行求解，最終合并所有小問題的解，從而形成原來大規(guī)模問題的解。
字面上的解釋是"分而治之"，這個技巧是很多高效算法的基礎(chǔ)，如排序算法（歸并排序、快速排序）、傅立葉變換（快速傅立葉變換）。
分治法中最重要的部分是循環(huán)遞歸的過程，每一層遞歸有三個具體步驟：
快速排序使用分治法來把一個序列分為小于基準(zhǔn)值和大于基準(zhǔn)值的兩個子序列。
遞歸地排序兩個子序列，直至最小的子序列長度為0或者1，整個遞歸過程結(jié)束，詳細(xì)步驟為：
重慶分公司
重慶分公司
#include
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=temp){
j--;
}
exchange(&a[i],&a[j]);
while(i #include
using namespace std;
template
void quick_sort_recursive(T arr[], int start, int end) {
if (start >= end)
return;
T mid = arr[end];
int left = start, right = end - 1;
//整個范圍內(nèi)搜尋比樞紐值小或大的元素，然后左側(cè)元素與右側(cè)元素交換
while (left < right) {
//試圖在左側(cè)找到一個比樞紐元更大的元素
while (arr[left] < mid && left < right)
left++;
//試圖在右側(cè)找到一個比樞紐元更小的元素
while (arr[right] >= mid && left < right)
right--;
//交換元素
std::swap(arr[left], arr[right]);
}
//這一步很關(guān)鍵
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
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 兩個版本均可正確運行，但代碼有一點差異:
過程說起來比較抽象，穩(wěn)住別慌！靈魂畫手大白會畫圖來演示這兩個過程。
以第一次遞歸循環(huán)為例:
步驟1: 選擇第一個元素為基準(zhǔn)值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指針繼續(xù)向左掃描，從藍(lán)色虛箭頭9位置游走到3的位置，此時right發(fā)現(xiàn)3<5，因此將此時left和right指向的元素互換，也就是元素3和元素5互換位置；
步驟4: 互換之后left指針繼續(xù)向右掃描，從綠色虛箭頭3位置游走到6的位置，此時left發(fā)現(xiàn)6>5，因此將此時left和right指向的元素互換，也就是元素6和元素5互換位置；
步驟5: 互換之后right指針繼續(xù)向左掃描，從藍(lán)色虛箭頭6位置一直游走到與left指針相遇，此時二者均停留在了pivot=5的新位置上，且左右兩邊分成了兩個相對于pivot值的子序列；
循環(huán)結(jié)束：至此出現(xiàn)了以5為基準(zhǔn)值的左右子序列，接下來就是對兩個子序列實施同樣的遞歸步驟。
以第二次和第三次左子序列遞歸循環(huán)為例:
步驟1-1：選擇第一個元素為基準(zhǔn)值pivot=a[left]=4，right指針指向尾部元素，此時先由right指針向左掃描，恰好起步元素3<4，因此將3和4互換；
步驟1-2：互換之后left指針從元素3開始向右掃描，一直游走到與right指針相遇，此時本次循環(huán)停止，特別注意這種情況下可以看到基準(zhǔn)值4只有左子序列，無右子序列，這種情況是一種退化，就像冒泡排序每次循環(huán)都將基準(zhǔn)值放置到最后，因此效率將退化為冒泡的O(n^2);
步驟1-3：選擇第一個元素為基準(zhǔn)值pivot=a[left]=3，right指針指向尾部元素，此時先由right指針向左掃描，恰好起步元素1<3，因此將1和3互換；
步驟1-4：互換之后left指針從1開始向右掃描直到與right指針相遇，此時注意到pivot=3無右子序列且左子序列l(wèi)en=1，達(dá)到了遞歸循環(huán)的終止條件，此時可以認(rèn)為由第一次循環(huán)產(chǎn)生的左子序列已經(jīng)全部有序。
循環(huán)結(jié)束：至此左子序列已經(jīng)排序完成，接下來對右子序列實施同樣的遞歸步驟，就不再演示了，聰明的你一定get到了。
特別注意:
以上過程中l(wèi)eft和right指針在某個元素相遇，這種情況在代碼中是不會出現(xiàn)的，因為外層限制了i!=j，圖中之所以放到一起是為了直觀表達(dá)終止條件。
分析一下:
個人覺得這個版本雖然同樣使用D&C思想但是更加簡潔，從動畫可以看到選擇pivot=a[end]，然后左右指針分別從index=0和index=end-1向中間靠攏。
過程中掃描目標(biāo)值并左右交換，再繼續(xù)向中間靠攏，直到相遇，此時再根據(jù)a[left]和a[right]以及pivot的值來進(jìn)行合理置換，最終實現(xiàn)基于pivot的左右子序列形式。
腦補場景:
上述過程讓我覺得很像統(tǒng)帥命令左右兩路軍隊從兩翼會和，并且在會和過程中消滅敵人有生力量(認(rèn)為是交換元素)，直到兩路大軍會師。
此時再將統(tǒng)帥王座擺到正確的位置，此過程中沒有統(tǒng)帥王座的反復(fù)變換，只有最終會師的位置，以王座位中心形成了左翼子序列和右翼子序列。
再重復(fù)相同的過程，直至完成大一統(tǒng)。
腦補不過癮 于是湊圖一張:
吃瓜時間：
印象中2017年初換工作的時候去CBD一家公司面試手寫快排，我就使用C++模板化的版本二實現(xiàn)的，但是面試官質(zhì)疑說這不是快排，爭辯之下讓我們彼此都覺得對方很Low，于是很快就把我送出門SayGoodBye了^_^。
我想表達(dá)的意思是，雖然快排的遞歸版本是基于D&C實現(xiàn)的，但是由于pivot值的選擇不同、交換方式不同等諸多因素，造成了多種版本的遞歸代碼。
并且內(nèi)層while循環(huán)里面判斷>=還是>(即是否等于的問題)，外層循環(huán)判斷本序列循環(huán)終止條件等寫法都會不同，因此在寫快排時切忌死記硬背，要不然邊界條件判斷不清楚很容易就死循環(huán)了。
看下上述我貼的兩個版本的代碼核心部分：
//版本一寫法
while(i!=j){
while(i=temp){
j--;
}
exchange(&a[i],&a[j]);
while(i= mid && left < right)
right--;
std::swap(arr[left], arr[right]);
} 覆蓋or交換:
代碼中首先將pivot的值引入局部變量保存下來，這樣就認(rèn)為A[L]這個位置是個坑，可以被其他元素覆蓋，最終再將pivot的值填到最后的坑里。
這種做法也沒有問題，因為你只要畫圖就可以看到，每次坑的位置是有相同元素的位置，也就是被備份了的元素。
個人感覺 與其叫坑不如叫備份，但是如果你代碼使用的是基于指針或者引用的swap，那么就沒有坑的概念了。
這就是覆蓋和交換的區(qū)別，本文的例子都是swap實現(xiàn)的，因此沒有坑位被最后覆蓋一次的過程。
所謂迭代實現(xiàn)就是非遞歸實現(xiàn)一般使用循環(huán)來實現(xiàn)，我們都知道遞歸的實現(xiàn)主要是借助系統(tǒng)內(nèi)的棧來實現(xiàn)的。
如果調(diào)用層級過深需要保存的臨時結(jié)果和關(guān)系會非常多，進(jìn)而造成StackOverflow棧溢出。
Stack一般是系統(tǒng)分配空間有限內(nèi)存連續(xù)速度很快，每個系統(tǒng)架構(gòu)默認(rèn)的棧大小不一樣，筆者在x86-CentOS7.x版本使用ulimit -s查看是8192Byte。
避免棧溢出的一種辦法是使用循環(huán)，以下為筆者驗證的使用STL的stack來實現(xiàn)的循環(huán)版本，代碼如下：
#include
#include
using namespace std;
template
void qsort(T lst[], int length) {
std::stack > mystack;
//將數(shù)組的首尾下標(biāo)存儲 相當(dāng)于第一輪循環(huán)
mystack.push(make_pair(0, length - 1));
while (!mystack.empty()) {
//使用棧頂元素而后彈出
std::pair top = mystack.top();
mystack.pop();
//獲取當(dāng)前需要處理的子序列的左右下標(biāo)
int i = top.first;
int j = top.second;
//選取基準(zhǔn)值
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];
}
//注意這個基準(zhǔn)值回填過程
lst[i] = pivot;
//向下一個子序列進(jìn)發(fā)
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 另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。
