深入理解快速排序和STL的sort算法

1.寫在前面

周六了...依然跳票...沒有新文章產(chǎn)出...因?yàn)楹苊?..是的...

為了證明筆者沒有放棄這塊陣地，整合三篇去年的文章，今天一起來學(xué)習(xí)一下：快速排序及其優(yōu)化 和 STL的sort算法

通過本文你將了解到以下內(nèi)容：

• 快速排序的基本思想
• 快速排序的遞歸實(shí)現(xiàn)和迭代實(shí)現(xiàn)
• 快速排序的最壞情況
• 快速排序和歸并排序?qū)Ρ?
• 快速排序的多角度優(yōu)化
• 內(nèi)省式排序基本原理
• STL的sort算法基本原理

2. 那年初識(shí)快排

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

常見不等同于簡單。

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

快速排序Quicksort又稱劃分交換排序partition-exchange sort，簡稱快排，一種排序算法。最早由C. A. R. Hoare教授在1960年左右提出，在平均狀況下，排序n個(gè)項(xiàng)目要O(nlogn)次比較。

在最壞狀況下則需要O(n^2)次比較，但這種狀況并不常見。事實(shí)上，快速排序通常明顯比其他算法更快，因?yàn)樗膬?nèi)部循環(huán)可以在大部分的架構(gòu)上很有效率地達(dá)成。

快排的提出者是大名鼎鼎的人物，go語言使用的并發(fā)模型CSP也是這個(gè)大神提出的，一起膜拜下。

查爾斯·安東尼·理查德·霍爾爵士(Sir Charles Antony Richard Hoare縮寫為C. A. R. Hoare，1934年1月11日－），昵稱為東尼·霍爾(Tony Hoare)，生于大英帝國錫蘭可倫坡（今斯里蘭卡），英國計(jì)算機(jī)科學(xué)家，圖靈獎(jiǎng)得主。

他設(shè)計(jì)了快速排序算法、霍爾邏輯、交談循序程式。在操作系統(tǒng)中，他提出哲學(xué)家就餐問題，并發(fā)明用來作為同步程序的監(jiān)視器（Monitors）以解決這個(gè)問題。他同時(shí)證明了監(jiān)視器與信號(hào)標(biāo)（Semaphore）在邏輯上是等價(jià)的。

1980年獲頒圖靈獎(jiǎng)、1982年成為英國皇家學(xué)會(huì)院士、2000年因?yàn)樗谟?jì)算機(jī)科學(xué)與教育方面的杰出貢獻(xiàn)，獲得英國王室頒贈(zèng)爵士頭銜、2011年獲頒約翰·馮諾依曼獎(jiǎng)，現(xiàn)為牛津大學(xué)榮譽(yù)教授，并在劍橋微軟研究院擔(dān)任研究員。

2.2 快速排序的基本思想和過程

2.2.1 D&C分治思想

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

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

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

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

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

2.2.2 基本過程

快速排序使用分治法來把一個(gè)序列分為小于基準(zhǔn)值和大于基準(zhǔn)值的兩個(gè)子序列。遞歸地排序兩個(gè)子序列，直至最小的子序列長度為0或者1，整個(gè)遞歸過程結(jié)束，詳細(xì)步驟為：

• 挑選基準(zhǔn)值: 從數(shù)列中挑出一個(gè)元素稱為基準(zhǔn)pivot，選取基準(zhǔn)值有數(shù)種具體方法，此選取方法對排序的時(shí)間性能有決定性影響。

• 基準(zhǔn)值分割: 重新排序數(shù)列，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面,所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面，與基準(zhǔn)值相等的數(shù)可以到任何一邊,在這個(gè)分割結(jié)束之后，對基準(zhǔn)值的排序就已經(jīng)完成。

• 遞歸子序列: 遞歸地將小于基準(zhǔn)值元素的子序列和大于基準(zhǔn)值元素的子序列排序，步驟同上兩步驟,遞歸終止條件是序列大小是0或1，因?yàn)榇藭r(shí)該數(shù)列顯然已經(jīng)有序。

3. 快速的遞歸實(shí)現(xiàn)和迭代實(shí)現(xiàn)

