在雙向迭代器上實現快速排序

Question

使用具有O（NlgN）時間和O（lgN）空間的雙向迭代器來實現快速排列似乎非常簡單。那麼，std::sort()需要隨機訪問迭代器的具體原因是什麼？

我已閱讀過有關主題why do std::sort and partial_sort require random-access iterators?。但是它沒有解釋可能需要隨機訪問迭代器來保持其時間和空間複雜度的可能的實現的具體部分。

一種可能實現與O（NlgN）時間和O（LGN）空間：

template <typename BidirIt, typename Pred> 
BidirIt partition(BidirIt first, BidirIt last, Pred pred) { 
    while (true) { 
    while (true) { 
     if (first == last) return first; 
     if (! pred(*first)) break; 
     ++first; 
    } 
    while (true) { 
     if (first == --last) return first; 
     if (pred(*last)) break; 
    } 
    iter_swap(first, last); 
    ++first; 
    } 
} 

template <typename BidirIt, typename Less = std::less<void>> 
void sort(BidirIt first, BidirIt last, Less&& less = Less{}) { 
    using value_type = typename std::iterator_traits<BidirIt>::value_type; 
    using pair = std::pair<BidirIt, BidirIt>; 
    std::stack<pair> stk; 
    stk.emplace(first, last); 
    while (stk.size()) { 
    std::tie(first, last) = stk.top(); 
    stk.pop(); 
    if (first == last) continue; 
    auto prev_last = std::prev(last); 
    auto pivot = *prev_last; 
    auto mid = ::partition(first, prev_last, 
     [=](const value_type& val) { 
     return val < pivot; 
     }); 
    std::iter_swap(mid, prev_last); 
    stk.emplace(first, mid); 
    stk.emplace(++mid, last); 
    } 
} 

Answer 1

爲什麼有實用庫排序函數需要隨機訪問迭代器的幾個原因。

最明顯的一個是衆所周知的事實，即如果數據被排序（或「大多數排序」），選擇數據透視分區的端點將快速排序減少到O，所以最真實生活quicksort實際上使用更強大的算法。我認爲最常見的是Wirth算法：選擇分區的第一個，中間和最後一個元素的中值，這對分類的向量是強健的。 （正如DieterKühl所指出的那樣，只選擇中間元素幾乎同樣可行，但對於三元中值算法實際上沒有額外的成本）。選擇一個隨機元素也是一個好策略，因爲它更難到遊戲，但是對PRNG的要求可能令人沮喪。除了採用端點以外，任何選擇樞軸的策略都需要隨機訪問迭代器（或線性掃描）。

其次，當分區很小時（對於一些小的啓發式定義），quicksort是次優的。當沒有足夠的元素時，插入排序的簡化循環與參考位置結合在一起將會成爲更好的解決方案。 （這不會影響整體算法的複雜性，因爲閾值是固定大小;對於任何先前建立的k，插入排序的最大值爲k。我認爲您通常會發現值介於10和30.）插入排序可以使用雙向迭代器完成，但要弄清楚分區是否小於閾值不能（再次說明，除非使用不必要的慢循環）。不管你怎麼努力，快速排序都可以退化爲O（n ）。第三種也可能是最重要的，快速排序可以簡併成O（n ）。早期的C++標準認爲std::sort的平均值可能是「O（n log n）」，但自從接受DR713以來，該標準要求std::sort爲沒有資格的O（n log n）。這不能用純快速排序來實現，所以現代的圖書館排序算法實際上是基於introsort或類似的。如果該算法檢測到分區太偏見，則該算法回退到不同的排序算法 - 通常是堆排序算法。後備算法很可能需要隨機訪問迭代器（例如，heapsort和shellort都可以）。

最後，遞歸深度可以通過使用遞歸最小分區和尾部循環（顯式循環）的簡單策略，將遞歸深度減少到最大值log n。由於遞歸通常比顯式維護堆棧要快，並且如果最大遞歸深度是低兩位數字，遞歸是完全合理的，這個小小的優化是值得的（儘管並非所有的庫實現都使用它）。同樣，這需要能夠計算分區的大小。

有可能需要隨機訪問迭代器實用分揀的其他方面;那些只是我的頭頂。

Answer 2

簡單的答案是，除非特別針對小範圍優化，否則quicksort速度較慢。要檢測範圍很小，需要確定其大小的有效方法。

我有一個演示文稿（here are the slides and the code），我展示用於創建快速實現快速排序的步驟。事實證明，排序實現實際上是一種混合算法。

在使quicksort快速的基本步驟如下：

1. 提防[大多]排序序列。這裏有趣的情況之一實際上是由所有相同元素組成的特殊排序序列：在實際數據中，相同的子序列根本不是罕見的。這樣做的方法是監視快速排序做了太多工作並切換到已知複雜度的算法（如heapsort或mergesort）以完成排序有問題的子序列。這種方法的名稱是introsort。
2. Quicksort在短序列上真的很差。由於快速排序是一個divide and conquer algorithm它實際上產生許多小序列。處理小序列可以例如使用insertionsort來完成。爲了找出序列是否很小，有必要有效地檢查序列的大小。這是需要隨機訪問的用武之地。

3. 有一些額外的優化，雖然他們的影響比上述方法的影響較小整體所必需的使快速排序真快。例如：

   • 使用的分區需要利用標記來減少比較次數。
   • 觀察分區是否做了任何工作可以通過賭博運行insertionsort來提早紓困，這會在做太多工作時停止。
   • 要使用，而不是作爲樞軸有一個優點要排序的序列的任一末端的中點增加前一個點的可能性（這也需要隨機存取，但是是比較小的原因）。

我沒有做過實驗，但實施這些必要的優化爲雙向迭代器可能不是真正有效：確定成本的序列是否是小（這並不需要得到的大小序列，但只要明確序列不是很小就可以停止）可能會變高。如果快速排序的運行速度減慢大約20％，則優選使用不同的排序算法：使用例如mergesort大致在該範圍內並且可以具有穩定的優點。

順便說一句，中位數作爲一個關鍵點的傳說中的選擇似乎沒有任何有趣的影響：使用中間值而不是中位數似乎大致一樣好（但它的確是一個更好的選擇，結束）。