快速排序

快速排序是已知最快的基於比較的排序演算法（平均而言，對於大量元素），需要 步。快速排序是一種遞迴演算法，它首先根據幾個規則（Sedgewick 1978）對陣列 進行分割槽

1. 某個鍵 在陣列中的最終位置（即，如果它是第 個最小的，它在位置 ）。

2. 所有在 左側的元素都小於或等於 。元素 、、...、 被稱為“左子檔案”。

3. 所有在 右側的元素都大於或等於 。元素 、...、 被稱為“右子檔案”。

快速排序由 Hoare (1961, 1962) 發明，經過了廣泛的分析和審查 (Sedgewick 1975, 1977, 1978)，並且已知比次快的排序演算法快大約兩倍。然而，在最壞的情況下，快速排序是一種慢速的 演算法（對於快速排序，“最壞情況”對應於已經排序）。

演算法對隨機順序排列的 個專案列表進行排序的平均時間 由遞迴方程給出

(1)

其中 (Havil 2003, p. 129)。這個遞迴可以改寫為

(2)

其解為

(3)

其中 是調和數。對於 , 1, ...，前幾個值是 0, 1, 3, 17/3, 53/6, 62/5, 163/10, ... (OEIS A093418 和 A096620)。

這具有漸近行為

(4)

其中 是尤拉-馬歇羅尼常數，這意味著 (Havil 2003, p. 130)。