快速排序一般大家寫遞歸的時(shí)候更多，但是遞歸往往也會(huì)寫出不同風(fēng)格的版本，所以我們一起來看下多個(gè)風(fēng)格的遞歸版本和迭代版本的實(shí)現(xiàn)，多種代碼對比會(huì)讓我們理解更深刻。

3.1 遞歸實(shí)現(xiàn)代碼

C語言遞歸版本一：

C++遞歸版本二：

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

• 版本一 使用雙指針交替從左(右)兩邊分別開始尋找大于基準(zhǔn)值(小于基準(zhǔn)值)，然后與基準(zhǔn)值交換，直到最后左右指針相遇。

• 版本二 使用雙指針向中間集合，左指針遇到大于基準(zhǔn)值時(shí)則停止，等待右指針，右指針遇到小于基準(zhǔn)值時(shí)則停止，與左指針指向的元素交換，最后基準(zhǔn)值放到合適位置。

3.2 遞歸實(shí)現(xiàn)過程演示

過程說起來比較抽象，穩(wěn)住別慌！靈魂畫手畫圖來演示這兩個(gè)過程。

3.2.1 C版本一過程演示

以第一次遞歸循環(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交換而來的4，新元素4不滿足停止條件，因此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è)相對于pivot值的子序列；

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

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

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

步驟1-2：互換之后left指針從元素3開始向右掃描，一直游走到與right指針相遇，此時(shí)本次循環(huán)停止，特別注意這種情況下可以看到基準(zhǔn)值4只有左子序列，無右子序列，這種情況是一種退化，就像冒泡排序每次循環(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開始向右掃描直到與right指針相遇，此時(shí)注意到pivot=3無右子序列且左子序列l(wèi)en=1，達(dá)到了遞歸循環(huán)的終止條件，此時(shí)可以認(rèn)為由第一次循環(huán)產(chǎn)生的左子序列已經(jīng)全部有序。

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

特別注意:

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

3.2.2 C++版本二過程演示

分析一下:

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

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

腦補(bǔ)場景:

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

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

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

3.3 多種遞歸版本說明

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

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

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

另外在網(wǎng)上很多大神的博客里面還進(jìn)行了多種模式的快排：單軸模式、雙向切分、三項(xiàng)切分、多基準(zhǔn)值等新花樣，感興趣可以參考快速排序算法的多種實(shí)現(xiàn)。

其實(shí)無論哪種寫法都需要明確知道自己是交換、還是覆蓋、基準(zhǔn)值選取位置、>=和<=的等號(hào)問題、循環(huán)終止條件等，這樣才能寫出BugFree的快速排序算法。

網(wǎng)上很多代碼的核心部分是這樣寫的：

覆蓋or交換

代碼中首先將pivot的值引入局部變量保存下來，這樣就認(rèn)為A[L]這個(gè)位置是個(gè)坑，可以被其他元素覆蓋，最終再將pivot的值填到最后的坑里。

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

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

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

3.4 迭代版本實(shí)現(xiàn)

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

如果調(diào)用層級(jí)過深需要保存的臨時(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來實(shí)現(xiàn)的循環(huán)版本，代碼如下：

4. 快速排序的優(yōu)化

快速排序是圖領(lǐng)獎(jiǎng)得主發(fā)明的算法，被譽(yù)為20世紀(jì)最重要的十大算法之一，快速排序?yàn)榱丝梢栽诙喾N數(shù)據(jù)集都有出色的表現(xiàn)，進(jìn)行了非常多的優(yōu)化，因此對我們來說要深入理解一種算法的最有效的手段就是不斷優(yōu)化提高性能。

4.1 快速排序vs歸并排序

快速排序和歸并排序采用的基本思想都是分治思想Divide&Conquer，從D&C思想來看最主要的部分就是分割和合并，兩種算法在使用D&C時(shí)側(cè)重點(diǎn)有一些差異:

歸并排序在分割時(shí)處理很簡單，在合并時(shí)處理比較多，重點(diǎn)在合并。

快速排序在分割時(shí)處理比較復(fù)雜，由于交換的存在遞歸結(jié)束時(shí)就相當(dāng)于合并完成了，重點(diǎn)在分割。

歸并排序分治示意圖：

快速排序分治示意圖：

注:快排的過程就不寫具體的數(shù)字了 僅為達(dá)意 點(diǎn)到即可。

可以明顯看出來，快速排序在選擇基準(zhǔn)值時(shí)對整個(gè)分治過程影響很大，因?yàn)橄乱粋€(gè)環(huán)節(jié)的分治是基于前一環(huán)節(jié)的分割結(jié)果進(jìn)行的。

