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方法的开头。

public static ArrayList<Integer> quicksort(ArrayList<Integer> array, int min, int max) 
{
    System.out.println(Arrays.toString(array.toArray()) + " -> " + min + " " + max);
    ...
}

您将确切地看到发生了什么以及何时/在哪里出错。

Answer 2

返回值中的快速排序(较大，pivot + 1，max)将导致：

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

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

Answer 3

问题出在min和max上

我知道你在你发送的数组中使用它们作为索引，但是-你发送的less & greater比原始数组小。

因此，对于您的示例，在第一次调用quicksort之后，pivot =2此部分quicksort(greater, pivot + 1, max)将发送值为3,4的greater，因此这将创建您的异常