为什么我的C++快速排序在数组含多个重复值时无法正常工作？

问题现象 #

• 代码在无重复值或仅含2个重复值的数组中运行正常，但重复值超过2个时输出错误。
• 测试数组：{11,6,8,23,9,1,5,15,7,7,7,7}
  • 预期输出：1 5 6 7 7 7 7 8 9 11 15 23
  • 实际输出：1 5 6 7 7 9 7 7 8 11 15 23
• 修改代码最后一个if块时会触发无限循环。

问题根源 #

1. main函数重复调用排序逻辑：同时调用了quicksort和recursive_func，导致排序流程被打乱——recursive_func内部已经会调用分区函数，无需单独调用quicksort。
2. 分区逻辑缺陷：
   • 计数pivot位置时，仅统计s+1到e中<=pivot的元素数量，导致pivot放置位置不准确，左侧仍存在大于pivot的元素。
   • 双指针循环条件过于严格（i<pivot_index && j>pivot_index），当其中一个指针到达pivot位置时，循环终止，剩余未交换的元素会导致分区错误。
3. 重复值处理不当：未将等于pivot的元素归位，导致递归排序时重复处理这些元素，甚至触发无限循环。

修复方案 #

使用荷兰国旗分区法处理重复值，将数组分为小于pivot、等于pivot、大于pivot三部分，避免重复值干扰排序流程；同时移除main函数中多余的排序调用。

修复后的完整代码 #

#include <iostream>
using namespace std;

void recursive_func(int arr[], int s, int e)
{
    if (s >= e)
        return;
    
    int pivot = arr[s];
    int low = s;
    int mid = s;
    int high = e;

    // 荷兰国旗分区：将数组分为 <pivot、=pivot、>pivot 三部分
    while (mid <= high) {
        if (arr[mid] < pivot) {
            swap(arr[low], arr[mid]);
            low++;
            mid++;
        } else if (arr[mid] == pivot) {
            mid++;
        } else {
            swap(arr[mid], arr[high]);
            high--;
        }
    }

    // 递归排序小于pivot的左半部分和大于pivot的右半部分
    recursive_func(arr, s, low - 1);
    recursive_func(arr, high + 1, e);
}

int main()
{
    int n = 12;
    int arr[12] = {11,6,8,23,9,1,5,15,7,7,7,7};

    // 仅调用递归排序函数即可
    recursive_func(arr, 0, n-1);

    for(int i=0; i<n; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}

修复说明 #

1. 移除多余调用：main函数中仅保留recursive_func调用，避免重复执行分区逻辑。
2. 荷兰国旗分区：
   • 使用三个指针low、mid、high遍历数组，将小于pivot的元素移到左侧，等于pivot的留在中间，大于pivot的移到右侧。
   • 等于pivot的元素无需递归排序，减少不必要的计算，同时避免重复值导致的分区错误。
3. 递归范围调整：递归仅处理小于pivot的左半部分（s到low-1）和大于pivot的右半部分（high+1到e），中间等于pivot的元素已处于正确位置。

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