快速排序使用3/5/7元素中位数作基准的代码实现问题

1 现有三数取中代码的错误原因 #

你当前的partition_3运行不符合预期是因为存在两个核心错误：

• 中间索引计算错误：数组中间位置应该是low + (high - low)/2，你遗漏了加low，当low不为0时会直接取到区间外的索引，逻辑完全错误
• 排序逻辑错误：你直接对三个索引的数值本身排序，而非按照索引对应的数组元素大小排序，完全达不到取三个元素中位数的效果

2 修复后的三数取中分区函数 #

int partition_3(int arr[], int low, int high)
{
    // 正确计算三个采样点索引
    int indices[] = {low, low + (high - low)/2, high};
    // 按索引对应的元素值排序索引
    sort(indices, indices + 3, [&](int a, int b) {
        return arr[a] < arr[b];
    });
    // 取排序后的中间索引作为中位数位置
    int median_idx = indices[1];
    // 交换到low位置，复用原有partition逻辑
    swap(arr[median_idx], arr[low]);
    return partition(arr, low, high);
}

3 扩展实现5数、7数取中位数基准 #

逻辑和三数取中一致，只需要均匀增加区间内的采样点即可：

3.1 五数取中分区函数 #

int partition_5(int arr[], int low, int high)
{
    // 将区间分为4等份，取5个均匀采样点
    int step = (high - low) / 4;
    int indices[] = {low, low + step, low + 2*step, low + 3*step, high};
    sort(indices, indices + 5, [&](int a, int b) {
        return arr[a] < arr[b];
    });
    // 5个元素的中位数是排序后第2位（从0计数）
    int median_idx = indices[2];
    swap(arr[median_idx], arr[low]);
    return partition(arr, low, high);
}

3.2 七数取中分区函数 #

int partition_7(int arr[], int low, int high)
{
    // 将区间分为6等份，取7个均匀采样点
    int step = (high - low) / 6;
    int indices[] = {low, low + step, low + 2*step, low + 3*step, low + 4*step, low + 5*step, high};
    sort(indices, indices + 7, [&](int a, int b) {
        return arr[a] < arr[b];
    });
    // 7个元素的中位数是排序后第3位（从0计数）
    int median_idx = indices[3];
    swap(arr[median_idx], arr[low]);
    return partition(arr, low, high);
}

4 配套逻辑优化建议 #

• 当待排序区间长度小于采样数时（比如区间只有2个元素时不需要三数取中），可以直接调用原有partition函数，避免采样逻辑异常
• 3数取中是工程上最常用的方案，已经能规避绝大多数有序数组的最坏时间复杂度问题，5数、7数取中仅在极端数据场景下使用，采样数越高排序的额外开销越大
• 你原有quickSort和partition（霍尔分区实现）逻辑正确，不需要修改，只需要替换调用的分区函数即可切换不同取中方案

内容的提问来源于stack exchange，提问作者boatcoder