CS61B 课程笔记（DISC 13 More Sorting)

我们要使用稳定的 Quicksort 对以下未排序的列表进行排序，假设枢轴总是第一个元素，并且使用三路划分法来处理相等的元素。

未排序的列表：
$ 18, 7, 22, 34, 99, 18, 11, 4 $

步骤1：选择 18 作为枢轴

列表变为：
$ 7, 11, 4 | 18, 18 | 22, 34, 99 $

步骤2：对左边的子数组 $7, 11, 4$ 进行划分，选择 7 作为枢轴

列表变为：
$ 4 | 7 | 11 $

步骤3：对右边的子数组 $22, 34, 99$ 进行划分，选择 22 作为枢轴

列表变为：
$ 22 | 34, 99 $

最终排序结果：
$ 4, 7, 11, 18, 18, 22, 34, 99 $

Quicksort 的最坏情况运行时间是 ( $(n^2) $)。最坏情况下，如果每次选择的枢轴是最小或最大的元素，那么每次划分后数组只会减少一个元素，导致递归深度为 ( $n$ )，每层需要做 ( $O(n) $) 的工作，总体运行时间为：

$ 1 + 2 + + n = (n^2) $

示例：对于已经排序好的列表，例如 $1, 2, 3, 4, 5$，如果总是选择第一个或最后一个元素作为枢轴，Quicksort 的运行时间将是 ( $(n^2) $)。

Quicksort 的最好情况运行时间是 ( $(n n) $)。当每次选择的枢轴能够将数组均匀划分为两个大小相等的部分时，递归深度为 ( $n $)，每层需要做 ( $O(n)$ ) 的工作，因此总的时间复杂度为 ( $O(n n) $)。

你无法做得比这个更好，因为任何比较排序的下界都是 ( $\Omega(n \log n)$ )，这违反了排序的下界理论。

排序算法	时间复杂度	空间复杂度	稳定性
插入排序	($ (n^2)$ )	($ O(1)$ )	是
堆排序	($ (n n)$ )	($ O(1) $)	否
归并排序	( $(n n) \| O(n) $)	是
快速排序	( $\Theta(n \log n)$ )	( $O(n) $)	否

解释：

如果使用随机化的快速排序，任何数组都可能变得不稳定。

无论使用何种方法进行 heapification，都至少需要检查数组中的每个元素，以确保满足堆的性质。这需要线性时间 ($ O(n) $)。

自顶向下的 heapification 每次插入一个元素到堆中，每次插入操作的最坏时间是 ( $O(\log n)$ )，插入 ( $n$ ) 个元素的总时间是：

$ n O(n) = O(n n) $

这表明 heapification 的最优解的时间复杂度至多为 ( $O(n n) $)。

自底向上的 heapification 通过从数组的最后一个非叶子节点开始，逐步调整每个子堆的结构，使得堆的性质自下而上得到满足。由于在每一层，所需要调整的元素数目随着层数的增加逐渐减少，总体时间复杂度为 ( $O(n)$ )。

我们可以用公式 ( $_{i=0}^{n} $) 来表示 heapify 的工作量。每一层的元素数目大约是上一层的一半，而调整这些元素的工作量也逐渐减少，总体来说，其时间复杂度是线性的：

$ T(n) = O(n) $

因此，自底向上的 heapify 是 ( $(n) $) 的算法，它也是 heapification 问题的最优解。