java - IndexOutOfBoundsException 和快速排序算法

Question

我无法弄清楚为什么我的代码出现 IndexOutOfBoundsException。我想知道是否有人可以成为我的额外眼睛来帮助我发现错误。我正在手动尝试这个，但我认为在浏览代码时我遗漏了一些东西。

代码:

package Algorithms;

import java.util.ArrayList;

public class quickSort {

    public static ArrayList<Integer> mergeArrayList(ArrayList<Integer> min, int pivot, ArrayList<Integer> max) {
        ArrayList<Integer> mergedList = new ArrayList<Integer>();
        //mergedList.addAll(min);
        for (int i : min) {
            mergedList.add(i);
        }
        mergedList.add(pivot);
        //mergedList.addAll(max);
        for (int j : max) {
            mergedList.add(j);
        }
        return mergedList;
    }


    public static ArrayList<Integer> quicksort(ArrayList<Integer> array, int min, int max) {
        if (array.size() <= 1) {
            return array;
        }
        int pivot = (min + max)/2;
        ArrayList<Integer> less = new ArrayList<Integer>();
        ArrayList<Integer> greater = new ArrayList<Integer>();
        for (int i : array) {
            if (i <= array.get(pivot)) {
                less.add(i);
            }
            else {
                greater.add(i);
            }
        }
        return mergeArrayList(quicksort(less,min,pivot - 1), array.get(pivot), quicksort(greater, pivot + 1, max));
    }

    public static void main(String[] args) {
        ArrayList<Integer> arr1 = new ArrayList<Integer>();
        int[] arr = {1,2,3,4,5};
        for (int i : arr) {
            arr1.add(i);
        }
        System.out.println(quicksort(arr1,0,arr1.size() - 1));
    }
}

错误:

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 3, Size: 2
    at java.util.ArrayList.rangeCheck(ArrayList.java:635)
    at java.util.ArrayList.get(ArrayList.java:411)
    at Algorithms.quickSort.quicksort(quickSort.java:30)
    at Algorithms.quickSort.quicksort(quickSort.java:37)
    at Algorithms.quickSort.main(quickSort.java:46)

Answer 1

返回中的quicksort(greater,pivot + 1, max)将导致:

int pivot = (max + pivot + 1) /2; //pseudocode

pivot 将大于数组的长度(是原始长度的一半)，导致当您请求 array.get(pivot) 时出现越界异常