4.2 分區(qū)不均勻和最壞復(fù)雜度

4.2.1 極端分區(qū)

考慮一種極端的情況下，如果基準(zhǔn)值選取的不合理，比如是最大的或者最小的，那么將導(dǎo)致只有一邊有數(shù)據(jù)，對于已經(jīng)排序或者近乎有序的數(shù)據(jù)集合來說就可能出現(xiàn)這種極端情況，還是來畫個(gè)圖看下：

圖中展示了每次分治都選擇第一個(gè)元素作為基準(zhǔn)值，但是每次的基準(zhǔn)值都是最小值，導(dǎo)致每次基準(zhǔn)值左側(cè)沒有子序列，除了基準(zhǔn)值之外全部元素都在右子序列。

4.2.2 最壞情況概率和復(fù)雜度計(jì)算

每次分割排序之后，只能在有序序列中增加1個(gè)元素遞歸樹變成了單支樹并且遞歸深度變大，極端情況的出現(xiàn)概率和最壞復(fù)雜度計(jì)算如下：

極端情況概率就是每次在剩余所有元素中挑出最小的，這樣每次的概率都是1/(n-i)，所以組合起來就是1/(n!)，所以隨機(jī)數(shù)據(jù)集合出現(xiàn)最差情況的概率非常低，但是有序數(shù)據(jù)下固定基準(zhǔn)值選擇就可能造成極端情況的出現(xiàn)。

最壞復(fù)雜度相當(dāng)于每次從n-i個(gè)元素中只找到1個(gè)數(shù)據(jù)，將所有情況累加也就達(dá)到了O(n^2)級(jí)別，并不是遞歸過程全都挑選了最值作為基準(zhǔn)值才會(huì)出現(xiàn)O(n^2)的復(fù)雜度，復(fù)雜度是一個(gè)概率化的期望值，具體的系數(shù)不同影響也很大。

4.3 基準(zhǔn)值選取優(yōu)化

分割越均勻速度越快 

從上面的幾張圖可以清晰看到基準(zhǔn)值的不同對于D&C過程的分割會(huì)產(chǎn)生很大的影響，為了保證快速排序的在通用數(shù)據(jù)集的效率，因此我們需要在基準(zhǔn)值的選取上做一些決策，換句話說就是讓選取的基準(zhǔn)值每次都可以盡可能均勻地分割數(shù)據(jù)集，這樣的效率是最高的。

隨機(jī)選取基準(zhǔn)值 

網(wǎng)上有很多選擇方法比如固定選取第一個(gè)、固定選取最后一個(gè)、固定選擇中間值、三值平均選取等，不過個(gè)人覺得每一次都隨機(jī)選取某個(gè)位置的數(shù)據(jù)作為基準(zhǔn)值，然后與第一個(gè)值互換，這樣就相當(dāng)于每次的基準(zhǔn)值都是隨機(jī)選擇的，就將固定index帶來的問題，大大降低了。

隨機(jī)vs固定對比試驗(yàn) 

接下來做一組對比試驗(yàn)，生成一個(gè)0-100000的有序數(shù)組，代碼增加了很多選擇項(xiàng)和時(shí)間測量代碼，測試代碼如下：

筆者使用相同的數(shù)據(jù)集在fix和random模式下，后者的耗時(shí)明顯低于前者，所以某些場景下隨機(jī)化帶來的性能提升很明顯，是一個(gè)慣用的優(yōu)化方法。

4.4 三分區(qū)模式優(yōu)化

前面的路子都是以基準(zhǔn)值為準(zhǔn)分為小于子序列和大于子序列，考慮一種特殊的數(shù)據(jù)集，數(shù)據(jù)集中有大量重復(fù)元素，這種情況下使用兩分區(qū)遞歸會(huì)對大量重復(fù)元素進(jìn)行處理。

