快速排序的实施似乎比Mergesort花费更多时间

Question

我试图对QuickSort进行实现(对于小数组,中间值为3分区元素和插入排序),并将其与MergeSort的实现进行比较,但即使QuickSort平均时间应该优于MergeSort,每次我执行它,似乎需要更多的时间来排序一个数组(即使是一个随机顺序).知道为什么会这样吗？

快速排序:

public class Quick {

    private static final int M = 10;
    private static Random random = new Random();

    public void sort(int[] a) {
        sort(a, 0, a.length - 1);
        insertionSort(a, 0, a.length - 1);
    }

    private void sort(int[] a, int lo, int hi) {
        if (hi - lo <= 10) return;
        swap(a, lo, pivot(a, lo, hi));
        int lt = lo, gt = hi;
        int v = a[lo];
        int i = lo;
        while (i <= gt) {
            if      (a[i] < v) swap(a, lt++, i++);
            else if (a[i] > v) swap(a, i, gt--);
            else              i++;
        }

        // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
        sort(a, lo, lt-1);
        sort(a, gt+1, hi);
    }

    private int pivot(int[] a, int lo, int hi) {
        int     r1 = random.nextInt(hi - lo) + lo,
                r2 = random.nextInt(hi - lo) + lo,
                r3 = random.nextInt(hi - lo) + lo;
        return median3(a, r1, r2, r3);
    }

    private void swap(int[] a, int i, int j) {
        if (i == j) return;
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    private static int median3(int[] a, int i, int j, int k) {
        return (a[i] < a[j] ?
                (a[j] < a[k] ? j : a[i] < a[k] ? k : i) :
                (a[k] < a[j] ? j : a[k] < a[i] ? k : i));
    }

    private void insertionSort(int[] a, int lo, int hi) {
        for (int i = lo; i <= hi; i++)
            for (int j = i; j > lo && a[j] < a[j-1]; j--)
                swap(a, j, j-1);
    }
}

归并:

public class Merge {

    public void sort(int[] a) {
        int[] aux = new int[a.length];
        sort(a, aux, 0, a.length - 1);
    }

    private void sort(int[] a, int[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }

    private void merge(int[] a, int[] aux, int lo, int mid, int hi) {
        System.arraycopy(a, lo, aux, lo, hi + 1 - lo);
        // Merge
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if      (i > mid)           a[k] = aux[j++];
            else if (j > hi)            a[k] = aux[i++];
            else if (aux[j] < aux[i])   a[k] = aux[j++];
            else                        a[k] = aux[i++];
        }
    }
}

例如,当我为10个长度为10 ^ 8的随机数组运行此算法时,MergeSort平均执行13385.8 ms,而QuickSort平均需要14096.7 ms.

为了澄清,这是我测量执行时间的方式

public static void main(String[] args) {
    int pow = (int) Math.pow(10, 8);
    int[] a, b;
    double[]    m1 = new double[10],
                m2 = m1.clone(),
    double st, et;
    Merge merge = new Merge();
    Quick quick = new Quick();
    for (int i = 0; i < 10; i++) {
        a = randomArray(pow);
        b = a.clone();
        st = currentTimeMillis();
        merge.sort(a);
        et = currentTimeMillis();
        m1[i] = et - st;
        st = currentTimeMillis();
        quick.sort(b);
        et = currentTimeMillis();
        m2[i] = et - st;
    }
    out.println("MergeSort: " + mean(m1));
    out.println("QuickSort: " + mean(m2));
}
private static int[] randomArray(int n) {
    r = new Random();
    int[] a = new int[n];
    for (int i = 0; i < a.length; i++) a[i] = r.nextInt();
    return a;
}

Answer 1

在尝试了很多方法来找出问题所在之后，我更改了创建随机数组的函数，结果QuickSort现在实际上工作得更快了。我真的不知道为什么，但似乎我创建数组的方式对QuickSort. 现在，我所做的不是生成随机整数数组，而是生成一个从 1 到 n 的数组，然后对其进行打乱，如下所示：

public static int[] permutation(int n) {
    int[] a = new int[n];

    for (int i = 0; i < n; ++i)  a[i] = i + 1;

    for (int i = 0; i < n; i++) {
        int r = i + rnd.nextInt(n - i),
            tmp = a[i];

        a[i] = a[r];
        a[r] = tmp;
    }

    return a;
}