算法 — sort · STL源碼分析

能使用STL的sort系列算法的前提是容器的迭代器必須為隨機迭代器。所以，vector和deque天然適用。STL的sort算法采用了一些策略，在不同情況下采用不同的排序算法，以達到各種算法優勢互補的效果。基本的原則是：數據量大時采用快速排序，數據量小時采用插入排序（這是對快排常用的一種優化策略），遞歸層次過深改用堆排序。首先是插入排序。它的平均和最壞時間復雜度都為O(N2)，量級小于千，那么插入排序還是一個不錯的選擇。SGI STL的插入排序默認以增序排列，另外還可以傳入一個仿函數作為比較規則，這里只說明前者。外層循環確定一個子區間，i位置的元素需要插入到已排序區間的正確位置上： ~~~ 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)); } ~~~ 進入__linear_insert函數： ~~~ 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); } ~~~ 上面代碼的注釋已經說明了一種簡單的情況，這是只需借用copy_backward算法將元素整體搬移，以騰出第一個位置給新插入元素。但其它情況下就要進入__unguarded_linear_insert函數了： ~~~ 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; // 新元素放入正確位置 } ~~~ 上述函數的目標就是要找到value也就是新插入元素的正確插入位置。以value位置為起點，前向遍歷已排序區間，遇到比value大的就后移一個位置，以消除逆轉對的存在。注意，這里不需要進行越界判斷，因為value肯定不會插入到區間頭部。當遇到大數據量時，效率為平方級的插入排序就不適用了。這時STL改用快速排序，平均效率為O(NlogN)，最壞效率為O(N2)。快排首先要選取樞軸，STL采用的方法是選取前、中、后三點的中值作為樞軸。接下來是分割，遍歷整個迭代器，小于樞軸的放左邊，大于樞軸的放右邊。具體做法如下： - first迭代器向后移動，*first大于或等于樞軸時停止。 - last迭代器向前移動，*last小于或等于樞軸時停止。 - 若first仍在last的左邊，則交換*first和*last，并調整兩個迭代器指向下一個位置。 - 重復上述行為直到first和last交叉，first即為右半部分起始位置。分割代碼如下： ~~~ template <class RandomAccessIterator, class T> // 快排的分割函數 RandomAccessIterator __unguarded_partition(RandomAccessIterator first, RandomAccessIterator last, T pivot) { while (true) { while (*first < pivot) ++first; // 向后移動直到*first大于或等于樞軸 --last; while (pivot < *last) --last; // 向前移動直到*last小于或等于樞軸 if (!(first < last)) return first; // 交叉后停止，返回的迭代器作為右子區間的開頭 iter_swap(first, last); // 交換兩個迭代器所指元素 ++first; } } ~~~ 現在來看看sort算法的對外接口： ~~~ 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); } } ~~~ 要閱讀__introsort_loop函數，先要了解introsort。以下是維基百科里的解釋：內省排序（英語：Introsort）是由David Musser在1997年設計的排序算法。這個排序算法首先從快速排序開始，當遞歸深度超過一定深度（深度為排序元素數量的對數值）后轉為堆排序。采用這個方法，內省排序既能在常規數據集上實現快速排序的高性能，又能在最壞情況下仍保持O(nlogn)的時間復雜度。個人理解，最壞情況發生在分割深度過深時，以中值作為樞軸的方法并不能選出合適的樞軸，導致分割時頻繁地交換元素，使效率下降到O(N)。上述代碼中的__lg(last - first) * 2就是根據元素個數計算深度閾值，當分割深度超過閾值時，轉而采用堆排序，是效率繼續保持為O(nlogn)。 ~~~ template <class Size> inline Size __lg(Size n) { // 控制分割惡化的情況，求2^k <= n的最大k值 Size k; for (k = 0; n != 1; n >>= 1) ++k; return k; } ~~~ 例如，當元素個數為40時，最多允許分割10層。有了上面內省排序的基礎，下面的代碼就很容易看了： ~~~ template <class RandomAccessIterator, class T, class Size> void __introsort_loop(RandomAccessIterator first, RandomAccessIterator last, T*, Size depth_limit) { while (last - first > __stl_threshold) { // 大于某個值才進行快速排序，這里__stl_threshold = 16 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; // 調整last位置，下一次while循環將對左半部分排序 } } ~~~ partial_sort已經在另一篇文章中詳細分析過了，實際上就是對整個區間進行堆排序。__median函數就是求取前、中、后三個元素中值作為樞軸，其它函數都已經在上面講解過了。遞歸分段排序，典型的分治策略。當__introsort_loop函數返回時，要么完全已排序，要么大體已排序。大體已排序則要進行微調，即sort函數調用完__introsort_loop之后調用__final_insertion_sort進行微調： ~~~ template <class RandomAccessIterator> void __final_insertion_sort(RandomAccessIterator first, RandomAccessIterator last) { if (last - first > __stl_threshold) { // 超過16個元素，則分割為兩段 __insertion_sort(first, first + __stl_threshold); // 前段使用插入排序 __unguarded_insertion_sort(first + __stl_threshold, last); // 剩余元素逐個插入 } else __insertion_sort(first, last); // 元素個數不超過16，直接使用插入排序 } ~~~ 注意，為了效率，STL又開始折騰了...，再進入__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)); // 將i所指元素插入已排序的16個元素的序列中，前面已經介紹過了 } template <class RandomAccessIterator> inline void __unguarded_insertion_sort(RandomAccessIterator first, RandomAccessIterator last) { __unguarded_insertion_sort_aux(first, last, value_type(first)); } ~~~ 為什么要這樣？當從__introsort_loop函數返回時，要么完全有序，要么大體有序。大體有序時，前面的子區間整體是要小于后面的子區間的，這是introsort操作之后的結果。在__final_insertion_sort中，如果元素個數超過16，先對前16個元素進行插入排序，后面剩下的元素再逐個插入到此有序區間。剛才說了由于已經是大體有序了，所以逐個插入操作不會出現過多的逆轉對，這正是插入排序的優勢所在。至此，STL的sort算法分析完了。要讀懂STL的心思確實不是意見容易的事情啊。參考：《STL源碼剖析》 P389.