递归QuickSort方法异常：多数输入数组排序结果不正确

你的递归快速排序仅在部分场景有效，多数情况排序结果错误，例如测试数组输出中出现13在22之后、27在31之后、105在120之后的乱序情况。以下是问题分析和修复方案：

错误原因分析 #

1. 递归终止条件错误 #

quickSortSub方法中使用if(b-a > 1)作为递归终止条件，这会跳过长度为2的子数组（即b-a=1的情况），导致这类子数组无法被排序，最终出现乱序。

2. Partition函数的内层循环无边界限制 #

partition方法的两个内层while循环未做边界控制：

• 第一个while(s[left] < pivot)会让left持续递增，可能超出right范围甚至数组边界；
• 第二个while(s[right] > pivot)会让right持续递减，可能小于a导致数组越界，同时会出现left与right交叉后仍继续移动的问题，最终导致pivot的位置放置错误。

修复后的完整代码 #

public class QuickSort {

    public static void quickSort(int[] s) {
        quickSortSub(s, 0, s.length - 1);
    }

    private static void quickSortSub(int[] s, int a, int b) {
        // 修复终止条件：只要起始索引小于结束索引就处理，覆盖所有需排序的子数组
        if(a < b) {
            int point = partition(s, a, b);
            quickSortSub(s, a, point - 1);
            quickSortSub(s, point + 1, b);
        } 
    }

    private static int partition(int[] s, int a, int b) {
        int pivot = s[b];
        int left = a;
        int right = b-1;
        while(left < right) {
            // 添加left <= right限制，防止越界
            while(left <= right && s[left] < pivot) {
                left++;
            }
            // 添加right >= left限制，防止越界且避免无效移动
            while(right >= left && s[right] > pivot) {
                right--;
            }
            if(left < right) {
                int tmp = s[left];
                s[left] = s[right];
                s[right] = tmp;
                // 交换后移动指针，避免重复交换同一元素
                left++;
                right--;
            }
        }
        // 确保left位置元素大于pivot时再交换，避免无效操作
        if(s[left] > pivot) {
            s[b] = s[left];
            s[left] = pivot;
        }
        return left;
    }

    public static void main(String[] args) {
        int[] arr = {85, 10, 24, 63, 45, 27, 100, 31, 96, 50, 40, 23, 49, 96, 120, 105, 13, 5, 42, 69, 22, 12};
        quickSort(arr);
        for (int i: arr) System.out.print(i + ", ");
        System.out.println("");
    }
}

修复细节说明 #

1. 递归终止条件调整：将b-a > 1改为a < b，确保所有长度大于1的子数组（包括长度为2的情况）都会被处理。
2. 内层循环边界控制：给两个while循环分别添加left <= right和right >= left的条件，避免数组越界，同时防止指针过度移动。
3. 交换后指针移动：交换左右元素后，将left右移、right左移，避免陷入重复交换同一对元素的死循环。
4. Pivot交换前判断：最后交换pivot到left位置前，先判断该位置元素是否大于pivot，避免当所有元素都小于pivot时，错误地移动pivot位置。

修复后运行代码，输出结果为正确的升序排列：
5, 10, 12, 13, 22, 23, 24, 27, 31, 40, 42, 45, 49, 50, 63, 69, 85, 96, 96, 100, 105, 120,

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