如何修改partition函数实现接近有序整数列表的正确排序

问题分析 #

当前给出的是基础版Lomuto分区实现，单轮分区逻辑本身无语法错误，但存在两个核心缺陷导致最终排序结果异常：

1. 参数设计缺陷：当前函数仅支持从下标0开始、长度为size的子数组分区，无法支持快排递归时对右半部分子区间（起始下标不为0）的处理，这是排序结果不完美的最常见原因。
2. 重复元素分区倾斜：现有逻辑仅将严格小于基准值的元素放到左侧，等于基准值的元素全部被划分到右侧，当数组存在大量重复元素时会导致分区极度不平衡，最坏时间复杂度退化到O(n²)，也可能引发边界处理错误。

修改方案 #

方案1：适配快排递归的标准Lomuto分区实现 #

首先修改参数结构，支持任意子区间分区，逻辑和原有实现对齐：

// 新增left和right参数，处理[left, right]闭区间的分区
int partition(std::vector<int>& tab, int left, int right) {
    // 随机选基准值，避免有序数组下触发最坏情况
    int pivot_idx = left + rand() % (right - left + 1);
    std::swap(tab[pivot_idx], tab[left]);
    int pivot = tab[left];
    int i = left + 1;
    for (int j = left + 1; j <= right; j++) {
        if (tab[j] < pivot) {
            std::swap(tab[i], tab[j]);
            i++;
        }
    }
    std::swap(tab[left], tab[i - 1]);
    return i - 1;
}

// 配套的快排递归实现参考
void quickSort(std::vector<int>& tab, int left, int right) {
    if (left >= right) return;
    int pivot_pos = partition(tab, left, right);
    quickSort(tab, left, pivot_pos - 1);
    quickSort(tab, pivot_pos + 1, right);
}

// 对外调用入口
void sort(std::vector<int>& tab) {
    if (tab.empty()) return;
    srand(time(nullptr)); // 初始化随机数种子，全局仅需调用一次
    quickSort(tab, 0, tab.size() - 1);
}

方案2：优化重复元素处理的双路分区（推荐） #

解决重复元素分区倾斜问题，大幅提升含大量重复元素数组的排序稳定性和效率：

int partition(std::vector<int>& tab, int left, int right) {
    int pivot_idx = left + rand() % (right - left + 1);
    std::swap(tab[pivot_idx], tab[left]);
    int pivot = tab[left];
    // 双指针分别从左右两端遍历
    int i = left + 1, j = right;
    while (true) {
        // 左指针找大于等于基准的元素
        while (i <= j && tab[i] < pivot) i++;
        // 右指针找小于等于基准的元素
        while (i <= j && tab[j] > pivot) j--;
        if (i > j) break;
        std::swap(tab[i], tab[j]);
        i++;
        j--;
    }
    std::swap(tab[left], tab[j]);
    return j;
}

该实现会把等于基准值的元素均匀分到左右两个分区，避免分区倾斜问题，排序稳定性和效率都更高。

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