排序

堆排序

时间

• 最差：$O(n\log n)$

算法过程

• $\text{MAX-HEAPIFY}(A,i)$：每次把 $i$ 与儿子中较大的交换，然后递归那个较大的儿子
• $\text{BUILD-MAX-HEAP}(A)$：自底向上对每个非叶节点做 $\text{MAX-HEAPIFY}$。时间复杂度 $O(n)$
• $\text{HEAP-INCREASE-KEY}(A,i,key)$：直接修改，然后向上移动

快速排序

时间

• 平均：$O(n\log n)$
• 最差：$O\left(n^2\right)$
• 随机化的期望时间：$O(n\log n)$

算法过程

找主元，划分，然后递归两边。

• $\text{PARTITION}(A,p,r)$：永远选择 $a_r$ 作为主元，$p$ 表示左边界

计数排序

时间

$\Theta (n+U)$，其中 $U$ 是值域。

是稳定排序。

LSD 基数排序

时间

$\Theta (m(n+U))$，$m$ 表示位数，$U$ 表示每一位的值域。

算法过程

从低到高分别按照每一位使用计数排序排序整个数组。

桶排序

时间

期望 $O(n)$。

算法过程

把值域均匀映射到若干个桶里，然后在每个桶里用其他的方法排序。每个桶的元素个数的期望是 $O(1)$。