一個(gè)優(yōu)化的方向就是使用三分區(qū)模式：小于區(qū)間、等于區(qū)間、大于區(qū)間,這樣在后續(xù)的處理中則只需要處理小于區(qū)和大于區(qū)，降低了等于基準(zhǔn)值區(qū)間元素的重復(fù)處理，加速排序過程。

4.4.1 三分區(qū)原理

如圖為三分區(qū)模式中某個(gè)時(shí)刻的快照，其中展示了幾個(gè)關(guān)鍵點(diǎn)和區(qū)間，包括基準(zhǔn)值、小于區(qū)、等于區(qū)、處理值、待處理區(qū)、大于區(qū)。

在實(shí)際過程中根據(jù)處理值與基準(zhǔn)值的大小關(guān)系，進(jìn)行相應(yīng)分區(qū)合并和交換，再進(jìn)行下標(biāo)移動(dòng)就可以了，實(shí)際中分三種情況，這也是寫代碼的依據(jù)：

1. 處理值e==p，將e合并到等于區(qū)，i++；

2. 處理值e<p，將e與(lt+1)位置的數(shù)據(jù)交換，擴(kuò)展小于區(qū)lt++，等于區(qū)長度不變，相當(dāng)于整體平移；

3. 處理值e>p，將e與(gt-1)位置的數(shù)據(jù)交換，擴(kuò)展大于區(qū)gt--，此時(shí)i不變，交換后的值是之前待處理區(qū)的尾部數(shù)據(jù)；

• e==p的合并

• e<p的合并

• e>p的合并

• 分區(qū)最終調(diào)整

處理完待處理區(qū)的全部數(shù)據(jù)之后的調(diào)整也非常重要，主要是將基準(zhǔn)值P與lt位置的數(shù)據(jù)交換，從而實(shí)現(xiàn)最終的三分區(qū)，如圖所示：

從最終的分區(qū)可以看到，我們下一次的循環(huán)可以不處理等于區(qū)的數(shù)據(jù)而只處理兩端分區(qū)數(shù)據(jù)，這樣在大量重復(fù)場景下優(yōu)化效果會(huì)非常明顯。

4.4.2 三分區(qū)實(shí)驗(yàn)

筆者使用相同的數(shù)據(jù)集在二分區(qū)模式下測試10w數(shù)據(jù)規(guī)模耗時(shí)大約是1800ms，數(shù)據(jù)集減少10倍耗時(shí)卻增大了幾十倍，或許二分區(qū)代碼還是存在優(yōu)化空間，不過這個(gè)對比可以看到存在大量重復(fù)元素時(shí)三分區(qū)性能還是很不錯(cuò)的。

4.5 快排優(yōu)化小結(jié)

對快速排序的優(yōu)化主要體現(xiàn)在基準(zhǔn)值選取、數(shù)據(jù)集分割、遞歸子序列選取、其他排序算法混合等方面，換句話說就是讓每次的分區(qū)盡量均勻且沒有重復(fù)被處理的元素，這樣才能保證每次遞歸都是高效簡潔的。

5. STL的sort算法

在了解sort算法的實(shí)現(xiàn)之前先來看一個(gè)概念：內(nèi)省式排序，說實(shí)話筆者的語文水平確實(shí)一般，對于這個(gè)詞語用在排序算法上總覺得不通透，那就研究一下吧！

5.1 內(nèi)省思想

內(nèi)省式排序英文是Introspective Sort，其中單詞introspective是內(nèi)省型的意思，還是不太明白，繼續(xù)搜索，看一下百度百科對這個(gè)詞條的解釋：

內(nèi)?。↖ntrospection ）在心理學(xué)中，它是心理學(xué)基本研究方法之一。內(nèi)省法又稱自我觀察法。它是發(fā)生在內(nèi)部的，我們自己能夠意識(shí)到的主觀現(xiàn)象。也可以說是對于自己的主觀經(jīng)驗(yàn)及其變化的觀察。

正因?yàn)樗闹饔^性，內(nèi)省法自古以來就成為心理學(xué)界長期的爭論。另外內(nèi)省也可看作自我反省，也是儒家強(qiáng)調(diào)的自我思考。從這個(gè)角度說可以應(yīng)用于計(jì)算機(jī)領(lǐng)域，如Java內(nèi)省機(jī)制和cocoa內(nèi)省機(jī)制。

