0

我正在尝试在 ArrayList 上实现快速排序算法。但是，我得到一个

Exception in thread "main" java.lang.StackOverflowError
    at sorting.QuickSort.quickSort(QuickSort.java:25)
    at sorting.QuickSort.quickSort(QuickSort.java:36)
    at sorting.QuickSort.quickSort(QuickSort.java:36)
    at sorting.QuickSort.quickSort(QuickSort.java:36)
    at sorting.QuickSort.quickSort(QuickSort.java:36)
    ...

我不确定为什么会有溢出。下面是我的实现：

public static void quickSort(ArrayList<Integer> al, int fromIdx, int toIdx) {
    int pivot, pivotIdx;

    if (fromIdx < toIdx) {
        pivot = al.get(fromIdx);
        pivotIdx = fromIdx;

        for (int i = 0; i != (fromIdx + 1); i++) {
            if (al.get(i) <= pivot) {
                pivotIdx += 1;
                swap(al, pivotIdx, i);
            }
        }

        swap(al, fromIdx, pivotIdx);
        quickSort(al, fromIdx, pivotIdx - 1);
        quickSort(al, pivotIdx + 1, toIdx);
    }
}

public static void swap(ArrayList<Integer> al, int xIdx, int yIdx) {
    Integer temp = al.get(xIdx);
    al.set(xIdx, al.get(yIdx));
    al.set(yIdx, temp);
}
4

1 回答 1

0

如果您尝试从fromIdxto对数组的块进行排序toIdx，则不应查看元素 0，除非它位于该块中。但是您的实现确实如此。

您在中间的索引技巧也有点……奇怪。我强烈建议您练习为数组剪下小纸片，并在一张纸上写下跟踪信息，以便您可以跟踪算法。如果你在实际操作时发现它没有意义，那么它在计算机中也没有意义。拿着纸片的行为可能看起来很傻，但对于准确地想象你在做什么很有帮助。（你越能准确地想象你的代码实际上做了什么，你就越有可能弄清楚它是否做错了什么。）

于 2013-10-27T05:46:02.427 回答