Java实现Quicksort遇数组越界、死循环及交换错误问题求助

你的代码存在几个核心错误，直接引发了索引越界、死循环和排序结果异常，下面逐个拆解问题并给出修复方案：

1. 子数组边界判断错误 #

内层while循环误用了整个数组的边界（j>=0、i < a.length），但当前处理的是from到to的子数组，超出该范围的索引无需处理，这会导致数组越界，也会让指针跑到错误位置。

• 修正：将j>=0改为j > ipivot（pivot在ipivot，j无需跑到pivot左侧）；将i < a.length改为i <= to

2. 元素比较逻辑反向 #

你的分区目标是把<=pivot的元素放左侧、>pivot的放右侧，但内层循环的条件写反了：

• 左指针循环应该找大于pivot的元素（原逻辑找小于的，导致i停在符合左侧规则的位置，完全不符合交换要求）
• 右指针循环逻辑正确（找>pivot的元素就左移，停在<=pivot的位置），但需要加上i < j的判断，避免i已经超过j时仍继续移动指针

3. Pivot最终位置选择错误 #

循环结束后你把pivot和i交换，但实际上当i>=j时，j的位置才是最后一个<=pivot的元素，应该把pivot和j交换，否则pivot位置错误会导致递归的子数组范围异常，进而引发死循环。

修正后的完整代码 #

public class Quicksort {

    /*
     * Entry method for Quicksort
     */
    public static void quicksort(int[] a) {
        quicksort(a, 0, a.length - 1);
    }

    /*
     * Quicksort! 
     * Operates in-place, i.e. it doesn't create a copy.
     */  
    public static void quicksort(int[] a, int from, int to) {
        // Base case: Sorting range is 1 element or empty.
        if (from >= to) {
            return;
        }
        
        int ipivot = from; // Pivot p
        System.out.println("Pivot p = " + a[ipivot]);
        printArray(a);
        
        int i = ipivot + 1;
        int j = to;
        while (i < j) {
            // 先从右往左找第一个<=pivot的元素
            while (j > ipivot && a[j] > a[ipivot]) {
                j--;
            }
            // 再从左往右找第一个>pivot的元素
            while (i < j && a[i] <= a[ipivot]) {
                i++;
            }
            
            // 交换不符合分区的元素
            if (i < j) {
                swap(a, i, j);
            }
        }
        // 将pivot交换到正确的位置：j的位置是最后一个<=pivot的元素
        int ipivot_final = j;
        System.out.println("swapping " + a[ipivot] +" @"+ipivot+" and " + a[ipivot_final]+" @"+ipivot_final + " (pivot)");
        swap(a, ipivot, ipivot_final);
        
        printArray(a);
        System.out.println();
        
        // 递归排序左右子数组
        quicksort(a, from, ipivot_final - 1);
        quicksort(a, ipivot_final + 1, to);
    }

    /*
     * HELPER METHODS
     */
    public static void printArray(int[] a) {
        for (int num : a) {
            System.out.print(num + ", ");
        }
        System.out.println();
    }

    public static boolean isSorted(int[] array) {
        for (int j = 0; j < array.length - 1; j++) {
            if (array[j] > array[j + 1])
                return false;      
        }
        return true;
    }

    private static int[] createRandomArray(int size, int minVal, int maxVal) {
        int[] a = new int[size];
        for (int i = 0; i < a.length; i++) {
            a[i] = (int) (Math.random() * (maxVal - minVal) + minVal);
        }
        return a;
    }

    private static void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    /*
     * MAIN
     */
    public static void main(String[] args) {
        final int MINSIZE = 10;
        final int MAXSIZE = 10;
        for (int size = MINSIZE; size <= MAXSIZE; size++) {
            int[] a = createRandomArray(size, 0, size);
            System.out.println("Unsorted array of size "+a.length);
            printArray(a);
            System.out.println("\nRunning Quicksort ...");
            quicksort(a);
            System.out.println("\nSorted array:");
            printArray(a);
            assert isSorted(a) : "Array is not sorted!";
            if (isSorted(a))
                System.out.println("\n\nSuccess!!\n\n");
            else
                System.out.println("\n\nERROR !! Something went wrong.\n\n");
        }
    }
}

关键修正点总结 #

• 限制指针在当前子数组[from, to]范围内移动，避免越界
• 修正左右指针的比较逻辑，确保找到的是需要交换的不符合分区规则的元素
• 将pivot交换到j的位置，而非i，保证pivot处于正确的分区点
• 内层循环加入i < j的判断，防止指针在交叉后仍继续移动

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