From 百度百科-內(nèi)省-科普中國審核通過詞條

原來內(nèi)省是個(gè)心理學(xué)名詞，到這里筆者有些感覺了，內(nèi)省就是自省、自我思考、根據(jù)自己的主觀經(jīng)驗(yàn)來觀察變化做出調(diào)整，而不是把希望寄托于外界，而是自己的經(jīng)驗(yàn)和能力。

通俗點(diǎn)說，內(nèi)省算法不挑數(shù)據(jù)集，盡量針對每種數(shù)據(jù)集都能給定對應(yīng)的處理方法，讓排序都能有時(shí)間保證。寫到這里，讓筆者腦海浮現(xiàn)了《倚天屠龍記》里面張無忌光明頂大戰(zhàn)六大門派的場景，無論敵人多么強(qiáng)悍或者羸弱，我都按照自己的路子應(yīng)對。

原來內(nèi)省是個(gè)心理學(xué)名詞，到這里筆者有些感覺了，內(nèi)省就是自省、自我思考、根據(jù)自己的主觀經(jīng)驗(yàn)來觀察變化做出調(diào)整，而不是把希望寄托于外界，而是自己的經(jīng)驗(yàn)和能力。

通俗點(diǎn)說，內(nèi)省算法不挑數(shù)據(jù)集，盡量針對每種數(shù)據(jù)集都能給定對應(yīng)的處理方法，讓排序都能有時(shí)間保證。寫到這里，讓筆者腦海浮現(xiàn)了《倚天屠龍記》里面張無忌光明頂大戰(zhàn)六大門派的場景，無論敵人多么強(qiáng)悍或者羸弱，我都按照自己的路子應(yīng)對。

5.2 內(nèi)省排序概況

俗話說俠者講究刀、槍、劍、戟、斧、鉞、鉤、叉等諸多兵器，這也告訴我們一個(gè)道理沒有哪種兵器是無敵的，只有在某些場景下的明顯優(yōu)勢，這跟軟件工程沒有銀彈是一樣的。

回到我們的排序算法上，排序算法也可謂是百花齊放：冒泡排序、選擇排序、插入排序、快速排序、堆排序、桶排序等等。

雖然一批老一輩的排序算法是O(n^2)的，優(yōu)秀的算法可以到達(dá)O(nlogn)，但是即使都是nlogn的快速排序和堆排序都有各自的長短之處，插入排序在數(shù)據(jù)幾乎有序的場景下性能可以到達(dá)O(n)，有時(shí)候我們應(yīng)該做的不是沖突對比而是融合創(chuàng)新。

內(nèi)省排序是由David Musser在1997年設(shè)計(jì)的排序算法。這個(gè)排序算法首先從快速排序開始，當(dāng)遞歸深度超過一定深度（深度為排序元素?cái)?shù)量的對數(shù)值）后轉(zhuǎn)為堆排序,David Musser大牛是STL領(lǐng)域響當(dāng)當(dāng)?shù)娜宋铩?/span>

拋開語境一味地對比孰好孰壞其實(shí)都沒有意義，內(nèi)省式排序就是集大成者，為了能讓排序算法達(dá)到一個(gè)綜合的優(yōu)異性能，內(nèi)省式排序算法結(jié)合了快速排序、堆排序、插入排序，并根據(jù)當(dāng)前數(shù)據(jù)集的特點(diǎn)來選擇使用哪種排序算法，讓每種算法都展示自己的長處，這種思想確實(shí)挺啟發(fā)人的。

5.3 內(nèi)省排序排兵布陣

前面提到了內(nèi)省式排序主要結(jié)合了快速排序、堆排序、插入排序，那么不禁要問，這三種排序是怎么排兵布陣的呢？知己知彼百戰(zhàn)不殆，所以先看下三種排序的優(yōu)缺點(diǎn)吧！

• 快速排序 在大量數(shù)據(jù)時(shí)無論是有序還是重復(fù)，使用優(yōu)化后的算法大多可以到達(dá)O(nlogn)，雖然堆排序也是O(nlogn)但是由于某些原因快速排序會(huì)更快一些，當(dāng)遞歸過深分割嚴(yán)重不均勻情況出現(xiàn)時(shí)會(huì)退化為O(n^2)的復(fù)雜度，這時(shí)性能會(huì)打折扣，這也就是快速排序的短處了。

