第一个和最后一个枢轴元素与非常大的 N 的通用放置

Question

我已经实现了快速排序算法和时间复杂度控制。它适用于较小的 N，但一旦我接近较大的 N，Whosebug 是不可避免的。我认为将枢轴元素作为最后一个元素可能是造成这种情况的原因。

我的第一个想法是简单地始终使用中间元素作为枢轴元素来避免这种情况，但由于测试程序抛出 'unsorted exception'，这不是一个有效的解决方案。

有什么办法可以解决这个问题吗？

public class QuickSorter implements IntSorter{

int partition (int a[], int lo, int hi) {
    int pivot = a[hi]; // pivot element
    int i = (lo - 1);

    for (int j = lo; j <= hi - 1; j++) {
        if (a[j] < pivot) {
            i++;
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    int temp = a[i+1];
    a[i+1] = a[hi];
    a[hi] = temp;
    return (i + 1);
}



@Override
public void sort(int[] a) {

    int lo = 0;
    int hi = a.length-1;
    if (lo < hi) {
        int p = partition(a, lo, hi);
        sort(a, lo, p - 1);
        sort(a, p + 1, hi);
    }
}

private void sort(int[] a, int lo, int hi) {
    if (lo < hi) {
        int p = partition(a, lo, hi);
        sort(a, lo, p - 1);
        sort(a, p + 1, hi);
    }
}
}

测试代码：

private static void testSort(IntSorter sorter, int firstN, boolean ordered) {
    double t1 = 0;
    int N = firstN/2;

    while (t1 < 0.7 && N < 10000000) {
        N *= 2;
        int[] a = create(N, ordered);
        t1 = timeit(sorter, a);
        System.out.println("T("+N+")="+t1);
        ArrayUtil.testOrdered(a);
    }
    int[] a = create(4*N, ordered);
    double t4 = timeit(sorter, a);
    ArrayUtil.testOrdered(a);
    double t01 = t1 / (N   * Math.log(N  )); 
    double t04 = t4 / (4*N * Math.log(4*N));
    System.out.println("T("+4*N+")="+t4+" growth per N log N: "+t04/t01);
    if (t04/t01 > 1.25) {
        System.out.println(sorter.getClass().getName()+".sort appears not to run in O(N log N) time");
        System.exit(1);
    }
}

public static void testOrdered(int[] a) {
    int N = a.length;
    for (int i = 1; i < N; i++) {
        if (a[i] < a[i-1]) {
            throw new SortingException("Not sorted, a["+(i-1)+"] > a["+i+"]");
        }
    }
}

Answer 1

正如 Thomas 评论的那样，使用中间元素作为基准应该可以正常工作。实际上，这是一个常见的选择，因为它适用于恰好已经完全或部分排序的输入数组。

至于避免堆栈溢出，一种常见的方法是仅在分区步骤后对较短的部分进行递归 - 这确保至少将在每个级别处理的数组减半，例如一个包含 1,000,000 个元素的数组的最大调用深度大约为 20 ( log2(1,000,000) ).

所以，而不是

private void sort(int[] a, int lo, int hi) {
    if (lo < hi) {
        int p = partition(a, lo, hi);
        sort(a, lo, p - 1);
        sort(a, p + 1, hi);
    }
}

你会

private void sort(int[] a, int lo, int hi) {
    while (lo < hi) {
        int p = partition(a, lo, hi);
        // recurse on smaller part, loop on larger part
        if (((p - 1) - lo) > (hi - (p + 1))) {
          sort(a, p + 1, hi);
          hi = p - 1;
        }
        else {
          sort(a, lo, p - 1);
          lo = p + 1;
        }
    }
}

Answer 2

在使用下面的方法排序之前打乱数组似乎也解决了我遇到的问题

public void shuffle(int[] a) {
    int N = a.length;
    Random randomGenerator = new Random();
    for (int i = 0; i < N; i++) {
        int r = i + randomGenerator.nextInt(N-i);     // between i and N-1
        int t = a[i]; a[i] = a[r]; a[r] = t;
    }
}

第一个和最后一个枢轴元素与非常大的 N 的通用放置

First and last pivot element vs generic placement with very large N

java

arrays

sorting

algorithm

quicksort