圖解 | 從武俠角度探究STL排序算法的奧秘
本文轉載自微信公眾號「后端研究所」，作者大白斯基。轉載本文請聯系后端研究所公眾號。
前言
今天來看一下STL中的sort算法的底層實現和代碼技巧。
眾所周知STL是借助于模板化來支撐數據結構和算法的通用化，通用化對于C++使用者來說已經很驚喜了，但是如果你看看STL開發者強大的陣容就意識到STL給我們帶來的驚喜絕不會止步于通用化，強悍的性能和效率是STL的更讓人驚艷的地方。
STL極致表現的背后是大牛們爐火純青的編程技藝和追求極致的工匠精神的切實體現。
筆者能力所限，只能踏著前人的肩膀來和大家一起看看STL中sort算法的背后究竟隱藏著什么，是不是有種《走進科學》的既視感，讓我們開始今天的sort算法旅程吧!
內省式哲學
在了解sort算法的實現之前先來看一個概念：內省式排序，說實話筆者的語文水平確實一般，對于這個詞語用在排序算法上總覺得不通透，那就研究一下吧!
內省式排序英文是Introspective Sort，其中單詞introspective是內省型的意思，還是不太明白，繼續搜索，看一下百度百科對這個詞條的解釋：
內省(Introspection )在心理學中，它是心理學基本研究方法之一。內省法又稱自我觀察法。它是發生在內部的，我們自己能夠意識到的主觀現象。也可以說是對于自己的主觀經驗及其變化的觀察。
正因為它的主觀性，內省法自古以來就成為心理學界長期的爭論。另外內省也可看作自我反省，也是儒家強調的自我思考。從這個角度說可以應用于計算機領域，如Java內省機制和cocoa內省機制。
好家伙，原來內省是個心理學名詞，到這里筆者有些感覺了，內省就是自省、自我思考、根據自己的主觀經驗來觀察變化做出調整，而不是把希望寄托于外界，而是自己的經驗和能力。
通俗點說，內省算法不挑數據集，盡量針對每種數據集都能給定對應的處理方法，讓排序都能有時間保證。
寫到這里，讓筆者腦海浮現了《倚天屠龍記》里面張無忌光明頂大戰六大門派的場景，無論敵人多么強悍或者羸弱，我都按照自己的路子應對。
他強由他強，清風拂山崗;
他橫由他橫，明月照大江;
他自狠來他自惡，我自一口真氣足。
---《九陽真經》達摩
哲學啊，確實這樣的，我們切換到排序的角度來看看內省是怎么樣的過程。
筆者理解的內省式排序算法就是不依賴于外界數據的好壞多寡，而是根據自己針對每種極端場景下做出相應的判斷和決策調整，從而來適應多種數據集合展現出色的性能。
內省式排序
俗話說俠者講究刀、槍、劍、戟、斧、鉞、鉤、叉等諸多兵器，這也告訴我們一個道理沒有哪種兵器是無敵的，只有在某些場景下的明顯優勢，這跟軟件工程沒有銀彈是一樣的。
回到我們的排序算法上，排序算法也可謂是百花齊放：冒泡排序、選擇排序、插入排序、快速排序、堆排序、桶排序等等。
雖然一批老一輩的排序算法是O(n^2)的，優秀的算法可以到達O(nlogn)，但是即使都是nlogn的快速排序和堆排序都有各自的長短之處，插入排序在數據幾乎有序的場景下性能可以到達O(n)，有時候我們應該做的不是沖突對比而是融合創新。
內省排序是由David Musser在1997年設計的排序算法。這個排序算法首先從快速排序開始，當遞歸深度超過一定深度(深度為排序元素數量的對數值)后轉為堆排序,David Musser大牛是STL領域響當當的人物。
拋開語境一味地對比孰好孰壞其實都沒有意義，內省式排序就是集大成者，為了能讓排序算法達到一個綜合的優異性能，內省式排序算法結合了快速排序、堆排序、插入排序，并根據當前數據集的特點來選擇使用哪種排序算法，讓每種算法都展示自己的長處，這種思想確實挺啟發人的。
內省排序的排兵布陣
前面提到了內省式排序主要結合了快速排序、堆排序、插入排序，那么不禁要問，這三種排序是怎么排兵布陣的呢?
知己知彼百戰不殆，所以先看下三種排序的優缺點吧!
快速排序
在大量數據時無論是有序還是重復，使用優化后的算法大多可以到達O(nlogn)，雖然堆排序也是O(nlogn)但是由于某些原因快速排序會更快一些，當遞歸過深分割嚴重不均勻情況出現時會退化為O(n^2)的復雜度，這時性能會打折扣，這也就是快速排序的短處了。
堆排序
堆排序是快速排序的有力競爭者，最大的特點是可以到達O(nlogn)并且復雜度很穩定，并不會像快速排序一樣可能退化為O(n^2)，但是堆排序過程中涉及大量堆化調整，并且元素比較是跳著來的對Cache的局部性特征利用不好，以及一些其他的原因導致堆排序比快速排序更慢一點，但是大O復雜度仍然是一個級別的。
插入排序
插入排序的一個特點是就像我們玩紙牌，在梳理手中的牌時，如果已經比較有序了，那么只需要做非常少的調整即可，因此插入排序在數據量不大且近乎有序的情況下復雜度可以降低到O(n)，這一點值得被應用。
優缺點也大致清楚了，所以可以猜想一下內省式排序在實際中是如何調度使這三種排序算法的：
- 啟動階段 面對大量的待排序元素，首先使用快速排序進行大刀闊斧排序，復雜度可以在O(nlogn)運行
- 深入階段 在快速排序使用遞歸過程中，涉及棧幀保存切換等諸多遞歸的操作，如果分區切割不當遞歸過深可能造成棧溢出程序終止，因此如果快速排序過程中退化為O(n^2)，此時會自動檢測切換為堆排序，因為堆排序沒有惡化情況，都可以穩定在O(nlogn)
- 收尾階段 在經過快排和堆排的處理之后，數據分片的待排序元素數量小于某個經驗設定值(可以認為是遞歸即將結束的前幾步調用)時，數據其實已經幾乎有序，此時就可以使用插入排序來提高效率，將復雜度進一步降低為O(n)。
寫到這里，筆者又天馬行空地想到了一個場景：
2005年春晚小品中黃宏和鞏漢林出演的《裝修》中黃宏作為裝修工人手拿一大一小兩把錘子，大錘80小錘40，大小錘頭切換使用。
其實跟內省排序切換排序算法是一個道理，所以技術源于生活又高于生活，貼圖一張大家一起體會一下：
用了很多篇幅來講內省思想和內省式排序，相信大家也已經get到了，所以我們具體看下實現細節，這個才是本文的重點，我們繼續往下一起分析吧!
sort算法的實現細節
本文介紹的sort算法是基于SGI STL版本的，并且主要是以侯捷老師的《STL源碼剖析》一書為藍本來進行展開的，因此使用了不帶仿函數的版本，讓我們來一起領略大牛們的杰作吧!圖為筆者買了很久卻一直壓箱底的STL神書：
sort函數的應用場景
SGI STL中的sort的參數是兩個隨機存取迭代器RandomAccessIterator，sort的模板也是基于此種迭代器的，因此如果容器不是隨機存取迭代器，那么可能無法使用通用的sort函數。
- 關聯容器 map和set底層是基于RB-Tree，本身就已經自帶順序了，因此不需要使用sort算法
- 序列容器 list是雙向迭代器并不是隨機存取迭代器，vector和deque是隨機存取迭代器適用于sort算法
- 容器適配器 stack、queue和priority-queue屬于限制元素順序的容器，因此不適用sort算法。
綜上我們可以知道，sort算法可以很好的適用于vector和deque這兩種容器。
sort總體概覽
前面介紹了內省式排序，所以看下sort是怎么一步步來使用introsort的，上一段入口代碼：
- template <class RandomAccessIterator>
- inline void sort(RandomAccessIterator first, RandomAccessIterator last) {
- if (first != last) {
- __introsort_loop(first, last, value_type(first), __lg(last - first) * 2);
- __final_insertion_sort(first, last);
- }
- }
從代碼來看sort使用了first和last兩個隨機存取迭代器，作為待排序序列的開始和終止，進一步調用了__introsort_loop和__final_insertion_sort兩個函數，從字面上看前者是內省排序循環，后者是插入排序。其中注意到__introsort_loop的第三個參數__lg(last - first)*2，憑借我們的經驗來猜(蒙)一下吧，應該遞歸深度的限制，不急看下代碼實現：
- template <class Size>
- inline Size __lg(Size n){
- Size k;
- for(k = 0;n > 1;n >>= 1) ++k;
- return k;
- }
這段代碼的意思就是n=last-first，2^k<=n的最大整數k值。
所以整體看當假設last-first=20時，k=4,最大分割深度depth_max=4*2=8，從而我們就可以根據first和last來確定遞歸的最大深度了。
快速排序和堆排序的配合 __introsort_loop函數中主要封裝了快速排序和堆排序，來看看這個函數的實現細節：
- //sort函數的入口
- template <class RandomAccessIterator, class T, class Size>
- void __introsort_loop(RandomAccessIterator first,
- RandomAccessIterator last, T*,
- Size depth_limit) {
- while (last - first > __stl_threshold) {
- if (depth_limit == 0) {
- partial_sort(first, last, last);//使用堆排序
- return;
- }
- --depth_limit;//減分割余額
- RandomAccessIterator cut = __unguarded_partition
- (first, last, T(__median(*first, *(first + (last - first)/2),
- *(last - 1))));//三點中值法分區過程
- __introsort_loop(cut, last, value_type(first), depth_limit);//子序列遞歸調用
- last = cut;//迭代器交換 切換到左序列
- }
- }
- //基于三點中值法的分區算法
- template <class RandomAccessIterator, class T>
- RandomAccessIterator __unguarded_partition(RandomAccessIterator first,
- RandomAccessIterator last,
- T pivot) {
- while (true) {
- while (*first < pivot) ++first;
- --last;
- while (pivot < *last) --last;
- if (!(first < last)) return first;
- iter_swap(first, last);
- ++first;
- }
各位先不要暈更不要蒙圈，一點點分析肯定可以拿下的。
- 先看參數兩個隨機存取迭代器first和last，第三個參數是__lg計算得到的分割深度;
- 這時候我們進入了while判斷了last-first的區間大小，__stl_threshold為16，侯捷大大特別指出__stl_threshold的大小可以是5~20，具體大小可以自己設置，如果大于__stl_threshold那就才會繼續執行，否則跳出;假如現在區間大小大于__stl_threshold，判斷第三個參數depth_limit是否為0，也就是是否出現了分割過深的情況，相當于給了一個初始最大值，然后每分割一次就減1，直到depth_limit=0，這時候調用partial_sort，從《stl源碼剖析》的其他章節可以知道，partial_sort就是對堆排序的封裝，看到這里有點意思了主角之一的heapsort出現了;
- 繼續往下看，depth_limit>0 尚有分割余額，那就燥起來吧!這樣來到了__unguarded_partition，這個函數從字眼看是快速排序的partiton過程，返回了cut隨機存取迭代器，__unguarded_partition的第三個參數__median使用的是三點中值法來獲取的基準值Pivot，至此快速排序的partition的三個元素集齊了，最后返回新的切割點位置;
- 繼續看馬上搞定啦，__introsort_loop出現了，果然遞歸了，特別注意一下這里只有一個遞歸，并且傳入的是cut和last，相當于右子序列，那左子序列怎么辦啊?別急往下看，last=cut峰回路轉cut變成了左子序列的右邊界，這樣就開始了左子序列的處理;
快速排序的實現對比
前面提到了在sort中快速排序的寫法和我們之前見到的有一些區別，看了一下《STL源碼剖析》對快排左序列的處理，侯捷老師是這么寫的："寫法可讀性較差，效率并沒有比較好"，看到這里更蒙圈了，不過也試著分析一下吧!
圖為：STL源碼剖析中侯捷老師對該種寫法的注釋
常見寫法：
- //快速排序的常見寫法偽代碼
- quicksort(arr,left,right){
- pivoit = func(arr);//使用某種方法獲取基準值
- cut = partition(left,right,pivot);//左右邊界和基準值來共同確定分割點位置
- quicksort(arr,left,cut-1);//遞歸處理左序列
- quicksort(arr,cut+1,right);//遞歸處理右序列
- }
SGI STL中的寫法:
- stl_quicksort(first,last){
- //循環作為外層控制結構
- while(ok){
- cut = stl_partition(first,last,_median(first,last));//分割分區
- stl_quicksort(cut,last);//遞歸調用 處理右子序列
- last = cut;//cut賦值為last 相當于切換到左子序列 再繼續循環
- }
- }
網上有一些大佬的文章說sgi stl中快排的寫法左序列的調用借助了while循環節省了一半的遞歸調用，是典型的尾遞歸優化思路。
這里我暫時還沒有寫測試代碼做對比，先占坑后續寫個對比試驗，再來評論吧，不過這種sgi的這種寫法可以看看哈。
堆排序的細節
- //注：這個是帶自定義比較函數的堆排序版本
- //堆化和堆頂操作
- 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達到__stl_threshold閾值之后，可以認為數據集近乎有序了，此時就可以通過插入排序來進一步提高排序速度了，這樣也避免了遞歸帶來的系統消耗，看下__final_insertion_sort的具體實現：
- 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的實現細節吧:
- 引入參數隨機存取迭代器first和last
- 如果last-first > __stl_threshold不成立就調用__insertion_sort，這個相當于元素數比較少了可以直接調用，不用做特殊處理;
- 如果last-first > __stl_threshold成立就進一步再分割成兩部分，分別調用__insertion_sort和__unguarded_insertion_sort，兩部分的分割點是__stl_threshold，不免要問這倆函數有啥區別呀?
__insertion_sort的實現
- //逆序對的調整
- 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);//區間移動
- *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));
- }
在插入函數中同樣出現了__unguarded_xxx這種形式的函數，unguarded單詞的意思是無防備的，無保護的，侯捷大大提到這種函數形式是特定條件下免去邊界檢驗條件也能正確運行的函數。
copy_backward也是一種整體移動的優化，避免了one by one的調整移動，底層調用memmove來高效實現。
__unguarded_insertion_sort的實現
- 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));
- }
關于插入排序的這兩個函數的實現和目的用途，展開起來會很細致，所以后面想著單獨在寫插入排序時單獨拿出了詳細學習一下，所以本文就暫時先不深究了，感興趣的讀者可以先行閱讀相關資料，后續我們再共同辯駁哈!
總結
本文主要闡述了內省式排序的思想和基本實現思路，并且以此為切入點對sgi stl中sort算法的實現來進行了一些解讀。
stl的作者們為了追求極致性能所以使用了大量的技巧，對此本文并沒有過多展開，也主要是段位不太高怕解讀錯了，聰明的讀者們可以嘗試來剖析一探大牛們的巔峰技藝。
