2

对于家庭作业，我必须编写一个 QuickSort 算法的实现，并使用它以某种随机顺序对包含 100k 个数字的列表进行排序。

在作业的第一部分，我必须使用数组的第一项作为枢轴元素。这确实返回了一个排序列表。但是，对于作业的第二部分，我必须使用最后一项作为枢轴，这会导致 StackOverflowException。当我在 8 条记录的较小集合中尝试它时，它确实可以正常工作。我一直在查看我的代码，但我不知道我在哪里犯了错误。任何帮助将不胜感激。我的代码如下：

public class QuickSort {

    private QuickSortStrategyEnum quickSortStrategy;

    public QuickSort(QuickSortStrategyEnum quickSortStrategy) {

        this.quickSortStrategy = quickSortStrategy;
    }

    public List<Integer> sortIntegerArray(List<Integer> arrayList, int left, int right) {

        if ( left >= right ) {
            return arrayList;
        }

        int i = partition(arrayList, left, right);

        if (i <= right) {

            int pivotNew = partition(arrayList, i, right);
            int pivotIndex = arrayList.indexOf(pivotNew);

            arrayList = sortIntegerArray(arrayList, left , pivotIndex - 1);
            arrayList = sortIntegerArray(arrayList, pivotIndex + 1, right);
        }

        return arrayList;
    }

    private int partition(List<Integer> arrayList, int left, int right) {

        int pivot = getPivot(arrayList, left, right);
        int i = left + 1;

        for (int j = i; j <= right; j++) {

            if (arrayList.get(j) < pivot) {

                Collections.swap(arrayList, j, i);
                i++;
            }
        }

        Collections.swap(arrayList, left, i - 1);
        return i;
    }

    private int getPivot(List<Integer> arrayList, int left, int right) {

        int pivot = 0;

        switch (quickSortStrategy) {

            case FIRST:
            pivot = arrayList.get(left);
            break;

            case LAST:
            pivot = arrayList.get(right);
            break;
        }
        return pivot;
    }

}
4

3 回答 3

5

提示：如果 会发生什么right == left + 1？

于 2012-04-15T18:12:14.363 回答
1

除了 David Harkness 指出的事实之外，分区逻辑也存在问题。试试这个：（删除大卫哈克尼斯指出的东西后）

private int partition(List<Integer> arrayList, int left, int right) {

    int pivot = getPivot(arrayList, left, right);
    int i = left - 1; 

    for (int j = left; j < right; j++) {
        if (arrayList.get(j) <= pivot) {
            i++;
            Collections.swap(arrayList, j, i);
        }
    }

    Collections.swap(arrayList, i+1, right);
    return i+1;
}

它适用于枢轴是最后一个元素的情况。不适用于第一个元素。

阅读，理解纸上的工作，干活，编写伪代码，然后向 Eclipse 打个招呼。不要急于实施。

于 2012-04-15T19:25:13.907 回答
1

这两行看起来很可疑：

int pivotNew = partition(arrayList, i, right);
int pivotIndex = arrayList.indexOf(pivotNew);

查看partition返回的内容并将其与您如何使用其结果进行比较。

于 2012-04-15T19:06:15.473 回答