什麼是最快的快速排序 - 排序算法的排名表？

Question

我試圖優化我的quicksort性能。對於4M（整數項）（每個4字節），它需要一個並行快速排序算法0​​.5（0.499703）秒對可支持72個併發線程（72個核心）的系統進行排序。我有興趣瞭解有效的方法來進一步優化我的並行快速排序。另外，有興趣與其他排序算法進行比較，如果有所有排序算法的排名表，給定一定的工作量？

Answer 1

據我所知，沒有用於排序算法的規範排行榜。排序算法的性能取決於許多不同的因素 - 您獲得的輸入分佈，輸入的大小，編程語言的選擇，所用編譯器的類型和設置，核心數量，環境溫度房間，操作系統等。

至於你的其他問題 - 如何優化你的quicksort - 沒有看到你的代碼，很難說肯定。以下是您可能想要嘗試的常見快速排序優化列表。

1. 切換到小輸入更快排序：插入排序運行在二次時間，但對於小的投入也可以是多少，比快速排序更快。一旦排序元素的數量下降到某個閾值以下，快速排序實現切換到插入排序並不罕見，這可以顯着減少運行時間。

2. 添加內省。 Introsort是快速排序的快速變體，可以跟蹤遞歸深度並在看起來算法退化時切換到堆排序。這可以保證運行時間爲O（n log n），如果沒有觸發這種情況，只會產生很小的成本。

3. 使用更好的分區算法。雙樞軸快速排序最近出現在現場，作爲傳統分區算法的替代方案。它在許多輸入上有更好的表現。此外，如果您希望得到大量重複輸入，請考慮使用可正常處理重複元素的分區方案。

4. 介紹尾聲消除。許多快速排序實現爲需要排序的兩個子數組啓動兩個遞歸調用，但實際上並不需要這樣做。您可以觸發一個遞歸調用，然後將第二個調用作爲尾部調用，方法是將參數覆蓋到初始調用並將整個事件放入while循環中。