“线程”main“java.lang.StackOverflowError”中的异常，用于大小大于 10000 的已排序、反向和相同数据的快速排序

Question

我尝试为所有不同数据大小和格式的输入实现快速排序算法。分区的基本代码是：

public static void QuickSortAlgorithm(int[] array) {
    QuickSort(array, 0, array.length-1);
}

public static void QuickSort(int[] A, int p, int r) {
    if (p < r) {
        int q = Partition(A, p, r);
        QuickSort(A, p, q - 1);
        QuickSort(A, q + 1, r);
    }
}

public static int Partition(int[] A, int p, int r) {
    int x = A[r];
    int i = p - 1;
    for (int j = p; j <= r - 1; j++) {
        if (A[j] <= x) {
            i = i + 1;
            int temp1;
            temp1 = A[i];
            A[i] = A[j];
            A[j] = temp1;
        }
    }
    int temp2;
    temp2 = A[i + 1];
    A[i + 1] = A[r];
    A[r] = temp2;

    return i + 1;

}

}

但是，它适用于大小高达 80,000 的随机数据。但是在排序和反转数据的情况下，它会抛出错误““主线程中的异常”java.lang.WhosebugError”。我试图通过命令行运行它，将文件名作为参数传递。

java -Xss1m QuickSortProgram  sorted_40000.txt

但它仍然会抛出错误。如何解决？我需要通过命令行运行程序。谢谢

Answer 1

排序和反向排序的数据对于您选择起始分区的最后一个元素的特定数据透视选择方法来说是麻烦的情况。您将始终在其中一个子分区中获得零个元素（假设您不将枢轴本身归因于任何一个）。如果您使用整体排序的简单实现，那么这意味着您将递归到等于要排序的元素数的深度，这使您准备好运行出栈 space。

反向排序实际上是最坏的情况，因为即使你解决了递归深度问题，你仍然会得到输入大小的二次方性能。

您可以做几件事。首先是修复整体排序，使其完全不受此类问题的影响。您可以通过采用混合迭代/递归方法来做到这一点，其中每对子分区中较大的一个在不递归的情况下进行排序。对于大小为 n 的输入，这可靠地将递归深度限制为最多 log₂(n)。示例：

static void quickSort(int[] a, int p, int r) {
    while (r - p > 1) {
        int q = Partition(a, p, r);

        if (q - p <= (r - p) / 2) {
            // the left-hand partition is smaller; sort it recursively
            quickSort(a, p, q - 1);
            // update p so as to sort the right-hand partition iteratively
            p = q + 1;
        } else {
            // the right-hand partition is smaller; sort it recursively
            quickSort(a, q + 1, r);
            // update r so as to sort the left-hand partition iteratively
            r = q - 1;
        }
    }
}

您还可以考虑使用更高级的枢轴选择算法。在输入最初排序或反向排序的情况下，三中位数会改善行为，尽管三中位数杀手级输入仍然可以引发二次行为。或者，随机枢轴选择没有提供可靠的杀手级输入，虽然行为只是概率 O(n log(n))，但随着输入的大小增加。

Answer 2

这实际上是正常的：快速排序（使用第一个或最后一个元素作为基准）平均运行时间为 O(n * log n)，但当数据已经排序时为 O(n^2)。递归调用的次数通常是O(log n)，但是当它已经排序时是O(n)。

所以你只是遇到需要花费大量时间的情况，因为大量的递归调用，所以你会得到堆栈溢出...如果你尝试随机使用它，你会得到同样的错误有序但更大（比如 2^40000，我建议你不要那样做；））数据集。

如果您仍然需要对已排序的数据进行排序，您应该使用其他选择作为数据透视表。一个简单的解决方案是随机取一个，但它不能确保你将 永远不会 进行 O(n) 次递归调用。如果您想确定这一点，您应该使用更聪明的方法，例如 John Bollinger 提出的方法。

https://en.wikipedia.org/wiki/Quicksort

“线程”main“java.lang.StackOverflowError”中的异常，用于大小大于 10000 的已排序、反向和相同数据的快速排序

“Exception in thread ”main“ java.lang.StackOverflowError” in Quick sort for sorted, reversed and Identical data of size greater than 10000

java

algorithm

stack

out-of-memory