Java实现以中间元素为基准的快速排序异常问题求助

问题重现 #

测试数组：

String[] arr = {"D", "C", "B", "A", "A", "Z", "g", "F", "e", "d", "c", "b"};

排序后输出为 A A B C D F g Z b c d e，不符合预期（正确顺序应为大写字母在前按升序，小写字母在后按升序，即A A B C D F Z b c d e g）；而另一数组String[] arr = {"D", "C", "B", "a", "A", "Z", "g", "f", "e", "d", "c", "b"};排序正常。

问题根源 #

原partition方法存在两处核心逻辑错误：

• 指针移动逻辑不严谨：对等于基准值（pivot）的元素直接移动指针，跳过了部分需要交换的场景，导致部分元素未被正确划分到基准值的左右侧。
• 基准值最终位置错误：循环结束后直接将基准值交换到i的位置，但此时i的位置并不一定是基准值的正确归属位置，破坏了分区的正确性。

修复后的代码 #

private static void quickSort(String[] arr, int start, int end) {
    if (end <= start) return;

    int pivot = partition(arr, start, end);
    quickSort(arr, start, pivot - 1);
    quickSort(arr, pivot + 1, end);
}

private static int partition(String[] arr, int start, int end) {
    // 选择中间索引作为基准值位置
    int pivotIndex = start + (end - start) / 2;
    String pivot = arr[pivotIndex];
    // 将基准值交换到数组末尾，避免循环中被干扰
    swap(arr, pivotIndex, end);
    
    int i = start;
    int j = end - 1;
    
    while (i <= j) {
        // 从左往右找第一个 >= 基准值的元素
        while (i <= j && arr[i].compareTo(pivot) < 0) {
            i++;
        }
        // 从右往左找第一个 <= 基准值的元素
        while (i <= j && arr[j].compareTo(pivot) > 0) {
            j--;
        }
        if (i <= j) {
            swap(arr, i, j);
            i++;
            j--;
        }
    }
    // 将基准值放到正确的分区位置
    swap(arr, i, end);
    return i;
}

// 抽离交换逻辑，提升代码可读性
private static void swap(String[] arr, int i, int j) {
    String temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

修复说明 #

1. 基准值预交换：先将中间位置的基准值移到数组末尾，避免在双指针移动过程中被意外交换，简化分区逻辑。
2. 双指针逻辑优化：
   • i从左向右遍历，找到第一个大于等于基准值的元素
   • j从右向左遍历，找到第一个小于等于基准值的元素
   • 找到后交换两者位置，同时移动指针，确保所有元素都被正确比较和划分
3. 基准值归位：循环结束后，将基准值从末尾交换到i的位置，此时i左侧元素均小于等于基准值，右侧元素均大于等于基准值，保证分区的正确性。

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