• 堆排序 堆排序是快速排序的有力競爭者，最大的特點(diǎn)是可以到達(dá)O(nlogn)并且復(fù)雜度很穩(wěn)定，并不會(huì)像快速排序一樣可能退化為O(n^2)，但是堆排序過程中涉及大量堆化調(diào)整，并且元素比較是跳著來的對Cache的局部性特征利用不好，以及一些其他的原因?qū)е露雅判虮瓤焖倥判蚋稽c(diǎn)，但是大O復(fù)雜度仍然是一個(gè)級(jí)別的。

• 插入排序 插入排序的一個(gè)特點(diǎn)是就像我們玩紙牌，在梳理手中的牌時(shí)，如果已經(jīng)比較有序了，那么只需要做非常少的調(diào)整即可，因此插入排序在數(shù)據(jù)量不大且近乎有序的情況下復(fù)雜度可以降低到O(n)，這一點(diǎn)值得被應(yīng)用。

優(yōu)缺點(diǎn)也大致清楚了，所以可以猜想一下內(nèi)省式排序在實(shí)際中是如何調(diào)度使這三種排序算法的：

• 啟動(dòng)階段 面對大量的待排序元素，首先使用快速排序進(jìn)行大刀闊斧排序，復(fù)雜度可以在O(nlogn)運(yùn)行

• 深入階段 在快速排序使用遞歸過程中，涉及棧幀保存切換等諸多遞歸的操作，如果分區(qū)切割不當(dāng)遞歸過深可能造成棧溢出程序終止，因此如果快速排序過程中退化為O(n^2)，此時(shí)會(huì)自動(dòng)檢測切換為堆排序，因?yàn)槎雅判驔]有惡化情況，都可以穩(wěn)定在O(nlogn)

• 收尾階段 在經(jīng)過快排和堆排的處理之后，數(shù)據(jù)分片的待排序元素?cái)?shù)量小于某個(gè)經(jīng)驗(yàn)設(shè)定值(可以認(rèn)為是遞歸即將結(jié)束的前幾步調(diào)用)時(shí)，數(shù)據(jù)其實(shí)已經(jīng)幾乎有序，此時(shí)就可以使用插入排序來提高效率，將復(fù)雜度進(jìn)一步降低為O(n)。

---

5.4 sort算法細(xì)節(jié)

本文介紹的sort算法是基于SGI STL版本的，并且主要是以侯捷老師的《STL源碼剖析》一書為藍(lán)本來進(jìn)行展開的，因此使用了不帶仿函數(shù)的版本。

SGI STL中的sort的參數(shù)是兩個(gè)隨機(jī)存取迭代器RandomAccessIterator，sort的模板也是基于此種迭代器的，因此如果容器不是隨機(jī)存取迭代器，那么可能無法使用通用的sort函數(shù)。

• 關(guān)聯(lián)容器 map和set底層是基于RB-Tree，本身就已經(jīng)自帶順序了，因此不需要使用sort算法
• 序列容器 list是雙向迭代器并不是隨機(jī)存取迭代器，vector和deque是隨機(jī)存取迭代器適用于sort算法
• 容器適配器 stack、queue和priority-queue屬于限制元素順序的容器，因此不適用sort算法。

綜上我們可以知道，sort算法可以很好的適用于vector和deque這兩種容器。

前面介紹了內(nèi)省式排序，所以看下sort是怎么一步步來使用introsort的，上一段入口代碼：

從代碼來看sort使用了first和last兩個(gè)隨機(jī)存取迭代器，作為待排序序列的開始和終止，進(jìn)一步調(diào)用了__introsort_loop和__final_insertion_sort兩個(gè)函數(shù)，從字面上看前者是內(nèi)省排序循環(huán)，后者是插入排序。其中注意到__introsort_loop的第三個(gè)參數(shù)__lg(last - first)*2，憑借我們的經(jīng)驗(yàn)來猜(蒙)一下吧，應(yīng)該遞歸深度的限制，不急看下代碼實(shí)現(xiàn)：

這段代碼的意思就是n=last-first，2^k<=n的最大整數(shù)k值。

