Java快速排序Partition方法异常：中间元素未正确排序求助

看起来你的快速排序核心问题出在partition方法的几个关键逻辑上，我帮你梳理并修复一下：

首先，先明确你的需求：只排序数组中除首尾（1000和-1000）之外的元素，也就是索引1到10的部分，这个调用逻辑quicksort(data, 1, data.length-2)是没问题的（data.length-2刚好是10个元素，对应索引1到10）。

原Partition方法的核心错误 #

• 基准元素（pivot）未归位：快排的partition步骤最后必须将基准元素交换到分割点的位置，这样递归才能正确分割左右子数组，原代码完全漏掉了这一步。
• high索引初始化错误：你用high = n，但n是传入的元素个数，不是最后一个元素的索引，正确的计算应该是first + n - 1（从first开始的n个元素，最后一个索引是起始索引+元素个数-1）。
• 多余的判断条件：交换元素时的low<=n是错误的，n是元素个数不是索引，应该只判断low < high。
• 返回值错误：原代码返回low，但正确的分割点应该是基准元素最终所在的索引。

修正后的Partition方法 #

private static int partition(int[] data, int first, int n) {
    int low = first;
    // 修正：计算正确的high索引
    int high = first + n - 1;
    int pivot = data[low]; // 选择第一个元素作为基准

    while (low < high) {
        // 从左往右找第一个大于等于pivot的元素
        while (low <= high && data[low] < pivot) {
            low++;
        }
        // 从右往左找第一个小于等于pivot的元素
        while (high >= low && data[high] > pivot) {
            high--;
        }
        // 交换找到的两个元素
        if (low < high) {
            int temp = data[low];
            data[low] = data[high];
            data[high] = temp;
        }
    }

    // 关键：将基准元素交换到正确的分割位置（high的位置）
    data[first] = data[high];
    data[high] = pivot;

    // 返回基准元素所在的索引，作为分割点
    return high;
}//end partition

修正逻辑解释 #

1. high索引修正：确保每次partition都能定位到当前子数组的最后一个元素，不管递归调用时的first和n是什么值。
2. 基准元素归位：循环结束后，high的位置就是基准元素应该在的位置，把原来的基准元素（存在first位置）和high位置的元素交换，这样基准元素就处于正确的分割点，左边都是小于等于它的元素，右边都是大于等于它的元素。
3. 返回分割点：返回基准元素所在的high索引，这样递归调用时就能正确分割左右子数组。

测试结果 #

修正后运行你的程序，输出会变成：

Here is the entire original array:
1000  80  10  50  70  60  90  20  30  40  0  -1000  
I have sorted all but the first and last numbers.
The numbers are now:
1000  0  10  20  30  40  50  60  70  80  90  -1000  

完全符合你的需求，中间元素已经正确排序。

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