快速排序的优化

快速排序的平均时间复杂度为 $O(n\log n)$，但在最坏情况下（如数组已有序）会退化为 $O(n^2)$。退化的根源在于枢轴选得太偏——每次划分只能剥掉一个元素，递归树退化成一条链。常见优化策略有三种。

思想：选取数组首、中、末三个元素，取其中位数作为枢轴（pivot），避免极端数据导致的最坏情况。

做法

• 设 low、high、$mid = (low+high)/2$
• 比较 a[low]、a[mid]、a[high]，将中位数交换到 a[low] 作为 pivot
• 然后正常执行 partition

效果：对已有序或逆序数组，pivot 接近中位值，避免 $O(n^2)$ 退化。

思想：随机选取一个元素作为枢轴，从概率上避免最坏情况。

做法

• 在 [low, high] 范围内随机生成一个下标 randIdx
• 将 a[randIdx] 与 a[low] 交换
• 然后正常执行 partition

效果：期望时间复杂度仍为 $O(n\log n)$，最坏情况概率极低。

思想：当子数组规模较小时，递归开销反而大于排序本身，此时切换为插入排序更高效。

做法

• 设定阈值 THRESHOLD（通常 10~20）
• 当 high - low + 1 <= THRESHOLD 时，调用插入排序
• 否则继续递归快排

效果：减少递归深度和函数调用开销，实际运行速度提升明显。

例 1：三数取中选取 pivot

数组：[10, 3, 15, 7, 8, 23, 9]

• $low=0$，$high=6$，$mid=3$
• a[low]=10，a[mid]=7，a[high]=9
• 中位数为 9（$7 < 9 < 10$）
• 将 a[high]=9 与 a[low]=10 交换 → [9, 3, 15, 7, 8, 23, 10]
• 以 9 为 pivot 进行 partition

partition 过程（Lomuto 方案）：

i = low = 0, pivot = 9
j=1: a[1]=3  < 9  → i=1, swap a[1],a[1]  → 不变
j=2: a[2]=15 > 9  → 跳过
j=3: a[3]=7  < 9  → i=2, swap a[2],a[3]  → [9,3,7,15,8,23,10]
j=4: a[4]=8  < 9  → i=3, swap a[3],a[4]  → [9,3,7,8,15,23,10]
j=5: a[5]=23 > 9  → 跳过
j=6: a[6]=10 > 9  → 跳过
最后 swap a[low],a[i]  → [8,3,7,9,15,23,10]

pivot 最终位置 $i=3$，左右两侧各 3 个元素，划分完全均衡。

例 2：小数组切换

数组（子问题）：[4, 2, 7, 1, 3]，阈值 = 10

• 此子数组长度为 $5 \leq 10$，直接调用插入排序
• 第 1 趟：[2, 4, 7, 1, 3]（插入 2）
• 第 2 趟：[2, 4, 7, 1, 3]（7 已有序）
• 第 3 趟：[1, 2, 4, 7, 3]（插入 1 到最前）
• 第 4 趟：[1, 2, 3, 4, 7]（插入 3）
• 排序完成，无递归调用