快速排序

快速排序是已知最快的基于比较的排序算法（平均而言，对于大量元素），需要 步。快速排序是一种递归算法，它首先根据几个规则（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)。