java - 使用快速排序对大型列表进行排序时总是会发生堆栈溢出

Question

我正在为一项作业进行快速排序，但在对大型列表(> 100.000 个项目)进行排序时，它总是会引发堆栈溢出。堆栈溢出应该表明停止条件不正确，但我找不到问题。我真的很感激一些帮助。谢谢阅读。 我的快速排序:

private void qSort(List<E> items, int low, int high, Comparator<E> comparator) {
    // base case
    if (low >= high) {
        return;
    }

    // set the pivot (last element)
    E pivot = items.get(high);

    int leftPointer = low;
    int rightPointer = high;

    while (leftPointer < rightPointer) {
        // we move the left pointer until we find a value that is bigger than the pivot
        while (leftPointer < rightPointer && comparator.compare(items.get(leftPointer), pivot) <= 0) {
            leftPointer++;
        }

        // we move the right pointer until we find a value that is smaller than the pivot
        while (leftPointer < rightPointer && comparator.compare(items.get(rightPointer), pivot) >= 0) {
            rightPointer--;
        }

        // swap the values at the pointers
        swap(items, leftPointer, rightPointer);

    }
    // at this point, leftPointer and rightPointer are equal and we need to swap the item at the pointers with the pivot
    swap(items, leftPointer, high);

    // now we have the pivot is in the correct position
    // we continue recursively sorting the left side of the pivot, (not including the pivot, because its already in its final position)
    qSort(items, low, leftPointer - 1, comparator);
    // and the right side of the pivot
    qSort(items, leftPointer + 1, high, comparator);

}

我尝试了各种不同的实现，但没有一个有效。我尝试过增加堆栈大小。

Answer 1

如果您的数据包含已排序的运行，则 n 项的快速排序将需要 O(n) 堆栈帧。即使只有一些排序运行，这也可能是一个问题。

对此有多种解决方案。最简单的方法是在使用之前将枢轴与随机元素交换。您现在将执行 O(n) 工作来生成 O(n) 伪随机选择。但现在几乎不可能触发快速排序的潜在病态行为。

目前最常用的解决方案是使用另一种排序算法。 Timsort是一个流行的选择，因为它最坏情况的行为是 O(n log(n))，但它可以找到并利用排序序列来获得时间 O(n)在许多常见的现实世界场景中。