以下文章來源于后端技術(shù)指南針 宾抓，作者后端技術(shù)指南針
1.寫在前面
今天一起來學(xué)習(xí)一下：快速排序及其優(yōu)化 和 STL的sort算法
通過本文你將了解到以下內(nèi)容：
- 快速排序的基本思想
- 快速排序的遞歸實(shí)現(xiàn)和迭代實(shí)現(xiàn)
- 快速排序的最壞情況
- 快速排序和歸并排序?qū)Ρ?/li>
- 快速排序的多角度優(yōu)化
- 內(nèi)省式排序基本原理
- STL的sort算法基本原理
2. 那年初識快排
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é)家，圖靈獎得主庐冯。
他設(shè)計(jì)了快速排序算法孽亲、霍爾邏輯、交談循序程式展父。在操作系統(tǒng)中墨林，他提出哲學(xué)家就餐問題，并發(fā)明用來作為同步程序的監(jiān)視器（Monitors）以解決這個(gè)問題犯祠。他同時(shí)證明了監(jiān)視器與信號標(biāo)（Semaphore）在邏輯上是等價(jià)的旭等。
1980年獲頒圖靈獎、1982年成為英國皇家學(xué)會院士衡载、2000年因?yàn)樗谟?jì)算機(jī)科學(xué)與教育方面的杰出貢獻(xiàn)搔耕，獲得英國王室頒贈爵士頭銜、2011年獲頒約翰·馮諾依曼獎，現(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í)候更多杏节，但是遞歸往往也會寫出不同風(fēng)格的版本，所以我們一起來看下多個(gè)風(fēng)格的遞歸版本和迭代版本的實(shí)現(xiàn)，多種代碼對比會讓我們理解更深刻奋渔。
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è)元素相遇叨橱，這種情況在代碼中是不會出現(xiàn)的邻奠，因?yàn)橥鈱酉拗屏薸!=j劫拗，圖中之所以放到一起是為了直觀表達(dá)終止條件阅羹。
3.2.2 C++版本二過程演示
分析一下:
個(gè)人覺得這個(gè)版本雖然同樣使用D&C思想但是更加簡潔勺疼，從動畫可以看到選擇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ì)從兩翼會和，并且在會和過程中消滅敵人有生力量(認(rèn)為是交換元素)递鹉，直到兩路大軍會師盟步。
此時(shí)再將統(tǒng)帥王座擺到正確的位置，此過程中沒有統(tǒng)帥王座的反復(fù)變換躏结，只有最終會師的位置却盘，以王座位中心形成了左翼子序列和右翼子序列，再重復(fù)相同的過程媳拴，直至完成大一統(tǒng)黄橘。
腦補(bǔ)不過癮 于是湊圖一張:
3.3 多種遞歸版本說明
雖然快排的遞歸版本是基于D&C實(shí)現(xiàn)的，但是由于pivot值的選擇不同屈溉、交換方式不同等諸多因素塞关，造成了多種版本的遞歸代碼。
并且內(nèi)層while循環(huán)里面判斷>=還是>(即是否等于的問題)子巾，外層循環(huán)判斷本序列循環(huán)終止條件等寫法都會不同帆赢，因此在寫快排時(shí)切忌死記硬背，要不然邊界條件判斷不清楚很容易就死循環(huán)了砰左。
看下上述我貼的兩個(gè)版本的代碼核心部分：
另外在網(wǎng)上很多大神的博客里面還進(jìn)行了多種模式的快排：單軸模式匿醒、雙向切分场航、三項(xiàng)切分缠导、多基準(zhǔn)值等新花樣，感興趣可以參考快速排序算法的多種實(shí)現(xiàn)溉痢。
其實(shí)無論哪種寫法都需要明確知道自己是交換僻造、還是覆蓋、基準(zhǔn)值選取位置孩饼、>=和<=的等號問題髓削、循環(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)用層級過深需要保存的臨時(shí)結(jié)果和關(guān)系會非常多沐飘，進(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)獎得主發(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(n2)級別，并不是遞歸過程全都挑選了最值作為基準(zhǔn)值才會出現(xiàn)O(n2)的復(fù)雜度对湃，復(fù)雜度是一個(gè)概率化的期望值崖叫，具體的系數(shù)不同影響也很大。
4.3 基準(zhǔn)值選取優(yōu)化
**分割越均勻速度越快 **
從上面的幾張圖可以清晰看到基準(zhǔn)值的不同對于D&C過程的分割會產(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ū)遞歸會對大量重復(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)移動就可以了仓蛆，實(shí)際中分三種情況，這也是寫代碼的依據(jù)：
處理值e==p挎春，將e合并到等于區(qū)看疙，i++；
處理值e<p直奋，將e與(lt+1)位置的數(shù)據(jù)交換能庆，擴(kuò)展小于區(qū)lt++，等于區(qū)長度不變脚线，相當(dāng)于整體平移搁胆；
處理值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)化效果會非常明顯酱鸭。
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)事肱ⅰ（Introspection ）在心理學(xué)中兄旬，它是心理學(xué)基本研究方法之一。內(nèi)省法又稱自我觀察法余寥。它是發(fā)生在內(nèi)部的领铐，我們自己能夠意識到的主觀現(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ù)娜宋铩?/p>
拋開語境一味地對比孰好孰壞其實(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)但是由于某些原因快速排序會更快一些，當(dāng)遞歸過深分割嚴(yán)重不均勻情況出現(xiàn)時(shí)會退化為O(n^2)的復(fù)雜度邻辉，這時(shí)性能會打折扣溪王，這也就是快速排序的短處了。
堆排序 堆排序是快速排序的有力競爭者值骇，最大的特點(diǎn)是可以到達(dá)O(nlogn)并且復(fù)雜度很穩(wěn)定莹菱，并不會像快速排序一樣可能退化為O(n^2)，但是堆排序過程中涉及大量堆化調(diào)整吱瘩，并且元素比較是跳著來的對Cache的局部性特征利用不好道伟，以及一些其他的原因?qū)е露雅判虮瓤焖倥判蚋稽c(diǎn)，但是大O復(fù)雜度仍然是一個(gè)級別的使碾。
插入排序 插入排序的一個(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)度使這三種排序算法的：
啟動階段 面對大量的待排序元素怜械，首先使用快速排序進(jìn)行大刀闊斧排序颅和，復(fù)雜度可以在O(nlogn)運(yùn)行
深入階段 在快速排序使用遞歸過程中傅事，涉及棧幀保存切換等諸多遞歸的操作，如果分區(qū)切割不當(dāng)遞歸過深可能造成棧溢出程序終止峡扩，因此如果快速排序過程中退化為O(n^2)蹭越，此時(shí)會自動檢測切換為堆排序，因?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那就才會繼續(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)父丰，再來評論吧肝谭，不過這種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ū)間移動
*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也是一種整體移動的優(yōu)化赢赊，避免了one by one的調(diào)整移動，底層調(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)和目的用途域携，展開起來會很細(xì)致，所以后面想著單獨(dú)在寫插入排序時(shí)單獨(dú)拿出了詳細(xì)學(xué)習(xí)一下鱼喉。
6.寫在最后
忙碌的日子里自己的時(shí)間就變得很少秀鞭，然后開始思考未來趋观，其實(shí)這樣并不好。
不多說了锋边，感謝各位讀者的傾情閱讀皱坛，筆芯你們。
