三数取中通过选首、中、尾三元素的中位数作基准，降低快排退化为O(n²)的概率，尤其提升对有序、逆序及重复数据的鲁棒性；需先判断数组长度是否小于3，再安全计算中位索引并避免越界。
为什么三数取中能缓解快排最坏情况
快速排序在每次划分时若选到最小或最大元素作基准（pivot），会导致一边子数组为空、另一边几乎全量，退化成 O(n²)。而三数取中——取首、中、尾三个位置的元素，取它们的中位数作为 pivot——能显著降低这种极端划分的概率，尤其对已排序、逆序或含大量重复元素的输入更鲁棒。
这不依赖随机化，也不需要额外空间，是工业级实现（如 glibc 的 qsort）常用策略。
如何安全获取“中位数”而不越界
数组长度可能小于 3，直接取 arr[0]、arr[n/2]、arr[n-1] 会出错；另外，n/2 在 n==0 或 n==1 时也需规避。
无序列表呈现关键处理点：
立即学习“C++免费学习笔记（深入）”；
- 总是先判断
n < 3：此时直接用插入排序或直接选arr[0]，跳过三数逻辑 - 计算中位索引用
n / 2（整除），但必须确保n > 0，且n-1 >= 0 - 比较三个值时，用临时变量交换或内联比较，避免修改原数组顺序（否则影响后续 partition）
- 推荐把中位数“挪到末尾”，再调用标准
partition，这样主逻辑不用大改
示例片段（仅中位数选取部分）：
int median_of_three(int arr[], int left, int right) {
int mid = left + (right - left) / 2;
if (arr[mid] < arr[left]) std::swap(arr[left], arr[mid]);
if (arr[right] < arr[left]) std::swap(arr[left], arr[right]);
if (arr[right] < arr[mid]) std::swap(arr[mid], arr[right]);
// 此时 arr[mid] 是三数中位数
std::swap(arr[mid], arr[right]); // 放到末尾，供 partition 使用
return arr[right];
}
partition 过程必须适配三数取中后的布局
三数取中后把中位数换到了 right 位置，意味着标准 partition 的 pivot 就是 arr[right]。但常见错误是仍按“任意位置 pivot”写法，没调整循环边界或忽略末尾已固定。
要点如下：
- 不要再在
partition内部重新选 pivot，它现在就是arr[right] - 双指针扫描范围应为
[left, right - 1]，因为right是 pivot 位，不参与比较 - 交换 pivot 到最终位置时，用
std::swap(arr[i + 1], arr[right])（i 是最后一个小于等于 pivot 的下标） - 若使用 Lomuto 分区方案，务必确认
i初始化为left - 1，且循环结束前i至少加过一次
递归边界与小数组优化不能省
三数取中只改善 pivot 质量，不解决小规模子问题的常数开销。实际中，当 right - left + 1 <= 10 左右，继续递归反而比插入排序慢。
注意这些细节：
- 插入排序阈值不是固定 10，可测得 8–16 之间较优；glibc 用 4，llvm libcxx 用 12
- 插入排序必须作用于原数组子区间
[left, right]，且保证left <= right - 递归调用前检查子数组长度，避免
left > right导致无限递归或越界访问 - 不要对单个元素（
left == right）再调用quick_sort，直接返回
真正难的不是写对三数逻辑，而是让 pivot 交换、partition 边界、递归剪枝这三处严丝合缝地咬合。漏掉任一环，要么性能回退，要么出现 std::out_of_range 或无限循环。
