快速排序（Quick Sort）实现异常求助：代码逻辑排查

我帮你排查了代码里的几个关键问题，主要是基准值（pivot）的位置处理错误和递归边界设置不当，导致排序结果不符合预期。咱们一步步来分析和修正：

核心错误点 #

• 基准值未归位：你选择了数组中间元素作为基准值，但分区完成后，这个基准值仍停留在原来的中间位置，没有被放到“左侧元素都小于等于它、右侧元素都大于等于它”的正确位置，导致递归的子数组范围混乱。
• 递归边界错误：循环结束后，你使用l-1和h+1作为子数组的边界，这会跳过或重复处理部分元素，破坏排序逻辑。
• 分区逻辑的小瑕疵：初始的h = high+1和l = low-1的设置，配合--h和++l的循环方式，容易导致边界判断混淆，增加出错概率。

修正后的代码 #

参考你提到的“基准值移至数组一端”的建议，我调整了分区逻辑，确保基准值最终归位，同时修正了递归边界：

static void QuickSortFromMiddle(int[] arr, int low, int high) { 
    if (low < high) { 
        // 选择中间位置作为基准值的初始位置
        int mid = (low + high) / 2;
        int pivot = arr[mid];
        // 把基准值移到数组左端，简化分区逻辑
        arr[mid] = arr[low];
        arr[low] = pivot;

        int l = low;
        int h = high;
        // 双向分区：把小于等于pivot的放左边，大于的放右边
        while (l < h) {
            // 从右往左找第一个小于等于pivot的元素
            while (l < h && arr[h] > pivot) h--;
            // 从左往右找第一个大于pivot的元素
            while (l < h && arr[l] <= pivot) l++;
            // 交换找到的两个元素
            if (l < h) {
                int temp = arr[l];
                arr[l] = arr[h];
                arr[h] = temp;
            }
        }
        // 将基准值放到它的正确位置
        arr[low] = arr[l];
        arr[l] = pivot;

        // 递归排序左右子数组（基准值所在位置已正确，无需再处理）
        QuickSortFromMiddle(arr, low, l - 1);
        QuickSortFromMiddle(arr, l + 1, high);
    } 
} 

static void QuickSort(int[] arr) { 
    if (arr == null || arr.Length <= 1) return;
    QuickSortFromMiddle(arr, 0, arr.Length - 1); 
} 

static void TestQuickSort() { 
    var arr = new[] { 1, 5, 3, 4, 57, 5, 5, 53 }; 
    QuickSort(arr); 
    foreach (int i in arr) { 
        Console.WriteLine(i); 
    } 
}

修正说明 #

1. 基准值移至一端：先把中间的基准值交换到数组左端，这样我们可以明确基准值的初始位置，避免它在分区过程中被干扰。
2. 双向分区逻辑：从左右两端分别查找需要交换的元素，确保左侧元素都≤基准值，右侧元素都>基准值。
3. 基准值归位：循环结束后，把基准值交换到l的位置（此时l就是基准值的正确位置），保证后续递归的子数组不包含已排好的基准值。
4. 正确的递归边界：递归时分别处理基准值左侧（low到l-1）和右侧（l+1到high）的子数组，避免重复处理或遗漏元素。

运行修正后的TestQuickSort方法，你会得到正确的排序结果：1, 3, 4, 5, 5, 5, 53, 57。

内容的提问来源于stack exchange，提问作者Frank.Liu