看似青銅實(shí)則王者

很多人提起快排和二分都覺(jué)得很容易的樣子，但是讓現(xiàn)場(chǎng)Code很多就翻車(chē)了，就算可以寫(xiě)出個(gè)遞歸版本的代碼，但是對(duì)其中的復(fù)雜度分析、邊界條件的考慮、非遞歸改造、代碼優(yōu)化等就無(wú)從下手，填鴨背誦基本上分分鐘就被面試官擺平了。

那年初識(shí)快速排序

快速排序Quicksort又稱(chēng)劃分交換排序partition-exchange sort，簡(jiǎn)稱(chēng)快排，一種排序算法。最早由東尼·霍爾(C. A. R. Hoare)教授在1960年左右提出，在平均狀況下，排序n個(gè)項(xiàng)目要O(nlogn)次比較。
在最壞狀況下則需要O(n^2)次比較，但這種狀況并不常見(jiàn)。事實(shí)上，快速排序通常明顯比其他算法更快，因?yàn)樗膬?nèi)部循環(huán)可以在大部分的架構(gòu)上很有效率地達(dá)成。

快速排序的核心思想

在計(jì)算機(jī)科學(xué)中，分治法(Divide&Conquer)是建基于多項(xiàng)分支遞歸的一種很重要的算法范式，快速排序是分治思想在排序問(wèn)題上的典型應(yīng)用。

所謂分治思想D&C就是把一個(gè)較大規(guī)模的問(wèn)題拆分為若干小規(guī)模且相似的問(wèn)題。再對(duì)小規(guī)模問(wèn)題進(jìn)行求解，最終合并所有小問(wèn)題的解，從而形成原來(lái)大規(guī)模問(wèn)題的解。

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

分治法中最重要的部分是循環(huán)遞歸的過(guò)程，每一層遞歸有三個(gè)具體步驟：

• 分解：將原問(wèn)題分解為若干個(gè)規(guī)模較小，相對(duì)獨(dú)立，與原問(wèn)題形式相同的子問(wèn)題。
• 解決：若子問(wèn)題規(guī)模較小且易于解決時(shí)，則直接解。否則，遞歸地解決各子問(wèn)題。
• 合并：將各子問(wèn)題的解合并為原問(wèn)題的解。

快速排序的基本過(guò)程

快速排序使用分治法來(lái)把一個(gè)序列分為小于基準(zhǔn)值和大于基準(zhǔn)值的兩個(gè)子序列。

遞歸地排序兩個(gè)子序列，直至最小的子序列長(zhǎng)度為0或者1，整個(gè)遞歸過(guò)程結(jié)束，詳細(xì)步驟為：

• 挑選基準(zhǔn)值: 從數(shù)列中挑出一個(gè)元素稱(chēng)為基準(zhǔn)pivot，選取基準(zhǔn)值有數(shù)種具體方法，此選取方法對(duì)排序的時(shí)間性能有決定性影響。
• 基準(zhǔn)值分割: 重新排序數(shù)列，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面,所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面，與基準(zhǔn)值相等的數(shù)可以到任何一邊,在這個(gè)分割結(jié)束之后，對(duì)基準(zhǔn)值的排序就已經(jīng)完成。
• 遞歸子序列: 遞歸地將小于基準(zhǔn)值元素的子序列和大于基準(zhǔn)值元素的子序列排序，步驟同上兩步驟,遞歸終止條件是序列大小是0或1，因?yàn)榇藭r(shí)該數(shù)列顯然已經(jīng)有序。

快速排序的遞歸實(shí)現(xiàn)

• 版本一 C實(shí)現(xiàn)

#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++實(shí)現(xiàn)

#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;
 //整個(gè)范圍內(nèi)搜尋比樞紐值小或大的元素，然后左側(cè)元素與右側(cè)元素交換
 while (left < right) {
 //試圖在左側(cè)找到一個(gè)比樞紐元更大的元素
 while (arr[left] < mid && left < right)
 left++;
 //試圖在右側(cè)找到一個(gè)比樞紐元更小的元素
 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 <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;
}

兩個(gè)版本均可正確運(yùn)行，但代碼有一點(diǎn)差異:

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

過(guò)程說(shuō)起來(lái)比較抽象，穩(wěn)住別慌！靈魂畫(huà)手大白會(huì)畫(huà)圖來(lái)演示這兩個(gè)過(guò)程。

