编写快速排序算法时索引越界异常

Question

我目前正在编写快速排序算法的修改版本，但我收到索引越界异常，即使我的 ArrayList 输入中包含元素。

希望有人能告诉我哪里错了...

这是错误代码：

 Exception in thread "main" java.lang.IndexOutOfBoundsException: Index:
 4, Size: 4 at java.util.ArrayList.rangeCheck(ArrayList.java:635)   at> java.util.ArrayList.get(ArrayList.java:411)     at
 Lab4.quickSort(Lab4.java:36)   at Lab4.main(Lab4.java:113)

这是我目前使用的代码：

public void quickSort(ArrayList<Integer> S){
    if(S.size() <= 1) return;

    int middle = (S.size() - 1) / 2;
    int pivot = S.get(middle);
    ArrayList<Integer> L = new ArrayList<Integer>(); //less
    ArrayList<Integer> E = new ArrayList<Integer>(); //equal
    ArrayList<Integer> G = new ArrayList<Integer>(); //greater

    int i = 0;
    while(!S.isEmpty()) {
        int next = S.get(i);
        if(next == pivot) E.add(next);
        else if(next > pivot) G.add(next);
        else if(next < pivot) L.add(next);
        i++;
    }

    quickSort(L);
    quickSort(G);

    S.addAll(L);
    S.addAll(E);
    S.addAll(G);
}

我目前用来测试这个方法的ArrayList如下（我想你可能也需要这部分）：

ArrayList<Integer> arr2 = new ArrayList<Integer>();
arr2.add(3);
arr2.add(1);
arr2.add(6);
arr2.add(5);
sort.quickSort(arr2);
System.out.println("\n\nQuickSort (should be sorted): ");
printIntArrayList(arr2);

Answer 1

如果 S 包含一个值 d.isEmpty() 从不 returns false。所以你运行陷入无限循环。如果我将 S.size() 变大，如果您使用 get() 函数，您将得到 ArrayIndexOutOfBoundException。

变化：

while(!S.isEmpty()) {

收件人：

while (i<S.size()) {

Answer 2

此代码有问题：

int i = 0;
while(!S.isEmpty()) {
    int next = S.get(i);
    if(next == pivot) E.add(next);
    else if(next > pivot) G.add(next);
    else if(next < pivot) L.add(next);
    i++;
}

从 S 中，您没有删除元素，因此您将满足条件。在每次迭代中，您都在增加 i 值，当您尝试读取第 n+1 个元素时，您会遇到异常。

您可能需要检查边界并循环直到那时（类似于 while (i<S.size())）？

Answer 3

问题出在这个循环

int i = 0;
    while(!S.isEmpty()) {
        int next = S.get(i);
        if(next == pivot) E.add(next);
        else if(next > pivot) G.add(next);
        else if(next < pivot) L.add(next);
        i++;
    }

变量'i'递增没有任何限制，你必须小心限制它递增的量，而且你的while循环不会中断，因为你没有从它删除任何东西

Answer 4

这里的问题是你的 S 永远不会为空，ArrayList 的函数只获取 return 值而不移动它，你应该做的是改变你的条件：while(i<S.size())) 这也不是在 List 上循环的最佳方式，相反你可能想在 List 上迭代：for (Integer x : S) 并使用 x 作为你的元素。

Answer 5

您的问题出在 while 循环上。您调用 !S.isEmpty() 作为您的布尔表达式，然后遍历 S。这样做的错误是 S 永远不会为空，因此您的方法一旦到达列表末尾就会总是越界。相反，请尝试检查列表是否包含下一项。我建议将以下内容放在循环的末尾：

if(S.get(i+1) == null){
return;
}

编写快速排序算法时索引越界异常

Index Out of Bounds Exception when writing QuickSort Algorithm

java

quicksort