快速排序（Quick Sort）的平均时间复杂度和最坏情况时间复杂度分析

题目描述

快速排序的平均时间复杂度是 O(n log n)，最坏情况时间复杂度是 O(n²)。请详细解释为什么平均情况是 O(n log n)，以及什么情况下会出现最坏时间复杂度 O(n²)，并说明如何优化以避免最坏情况。

解题过程

1. 快速排序基本思想回顾

快速排序采用“分治法”（Divide and Conquer）：

• 选择一个基准元素（pivot）：从数组中选择一个元素作为基准。
• 划分（Partition）：重新排列数组，使得所有小于基准的元素放在基准左边，所有大于基准的元素放在基准右边。此时基准元素处于其最终正确位置。
• 递归排序：对基准左右两侧的子数组递归地应用快速排序。

2. 时间复杂度分析的基础

快速排序的性能关键取决于划分的平衡性：

• 每次划分后，如果基准能将数组分成两个大小大致相等的子数组，则递归深度为 O(log n)，每层总比较交换操作为 O(n)，总时间复杂度为 O(n log n)。
• 如果每次划分都极度不平衡（例如一个子数组大小为 n-1，另一个为 0），递归深度为 O(n)，每层总比较交换操作为 O(n)，总时间复杂度为 O(n²)。

3. 平均情况 O(n log n) 的详细推导

前提假设：数组元素随机排列，且基准选择是随机的（或采用首/中/尾元素等常见方法，在随机输入下划分结果期望平衡）。

推导过程：

1. 设 T(n) 为对 n 个元素排序的平均时间。
2. 每次划分的比较交换操作与 n 成正比，记为 c·n（c 为常数）。
3. 划分后，基准左侧有 k 个元素，右侧有 n-1-k 个元素（0 ≤ k ≤ n-1）。由于随机输入，k 在 0 到 n-1 之间均匀分布，每个 k 出现的概率为 1/n。
4. 递归方程：
   T(n) = c·n + (1/n) * Σ [T(k) + T(n-1-k)]，其中 Σ 对 k=0 到 n-1 求和。
5. 由于对称性，T(k) 和 T(n-1-k) 的期望相同，可化简为：
   T(n) = c·n + (2/n) * Σ T(k)，其中 Σ 对 k=0 到 n-1 求和。
6. 通过数学归纳法或递归树法可证明 T(n) = O(n log n)。直观理解：每次划分期望将数组分成比例固定的两部分（如 1:9），递归深度仍为 O(log n)；即使比例更差，只要划分是常数比例，深度仍为对数级。

举例说明：
假设数组长度 n=8，每次划分恰好分成两个长度 4 的子数组：

• 第 1 层：划分 8 个元素，操作 O(8)。
• 第 2 层：两个子数组各划分 4 个元素，总操作 O(4+4)=O(8)。
• 第 3 层：四个子数组各划分 2 个元素，总操作 O(2*4)=O(8)。
• 递归深度为 log₂8 = 3，每层总操作 O(8)，总操作 O(8 * 3) = O(24) ≈ O(n log n)。

4. 最坏情况 O(n²) 的出现条件

条件：每次划分都极度不平衡，即一个子数组包含 0 个元素，另一个包含 n-1 个元素。
常见场景：

1. 数组已完全有序（升序或降序），且选择第一个元素或最后一个元素作为基准。
2. 数组所有元素相同，且基准选择策略不处理重复值。

举例说明：
假设数组 [1, 2, 3, 4, 5]，选择第一个元素 1 为基准：

• 第 1 次划分：基准 1 左侧子数组为空，右侧为 [2,3,4,5]，操作 O(5)。
• 第 2 次划分：对 [2,3,4,5] 以 2 为基准，左侧为空，右侧为 [3,4,5]，操作 O(4)。
• 依此类推，总操作 = 5+4+3+2+1 = O(15) ≈ O(n²)。

5. 如何优化以避免最坏情况

目标：使划分尽可能平衡，保证平均 O(n log n)。
优化策略：

1. 随机选择基准：每次划分随机选择一个元素作为基准，可极大降低最坏情况概率。
2. 三数取中法：选择数组首、中、尾三个元素的中位数作为基准，有效避免已有序数组的最坏情况。
3. 小数组切换插入排序：当子数组长度小于阈值（如 10）时，改用插入排序，减少递归开销。
4. 三路划分：处理大量重复元素，将数组分为“小于基准”、“等于基准”、“大于基准”三部分，避免重复元素导致的不平衡。

代码示例（三数取中法选择基准）：

def choose_pivot(arr, low, high):
    mid = (low + high) // 2
    # 取 arr[low], arr[mid], arr[high] 的中位数索引
    candidates = [(arr[low], low), (arr[mid], mid), (arr[high], high)]
    candidates.sort(key=lambda x: x[0])
    return candidates[1][1]  # 返回中位数索引

6. 总结

• 平均 O(n log n)：基于随机输入和期望平衡划分，递归深度 O(log n)，每层 O(n)。
• 最坏 O(n²)：发生在每次划分极度不平衡时，如数组已有序且基准选择不当。
• 优化方法：随机化、三数取中、小数组插入排序、三路划分等，可避免最坏情况，在实际应用中快速排序效率很高。