Java实现Randomized QuickSort抛出IndexOutOfBounds异常求助

触发ArrayIndexOutOfBounds异常的核心原因是swap函数调用时参数传递错误，具体问题及修复方式如下：

• 你定义的swap(int[] A, int i, int j)方法的后两个入参是数组的下标索引，但你所有调用swap的位置都错误传入了数组对应位置的元素值，当元素值大于等于数组长度时，就会触发索引越界：
  • randomisedPartition方法中的swap(A, A[randomNum], A[start]); 修正为swap(A, randomNum, start);
  • hoarePartition方法中的swap(A, A[i], A[j]); 修正为swap(A, i, j);
  • hoarePartition方法末尾的swap(A, A[start], A[j]); 修正为swap(A, start, j);
• 补充优化点：Random对象不需要每次调用randomisedPartition都新建，提到类属性位置初始化即可，避免重复实例化的性能开销。

修正后的完整代码如下：

import java.util.Random;

public class QuickSort {
    // Random实例提到类属性，避免重复创建
    private final Random rng = new Random();

    void quickSort(int[] A, int start, int end) { // 初始调用参数：start = 0, end = n-1
        while (start < end) {
            int iOfPartition = randomisedPartition(A, start, end);
            // 尾递归优化，优先递归长度更小的子数组
            if (iOfPartition - start < end - iOfPartition) {
                quickSort(A, start, iOfPartition - 1);
                start = iOfPartition + 1;
            } else {
                quickSort(A, iOfPartition + 1, end);
                end = iOfPartition - 1;
            }
        }
    }

    int randomisedPartition(int[] A, int start, int end) {
        int randomNum = rng.nextInt(end + 1 - start) + start;
        swap(A, randomNum, start);
        return hoarePartition(A, start, end);
    }

    int hoarePartition(int[] A, int start, int end) {
        int pivot = A[start];
        int i = start;
        int j = end;
        while (i < j) {
            while (A[i] <= pivot && i < end) i++;
            while (A[j] > pivot && j > start) j--;
            if (i < j) swap(A, i, j); 
        }
        swap(A, start, j);
        return j; 
    }

    void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

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