一、兩者對比

快速排序

• 當兩個子數(shù)組都有序時，整個數(shù)組也就有序
• 遞歸調用發(fā)生在處理整個數(shù)組之后
• 切分的位置取決于數(shù)組的內容

歸并排序

• 將數(shù)組分為兩個子數(shù)組分別排序，并將有序的子數(shù)組歸并，以將整個數(shù)組排序
• 遞歸調用發(fā)生在處理整個數(shù)組之前
• 一個數(shù)組被等分為兩半

二、快速排序詳解

源碼解析

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

private void sort(int[] 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(int[] a, int lo, int hi) {
    int i = lo;         // 左指針開始位置
    int j = hi + 1;     // 右指針開始位置
    int v = a[lo];      // 軸點
    while (true) {
        while (i < hi && a[++i] < v) {} // 從左向右掃描，直到找到一個大于等于軸點的元素
        while (lo < j && a[--j] > v) {} // 從右向左掃描，直到找到一個小于等于軸點的元素
        if (i >= j) break;
        exch(a, i, j);                  // 交換這兩個沒有排好的元素
    }
    // 軸點和左子數(shù)組最右元素交換
    // from   v    <=v    >=v
    //  to   <=v    v     >=v
    exch(a, lo, j);
    return j;           // 返回軸點位置
}

private void exch(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

// Fisher–Yates shuffle algorithm
private void shuffle(int[] a) {
    Random random = new Random();
    for (int i = a.length - 1; i >= 0; i--) {
        // 0 <= r <= i
        int r = random.nextInt(i + 1);
        exch(a, i, r);
    }
}

快速排序最好和最壞的情況

最好情況：

• 軸點（pivot）總是落在子數(shù)組的中位數(shù)上

最壞情況：

• 壞排序：原數(shù)組已經(jīng)有序
• 壞元素：所有元素都是重復的

在快速排序中，一個數(shù)組的partition的遞歸函數(shù)調用樹看上去就像二叉樹一樣，如果pivot每次都接近子數(shù)組的中位數(shù)，那么整棵函數(shù)調用二叉樹也會更接近平衡。

三、歸并排序詳解

源碼解析

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

private void sort(int[] a, int lo, int hi) {
    if (hi <= lo) return;
    int mid = lo + (lo + hi) / 2;
    sort(a, lo, mid);       // 排序左半邊
    sort(a, mid + 1, hi);   // 排序右半邊
    merge(a, lo, mid, hi);
}

private void merge(int[] a, int lo, int mid, int hi) {
    for (int k = lo; k <= hi; k++) {
        aux[k] = a[k];
    }
    int i = lo;         // 左半邊起始位置
    int 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++];  // 左半邊元素更小，取左半邊元素
    }
}

四、參考資料

• Robert Sedgewick & Kevin Wayne《算法（第四版）》

• UC Berkeley CS 61B