Java自定义快速排序方法触发Out of Bounds Exception问题求助

常见问题根源 #

你的Out of Bounds Exception大概率是以下几个错误导致的：

• 递归边界未正确处理：没有在low >= high时终止递归，导致传入的索引超出当前子数组范围。
• Pivot选择错误：递归过程中没有基于当前子数组的high索引取pivot，而是错误地使用了全局列表的末尾元素（或硬编码为0），导致访问了不存在的索引。
• Partition方法索引逻辑错误：循环中索引越界，或pivot位置交换时用了错误的索引值。

关键修复点 #

1. 修正递归终止条件

确保递归仅在子数组有效（low < high）时执行：

public void myQuickSort(List<Transaction> list, int low, int high) {
    if (low < high) { // 当low >= high时直接返回，避免无效递归
        int pivotIdx = partition(list, low, high);
        myQuickSort(list, low, pivotIdx - 1);
        myQuickSort(list, pivotIdx + 1, high);
    }
}

2. 正确选择当前子数组的Pivot

必须基于当前递归的high索引取pivot，而不是全局列表的末尾：

private int partition(List<Transaction> list, int low, int high) {
    // 取当前子数组的最后一个元素作为pivot
    Transaction pivot = list.get(high);
    int i = low - 1; // 小于pivot的元素的最后位置指针

    // 遍历当前子数组（除pivot外的元素）
    for (int j = low; j < high; j++) {
        if (list.get(j).compareTo(pivot) <= 0) {
            i++;
            Collections.swap(list, i, j);
        }
    }
    // 将pivot交换到正确的分割位置
    Collections.swap(list, i + 1, high);
    return i + 1;
}

3. 检查循环边界

注意partition方法中的循环仅遍历到high - 1，因为high位置是pivot本身，不需要参与比较。

验证步骤 #

1. 初始调用时传入正确的边界：myQuickSort(transactionList, 0, transactionList.size() - 1)
2. 单步调试时重点观察low、high、pivotIdx三个变量的取值，确认每次递归的子数组范围始终在[0, list.size()-1]内。

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