快速排序和归并排序的时间消耗对比

背景知识

快速排序和归并排序都基于递归的思想。其中归并排序每次将输入平均划分为两部分，因此时间复杂度为O(nlogn)。而快速排序根据选择的 pivot将其余的数据划分为大于s[pivot]和小于s[pivot]的，只有当s[pivot]恰好是中位数时，时间复杂度才是O(nlogn)，最坏情况下， 每次选择的pivot都位于边缘，如下图所示。这样时间复杂度就退化为$O(n^2)$

以上的分析是基于内存模型和大 O表示法的，而在实际运行过程中，由于归并排序归并需要的时间比快速排序时间长，因此时间的比较可能出现不一样的结果。本文将对其实际性能进行对比。本实验基于java 1.8。

实验结果

数组长度	初始化情况	快速排序	归并排序	System
1e6	有序	StackOverflow	496	5
1e6	无序	153	663	180
1e8	有序	StackOverflow	496	131
1e6	无序	17380	too long	17471

时间单位：ms

结果分析

可以看出，当数组是有序的时候，我们实现的快速排序算法性能会急剧下降，具体原因文章开头已经介绍了。对于这种情况，有以下几种解决方式：

1. 排序之前对数组进行随机排列，时间复杂度为O(n)。

2. 检查数组之前是否是有序的，在java Arrays.sort()中，如果数组长度超过286，且有序的子片段不超过67，则通过归并排序进行合并。

public static <T> void sort(T[] a, Comparator<? super T> c) {}

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

核心代码

快速排序

public class QuickSort {
    public static void main(String[] args){
        int[] s = new int[] {4,1,2,3,5, 10, 9, 7, 6, 4};
        new QuickSort().quickSort(s, 0, s.length - 1);
        System.out.println(Arrays.toString(s));
    }

    public void quickSort(int[] s, int l, int h) {
        int p;
        if (h - l > 0) {
            p = parition(s, l, h);
            quickSort(s,l,p-1);
            quickSort(s,p+1,h);
        }
    }

    private int parition(int[] s, int l, int h) {
        int i; /* counter */
        int p; /* pivot element index */
        int firsthigh; /* next position to store lowest num */

        p = h;
        firsthigh = l;

        for (i = l; i < h; i ++) {
            if (s[i] < s[p]) {
                swap(s, i, firsthigh);
                firsthigh ++;
            }
        }
        swap(s, p , firsthigh);
        return (firsthigh);
    }

    private void swap(int[] s, int i, int i1) {
        int temp = s[i];
        s[i] = s[i1];
        s[i1] = temp;
    }
}

归并排序

public class MergeSort {

    public static void main(String[] args){
        int[] s = new int[] {4,1,2,3,5, 10, 9, 7, 6, 4};
        new MergeSort().mergesort(s, 0, s.length - 1);
        System.out.println(Arrays.toString(s));
    }

    void mergesort(int[] s, int low, int high)
    {
        int i; /* counter */
        int middle; /* index of middle element */
        if (low < high) {
            middle = (low+high)/2;
            mergesort(s,low,middle);
            mergesort(s,middle+1,high);
            merge(s, low, middle, high);
        }
    }

    private void merge(int[] s, int low, int middle, int high) {
        int i; // counter
        Queue<Integer> buffer1, buffer2;
        buffer1 = new LinkedList<>();
        buffer2 = new LinkedList<>();
        for (i = low; i <= middle; i++) {
            buffer1.offer(s[i]);
        }
        for (i = middle + 1; i <= high; i++) {
            buffer2.offer(s[i]);
        }
        i = low;
        while ((!buffer1.isEmpty()) && (!buffer2.isEmpty())) {
            if (buffer1.peek() <= buffer2.peek()) { // equals keeps stability
                s[i++] = buffer1.poll();
            } else {
                s[i++] = buffer2.poll();
            }
        }
        while (!buffer1.isEmpty()) {
            s[i++] = buffer1.poll();
        }
        while (!buffer2.isEmpty()) {
            s[i++] = buffer2.poll();
        }
    }


}