快速排序的遞歸演示

• 版本一遞歸代碼的排序過(guò)程示意圖：

以第一次遞歸循環(huán)為例:

步驟1: 選擇第一個(gè)元素為基準(zhǔn)值pivot=a[left]=5,right指針指向尾部元素，此時(shí)先由right自右向左掃描直至遇到<5的元素，恰好right起步元素4<5，因此需要將4與5互換位置；

步驟2: 4與5互換位置之后，輪到left指針從左向右掃描，注意一下left的起步指針指向了由步驟1交換而來(lái)的4，新元素4不滿(mǎn)足停止條件，因此left由綠色虛箭頭4位置游走到元素9的位置，此時(shí)left找到9>5，因此將此時(shí)left和right指向的元素互換，也就是元素5和元素9互換位置；

步驟3: 互換之后right指針繼續(xù)向左掃描，從藍(lán)色虛箭頭9位置游走到3的位置，此時(shí)right發(fā)現(xiàn)3<5，因此將此時(shí)left和right指向的元素互換，也就是元素3和元素5互換位置；

步驟4: 互換之后left指針繼續(xù)向右掃描，從綠色虛箭頭3位置游走到6的位置，此時(shí)left發(fā)現(xiàn)6>5，因此將此時(shí)left和right指向的元素互換，也就是元素6和元素5互換位置；

步驟5: 互換之后right指針繼續(xù)向左掃描，從藍(lán)色虛箭頭6位置一直游走到與left指針相遇，此時(shí)二者均停留在了pivot=5的新位置上，且左右兩邊分成了兩個(gè)相對(duì)于pivot值的子序列；

循環(huán)結(jié)束：至此出現(xiàn)了以5為基準(zhǔn)值的左右子序列，接下來(lái)就是對(duì)兩個(gè)子序列實(shí)施同樣的遞歸步驟。

以第二次和第三次左子序列遞歸循環(huán)為例:

步驟1-1：選擇第一個(gè)元素為基準(zhǔn)值pivot=a[left]=4，right指針指向尾部元素，此時(shí)先由right指針向左掃描，恰好起步元素3<4，因此將3和4互換；

步驟1-2：互換之后left指針從元素3開(kāi)始向右掃描，一直游走到與right指針相遇，此時(shí)本次循環(huán)停止，特別注意這種情況下可以看到基準(zhǔn)值4只有左子序列，無(wú)右子序列，這種情況是一種退化，就像冒泡排序每次循環(huán)都將基準(zhǔn)值放置到最后，因此效率將退化為冒泡的O(n^2);

步驟1-3：選擇第一個(gè)元素為基準(zhǔn)值pivot=a[left]=3，right指針指向尾部元素，此時(shí)先由right指針向左掃描，恰好起步元素1<3，因此將1和3互換；

步驟1-4：互換之后left指針從1開(kāi)始向右掃描直到與right指針相遇，此時(shí)注意到pivot=3無(wú)右子序列且左子序列l(wèi)en=1，達(dá)到了遞歸循環(huán)的終止條件，此時(shí)可以認(rèn)為由第一次循環(huán)產(chǎn)生的左子序列已經(jīng)全部有序。

循環(huán)結(jié)束：至此左子序列已經(jīng)排序完成，接下來(lái)對(duì)右子序列實(shí)施同樣的遞歸步驟，就不再演示了，聰明的你一定get到了。

特別注意:

以上過(guò)程中l(wèi)eft和right指針在某個(gè)元素相遇，這種情況在代碼中是不會(huì)出現(xiàn)的，因?yàn)橥鈱酉拗屏薸!=j，圖中之所以放到一起是為了直觀表達(dá)終止條件。

• 版本二C++版本動(dòng)畫(huà)演示：

分析一下:

個(gè)人覺(jué)得這個(gè)版本雖然同樣使用D&C思想但是更加簡(jiǎn)潔，從動(dòng)畫(huà)可以看到選擇pivot=a[end]，然后左右指針?lè)謩e從index=0和index=end-1向中間靠攏。

過(guò)程中掃描目標(biāo)值并左右交換，再繼續(xù)向中間靠攏，直到相遇，此時(shí)再根據(jù)a[left]和a[right]以及pivot的值來(lái)進(jìn)行合理置換，最終實(shí)現(xiàn)基于pivot的左右子序列形式。