所以整體看當(dāng)假設(shè)last-first=20時(shí)，k=4,最大分割深度depth_max=4*2=8，從而我們就可以根據(jù)first和last來確定遞歸的最大深度了。

快速排序和堆排序的配合

__introsort_loop函數(shù)中主要封裝了快速排序和堆排序，來看看這個(gè)函數(shù)的實(shí)現(xiàn)細(xì)節(jié)：

各位先不要暈更不要蒙圈，一點(diǎn)點(diǎn)分析肯定可以拿下的。

• 先看參數(shù)兩個(gè)隨機(jī)存取迭代器first和last，第三個(gè)參數(shù)是__lg計(jì)算得到的分割深度；

• 這時(shí)候我們進(jìn)入了while判斷了last-first的區(qū)間大小，__stl_threshold為16，侯捷大大特別指出__stl_threshold的大小可以是5~20，具體大小可以自己設(shè)置，如果大于__stl_threshold那就才會(huì)繼續(xù)執(zhí)行，否則跳出；

• 假如現(xiàn)在區(qū)間大小大于__stl_threshold，判斷第三個(gè)參數(shù)depth_limit是否為0，也就是是否出現(xiàn)了分割過深的情況，相當(dāng)于給了一個(gè)初始最大值，然后每分割一次就減1，直到depth_limit=0，這時(shí)候調(diào)用partial_sort，從《stl源碼剖析》的其他章節(jié)可以知道，partial_sort就是對堆排序的封裝，看到這里有點(diǎn)意思了主角之一的heapsort出現(xiàn)了；

• 繼續(xù)往下看，depth_limit>0 尚有分割余額，那就燥起來吧！這樣來到了__unguarded_partition，這個(gè)函數(shù)從字眼看是快速排序的partiton過程，返回了cut隨機(jī)存取迭代器，__unguarded_partition的第三個(gè)參數(shù)__median使用的是三點(diǎn)中值法來獲取的基準(zhǔn)值Pivot，至此快速排序的partition的三個(gè)元素集齊了，最后返回新的切割點(diǎn)位置；

• 繼續(xù)看馬上搞定啦，__introsort_loop出現(xiàn)了，果然遞歸了，特別注意一下這里只有一個(gè)遞歸，并且傳入的是cut和last，相當(dāng)于右子序列，那左子序列怎么辦啊？別急往下看，last=cut峰回路轉(zhuǎn)cut變成了左子序列的右邊界，這樣就開始了左子序列的處理；

快速排序的實(shí)現(xiàn)對比

前面提到了在sort中快速排序的寫法和我們之前見到的有一些區(qū)別，看了一下《STL源碼剖析》對快排左序列的處理，侯捷老師是這么寫的："寫法可讀性較差，效率并沒有比較好"，看到這里更蒙圈了，不過也試著分析一下吧！

圖為：STL源碼剖析中侯捷老師對該種寫法的注釋

常見寫法：

SGI STL中的寫法:

網(wǎng)上有一些大佬的文章說sgi stl中快排的寫法左序列的調(diào)用借助了while循環(huán)節(jié)省了一半的遞歸調(diào)用，是典型的尾遞歸優(yōu)化思路.

這里我暫時(shí)還沒有寫測試代碼做對比，先占坑后續(xù)寫個(gè)對比試驗(yàn)，再來評(píng)論吧，不過這種sgi的這種寫法可以看看哈。

堆排序的細(xì)節(jié)

//注：這個(gè)是帶自定義比較函數(shù)的堆排序版本
//堆化和堆頂操作
template <class RandomAccessIterator, class T, class Compare>
void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
                    RandomAccessIterator last, T*, Compare comp) {
    make_heap(first, middle, comp);
    for (RandomAccessIterator i = middle; i < last; ++i)
        if (comp(*i, *first))
            __pop_heap(first, middle, i, T(*i), comp, distance_type(first));
    sort_heap(first, middle, comp);
}
//堆排序的入口
template <class RandomAccessIterator, class Compare>
inline void partial_sort(RandomAccessIterator first,
                         RandomAccessIterator middle,
                         RandomAccessIterator last, Compare comp) {
    __partial_sort(first, middle, last, value_type(first), comp);
}

插入排序上場了

