java - 使用泛型列表进行快速排序时索引越界异常

Question

这是我到目前为止编写的代码:

import java.util.Collections;
import java.util.Random;
import java.util.List;

public class Sorter<T extends Comparable<T>> {
public void sort(List<T> list) {
    if (list.size() <= 10) {
        insertionSort(list, 0, list.size());
    } else {
        quickSort(list, 0, list.size() - 1);
    }
}

private void quickSort(List<T> list, int leftIndex, int rightIndex) {
    int i = leftIndex;
    int j = rightIndex;
    if (i >= j) { 
        return;
    } else if (j - i <= 10) {
        insertionSort(list, i, j+1);
        return;
    }


    int rand = randomizePivot(j, i);
    T pivot = list.get(rand);
    Collections.swap(list, rand, j);

    while (i < j) {

        while (!list.get(i).compareTo(pivot) && i < j) {
            i++;
        }


        while (!pivot.compareTo(list.get(j)) && i < j) {
            j--;
        }


        if (i < j) {
            Collections.swap(list, i, j);
        }
    }

    list.remove(rightIndex);
    list.add(rightIndex, list.get(j));
    list.remove(j);
    list.add(j, pivot);

    quickSort(list, leftIndex, i - 1);
    quickSort(list, j + 1, rightIndex);
}

private int randomizePivot(int hi, int lo) {
    Random rand = new Random();
    return rand.nextInt(hi - lo + 1) + lo;
}

private void insertionSort(List<T> list, int lo, int hi) {
    for (int i = lo + 1; i < hi; i++) {
        int j = i - 1;
        T elem = list.get(i);
        while (j >= lo && list.get(j).compareTo(elem)) {
            list.remove(j + 1);
            list.add(j + 1, list.get(j));
            j--;
        }
        list.remove(j + 1);
        list.add(j + 1, elem);
    }
}

}

十有八九“有效”。有时它会在这一行给出 IndexOutOfBoundsException:

        list.add(rightIndex, list.get(j));

这就是枢轴找到其最终位置的部分。在包含 25 项的列表中，确切的错误消息是:

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 24, Size: 24
at java.util.LinkedList.checkElementIndex(Unknown Source)
at java.util.LinkedList.get(Unknown Source)

有人可以帮忙吗？哪里错了？

Answer 1

只有当 rightIndex == j 时才会发生这种情况在这里，您删除最右边的元素，并在下一步中尝试重新插入它。但 j 索引随后就消失了。

像这样保护它:

if (rightIndex != j) {
       list.remove(rightIndex);
       list.add(rightIndex, list.get(j));
}