腦補(bǔ)場(chǎng)景:

上述過(guò)程讓我覺(jué)得很像統(tǒng)帥命令左右兩路軍隊(duì)從兩翼會(huì)和，并且在會(huì)和過(guò)程中消滅敵人有生力量(認(rèn)為是交換元素)，直到兩路大軍會(huì)師。

此時(shí)再將統(tǒng)帥王座擺到正確的位置，此過(guò)程中沒(méi)有統(tǒng)帥王座的反復(fù)變換，只有最終會(huì)師的位置，以王座位中心形成了左翼子序列和右翼子序列。

再重復(fù)相同的過(guò)程，直至完成大一統(tǒng)。

腦補(bǔ)不過(guò)癮 于是湊圖一張:

快速排序的多種版本

吃瓜時(shí)間：

印象中2017年初換工作的時(shí)候去CBD一家公司面試手寫(xiě)快排，我就使用C++模板化的版本二實(shí)現(xiàn)的，但是面試官質(zhì)疑說(shuō)這不是快排，爭(zhēng)辯之下讓我們彼此都覺(jué)得對(duì)方很Low，于是很快就把我送出門(mén)SayGoodBye了_。

我想表達(dá)的意思是，雖然快排的遞歸版本是基于D&C實(shí)現(xiàn)的，但是由于pivot值的選擇不同、交換方式不同等諸多因素，造成了多種版本的遞歸代碼。

并且內(nèi)層while循環(huán)里面判斷>=還是>(即是否等于的問(wèn)題)，外層循環(huán)判斷本序列循環(huán)終止條件等寫(xiě)法都會(huì)不同，因此在寫(xiě)快排時(shí)切忌死記硬背，要不然邊界條件判斷不清楚很容易就死循環(huán)了。

看下上述我貼的兩個(gè)版本的代碼核心部分：

//版本一寫(xiě)法
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]);
}

//版本二寫(xiě)法
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的值引入局部變量保存下來(lái)，這樣就認(rèn)為A[L]這個(gè)位置是個(gè)坑，可以被其他元素覆蓋，最終再將pivot的值填到最后的坑里。

這種做法也沒(méi)有問(wèn)題，因?yàn)槟阒灰?huà)圖就可以看到，每次坑的位置是有相同元素的位置，也就是被備份了的元素。

個(gè)人感覺(jué) 與其叫坑不如叫備份，但是如果你代碼使用的是基于指針或者引用的swap，那么就沒(méi)有坑的概念了。

這就是覆蓋和交換的區(qū)別，本文的例子都是swap實(shí)現(xiàn)的，因此沒(méi)有坑位被最后覆蓋一次的過(guò)程。

快速排序的迭代實(shí)現(xiàn)

所謂迭代實(shí)現(xiàn)就是非遞歸實(shí)現(xiàn)一般使用循環(huán)來(lái)實(shí)現(xiàn)，我們都知道遞歸的實(shí)現(xiàn)主要是借助系統(tǒng)內(nèi)的棧來(lái)實(shí)現(xiàn)的。

如果調(diào)用層級(jí)過(guò)深需要保存的臨時(shí)結(jié)果和關(guān)系會(huì)非常多，進(jìn)而造成StackOverflow棧溢出。

Stack一般是系統(tǒng)分配空間有限內(nèi)存連續(xù)速度很快，每個(gè)系統(tǒng)架構(gòu)默認(rèn)的棧大小不一樣，筆者在x86-centos7.x版本使用ulimit -s查看是8192Byte。

避免棧溢出的一種辦法是使用循環(huán)，以下為筆者驗(yàn)證的使用STL的stack來(lái)實(shí)現(xiàn)的循環(huán)版本，代碼如下：

#include <stack>
#include <iostream>
using namespace std;

template<typename T>
void qsort(T lst[], int length) {
 std::stack<std::pair<int, int> > mystack;
 //將數(shù)組的首尾下標(biāo)存儲(chǔ) 相當(dāng)于第一輪循環(huán)
 mystack.push(make_pair(0, length - 1));

 while (!mystack.empty()) {
 //使用棧頂元素而后彈出
 std::pair<int,int> 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];
 }
 //注意這個(gè)基準(zhǔn)值回填過(guò)程
 lst[i] = pivot;

 //向下一個(gè)子序列進(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<len-1;i++)
 cout<<a[i]<<endl;
}