CS61B 课程笔记（Lecture 33 Quick Sort)

1. 之前学习的排序算法

在学习快速排序之前，我们已经讨论了以下排序算法：

• 选择排序（Selection Sort）：找出最小的元素，将其放到前面。
• 堆排序（Heap Sort）：使用最大优先队列（MaxPQ）找到最大元素，将其放到最后。
• 归并排序（Merge Sort）：将两个已排序的部分合并成一个完整的排序。
• 插入排序（Insertion Sort）：确定当前元素插入的位置。

2. 快速排序的核心思想

快速排序的核心思想是划分（partitioning）。具体步骤如下：

1. 选择一个主元（pivot）：从数组中选择一个元素作为主元，例如 $x = a[i] $。
2. 划分过程：将数组重新排列，使得主元 \(x\) 移动到某个位置 $ j $，并满足以下条件：
   • 所有在 $x $ 左边的元素都小于或等于 $ x$ 。
   • 所有在 \(x\) 右边的元素都大于或等于 \(x\) 。

3. 快速排序算法

快速排序的步骤如下：

• 对于 $ N$ 个元素：
  1. 选择最左边的元素作为主元。
  2. 递归地对左半部分进行快速排序。
  3. 递归地对右半部分进行快速排序。

4. 快速排序的性能分析

快速排序在性能分析中需要考虑几个方面：

4.1 最优情况

• 最优情况发生在主元总是选在中间（即每次划分都能选中中位数）：
  • 每一层的工作量大约为 $ O(N)$ 。
  • 每一层的数量 \(H\) 大约为 \(\Theta(\log N)\) 。
  • 整体运行时间为 $(N N) $。

4.2 最坏情况

• 最坏情况发生在每次选择的主元都在数组的最前面，此时：
  • 每一层的工作量仍为 \(O(N)\) 。
  • 层数 \(H\) 为 $N $（每个元素都被选为主元）。
  • 整体运行时间为 $(N^2) $。

5. 快速排序与归并排序的性能对比

性能分析	快速排序	归并排序
最优情况	$ (N N)$	\(\Theta(N \log N)\)
最坏情况	$ (N^2) $	$(N N) $

虽然归并排序在理论上比快速排序更好，但快速排序在实际应用中通常表现得更快，原因包括：

• 快速排序在平均情况下的运行时间为 $ (N N) $。
• 快速排序在许多情况下的常数因素比归并排序小。

6. 避免快速排序的最坏情况

快速排序的性能受到主元选择的影响，以下是一些优化策略：

• 避免不良排序：在数组已经排好序（或几乎排好序）时，快速排序可能会表现出最坏情况的性能。
• 选择主元策略：选择随机主元或在排序前随机打乱数组可以帮助保证运行在平均情况下。

7. 总结

• 插入排序的优点：对于几乎已排序的数组，插入排序表现非常快，特别是当 $ N $ 较小（约 $ N $ ）。
• 划分的定义：划分是将数组重排，使得主元左边的元素都小于等于主元，右边的元素都大于等于主元。
• 快速排序的运行时间：在最优情况下为 \(\Theta(N \log N)\) ，在最坏情况下为 $(N^2) $。
• 主元选择的影响：主元选择策略对快速排序的性能有重大影响，应选择合适的方法来提高效率。