CS61B 课程笔记（Lecture 34 More Quick Sort, Stability, Shuffling)

1. 快速排序的基本概念

• 定义：快速排序是一种分治法的排序算法，基于选择一个“枢轴”元素，并将数组分为两部分，左侧小于等于枢轴，右侧大于枢轴。
• 基本步骤：
  1. 选择枢轴（通常选择最左边的元素）。
  2. 划分数组，使得左侧元素均小于或等于枢轴，右侧元素均大于枢轴。
  3. 递归地对左、右子数组进行快速排序。

2. 快速排序的性能分析

• 最优情况：当每次划分均匀，时间复杂度为 (\(\Theta(N \log N)\))。
• 最坏情况：当数组已排序或全为重复元素时，时间复杂度为 (\(\Theta(N^2)\))。
• 影响因素：
  • 枢轴选择的质量
  • 输入数组的特性

3. 避免最坏情况的策略

3.1 引入随机性

• 随机选择枢轴：随机选择一个元素作为枢轴，降低最坏情况发生的概率。
• 数组洗牌：在排序前随机打乱数组，以避免已排序或重复元素的影响。

3.2 智能枢轴选择

• 常数时间的选择：选择几个元素，选出“最佳”作为枢轴。
• 线性时间的选择：使用“精确中位数快速排序”算法，找到中位数作为枢轴，确保每次划分的有效性。

3.3 自省算法

• 在递归深度达到某个阈值时，切换到其他排序算法（如归并排序）。

4. 快速排序的变种

4.1 快速排序 L3S

• 特性：选择最左边的枢轴，洗牌数组。
• 性能：比归并排序略差。

4.2 快速排序 LTHS

• 特性：采用Tony Hoare的就地划分方案。
• 性能：可以获得更好的快速排序效果。

4.3 精确中位数快速排序

• 使用“快速选择”算法在线性时间内识别中位数。
• 性能：在最坏情况下为 (\(\Theta(N^2)\))，但预期运行时间为 (\(\Theta(N)\))。

5. 快速选择算法

• 目标：通过划分找到中位数。
• 过程：
  1. 初始化数组，选择最左边的项为枢轴。
  2. 划分数组，找到中位数的索引。
  3. 根据中位数的位置决定继续划分的方向。

6. 总结

• 快速排序：
  • 有多种变种可供选择。
  • 随机化与智能枢轴选择是改善性能的关键。
• 快速选择：
  • 预期运行时间为 (\(\Theta(N)\))，但最坏情况为 (\(\Theta(N^2)\))。