java - 我的快速排序实现不适用于 10000 个序列号

Question

我有一个快速排序实现，这种排序实现可以很好地处理小数组和 10000 个随机数，但是当输入是 10000 个序列号(从 1 到 10000)时它会抛出一个计算器错误

public class QuickSort<T extends Comparable> extends Sort<T>{

public void sort(Comparable[] input) {
    sort(input, 0, input.length-1);
}

private void sort(Comparable[] a, int lo, int hi) {
    if (hi <= lo) return;

    int j = partition(a, lo, hi);
    sort(a, lo, j-1);
    sort(a, j+1, hi);
}

private int partition(Comparable[] a, int lo, int hi) {
    int i=lo;
    int j=hi + 1;
    Comparable v = a[lo];

    while(true) {
        while (less(a[++i], v)) {
            if (i == hi) break;
        }

        while (less(v, a[--j])) {
            if (j == lo) break;
        }

        if(i >= j) break;

        exch(a, i, j);
    }
    exch(a, lo, j);
    return j;
}

public static boolean less (Comparable a, Comparable b) {
    return a.compareTo(b) < 0;
}

public static void exch(Comparable[] array, int i, int j) {
    Comparable temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

public static void main(String...args) {
    Integer[] array = new Integer[] {10,2,9,11,1,19,9,4,6,2,1,4,5,6};
    new QuickSort<>().sort(array);

    for (int temp : array) {
        System.out.print(temp + " ");
    }
}
}

它适用于 10000 个随机数和其他输入。但是当使用 10000 个序列号(从 1 到 10000)执行时会抛出 stackoverflow 错误

Answer 1

在最坏的情况下，简单的快速排序实现具有 O(n^2) 的复杂度和 O(n) 的额外内存需求。由于糟糕的枢轴元素选择方法，您在有序序列上遇到了这种最坏情况。

Wikipedia :

In the very early versions of quicksort, the leftmost element of the partition would often be chosen as the pivot element. Unfortunately, this causes worst-case behavior on already sorted arrays, which is a rather common use-case. The problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition or (especially for longer partitions) choosing the median of the first, middle and last element of the partition for the pivot (as recommended by Sedgewick).

解决此问题的简单方法是将中间元素作为支点。替换

Comparable v = a[lo];

与

Comparable v = a[lo+(hi-lo)/2];

为这种枢轴选择方法创建最坏情况测试并不难，但您需要在大型输入情况下有意识地进行测试。如果你想要类似于 Quicksort 并且没有 O(n^2) 最坏情况的排序算法，你应该看看 Introsort算法。