__introsort_loop達(dá)到__stl_threshold閾值之后，可以認(rèn)為數(shù)據(jù)集近乎有序了，此時(shí)就可以通過插入排序來進(jìn)一步提高排序速度了，這樣也避免了遞歸帶來的系統(tǒng)消耗，看下__final_insertion_sort的具體實(shí)現(xiàn)：

template <class RandomAccessIterator>
void __final_insertion_sort(RandomAccessIterator first, 
                            RandomAccessIterator last) {
    if (last - first > __stl_threshold) {
        __insertion_sort(first, first + __stl_threshold);
        __unguarded_insertion_sort(first + __stl_threshold, last);
    }
    else
        __insertion_sort(first, last);
}

來分析一下__final_insertion_sort的實(shí)現(xiàn)細(xì)節(jié)吧！

• 引入?yún)?shù)隨機(jī)存取迭代器first和last

• 如果last-first > __stl_threshold不成立就調(diào)用__insertion_sort，這個(gè)相當(dāng)于元素?cái)?shù)比較少了可以直接調(diào)用，不用做特殊處理；

• 如果last-first > __stl_threshold成立就進(jìn)一步再分割成兩部分，分別調(diào)用__insertion_sort和__unguarded_insertion_sort，兩部分的分割點(diǎn)是__stl_threshold，不免要問這倆函數(shù)有啥區(qū)別呀？

__insertion_sort的實(shí)現(xiàn)

//逆序?qū)Φ恼{(diào)整
template <class RandomAccessIterator, class T>
void __unguarded_linear_insert(RandomAccessIterator last, T value) {
    RandomAccessIterator next = last;
    --next;
    while (value < *next) {
        *last = *next;
        last = next;
        --next;
    }
    *last = value;
}

template <class RandomAccessIterator, class T>
inline void __linear_insert(RandomAccessIterator first, 
                            RandomAccessIterator last, T*) {
    T value = *last;
    if (value < *first) {
        copy_backward(first, last, last + 1);//區(qū)間移動(dòng)
        *first = value;
    }
    else
        __unguarded_linear_insert(last, value);
}

//__insertion_sort入口
template <class RandomAccessIterator>
void __insertion_sort(RandomAccessIterator first, RandomAccessIterator last) {
    if (first == last) return; 
    for (RandomAccessIterator i = first + 1; i != last; ++i)
        __linear_insert(first, i, value_type(first));
}

在插入函數(shù)中同樣出現(xiàn)了__unguarded_xxx這種形式的函數(shù)，unguarded單詞的意思是無防備的，無保護(hù)的，侯捷大大提到這種函數(shù)形式是特定條件下免去邊界檢驗(yàn)條件也能正確運(yùn)行的函數(shù)。

copy_backward也是一種整體移動(dòng)的優(yōu)化，避免了one by one的調(diào)整移動(dòng)，底層調(diào)用memmove來高效實(shí)現(xiàn)。

__unguarded_insertion_sort的實(shí)現(xiàn)

template <class RandomAccessIterator, class T>
void __unguarded_insertion_sort_aux(RandomAccessIterator first, 
                                    RandomAccessIterator last, T*) {
    for (RandomAccessIterator i = first; i != last; ++i)
        __unguarded_linear_insert(i, T(*i));
}

template <class RandomAccessIterator>
inline void __unguarded_insertion_sort(RandomAccessIterator first, 
                                RandomAccessIterator last) {
    __unguarded_insertion_sort_aux(first, last, value_type(first));
}

關(guān)于插入排序的這兩個(gè)函數(shù)的實(shí)現(xiàn)和目的用途，展開起來會(huì)很細(xì)致，所以后面想著單獨(dú)在寫插入排序時(shí)單獨(dú)拿出了詳細(xì)學(xué)習(xí)一下。

6.寫在最后

忙碌的日子里自己的時(shí)間就變得很少，然后開始思考未來，其實(shí)這樣并不好。

不多說了，感謝各位讀者的傾情閱讀，筆芯你們。

巨人的肩膀

• http://feihu.me/blog/2014/sgi-std-sort/
• https://liam.page/2018/09/18/std-sort-in-STL/
• https://zhuanlan.zhihu.com/p/36274119
• 侯捷《STL源碼剖析》第六章