摘要：本文介紹幾種常見(jiàn)排序算法選擇排序，插入排序，希爾排序，歸并排序，快速排序，堆排序，對(duì)算法的思路性質(zhì)特點(diǎn)具體步驟實(shí)現(xiàn)以及圖解進(jìn)行了全面的說(shuō)明。最后對(duì)幾種排序算法進(jìn)行了比較和總結(jié)。

本文介紹幾種常見(jiàn)排序算法（選擇排序，插入排序，希爾排序，歸并排序，快速排序，堆排序），對(duì)算法的思路、性質(zhì)、特點(diǎn)、具體步驟、java實(shí)現(xiàn)以及trace圖解進(jìn)行了全面的說(shuō)明。最后對(duì)幾種排序算法進(jìn)行了比較和總結(jié)。

本文所有圖片均截圖自coursera上普林斯頓的課程《Algorithms, Part I》中的Slides

相關(guān)命題的證明可參考《算法（第4版）》

源碼可在官網(wǎng)下載,也可以在我的github倉(cāng)庫(kù) algorithms-learning下載，已經(jīng)使用maven構(gòu)建

倉(cāng)庫(kù)下載：git clone git@github.com:brianway/algorithms-learning.git

java: Interface Comparable

Java中很多類(lèi)已經(jīng)實(shí)現(xiàn)了Comparable接口，用戶(hù)也可自定義類(lèi)型實(shí)現(xiàn)該接口

total order:

Antisymmetry(反對(duì)稱(chēng)性): if v ≤ w and w ≤ v, then v = w.

Transitivity(傳遞性): if v ≤ w and w ≤ x, then v ≤ x.

Totality: either v ≤ w or w ≤ v or both.

注意： The <= operator for double is not a total order，violates totality: (Double.NaN <= Double.NaN) is false

通用代碼：

// Less. Is item v less than w ?
private static boolean less(Comparable v, Comparable w) {
    return v.compareTo(w) < 0;
}

//Exchange. Swap item in array a[] at index i with the one at index j
private static void exch(Comparable[] a,, int i, int j) {
    Comparable swap = a[i];
    a[i] = a[j];
    a[j] = swap;
}

思路：

在第i次迭代中，在剩下的(即未排序的)元素中找到最小的元素

將第i個(gè)元素與最小的元素交換位置

現(xiàn)象：

設(shè)已排序的和未排序的交界處為 ↑，則每次循環(huán)， ↑ 從左往右移動(dòng)一個(gè)位置

↑ 左邊的元素（包括↑）固定了，且升序

↑ 右邊的任一元素全部比左邊的所有元素都大

步驟：

move the pointer to the right

indentify index of minimun entry on right

exchange into positon

java實(shí)現(xiàn)：

public static void sort(Comparable[] a) {
    int N = a.length;
    for (int i = 0; i < N; i++) {
        int min = i;
        for (int j = i+1; j < N; j++) {
            if (less(a[j], a[min])) min = j;
        }
        exch(a, i, min);
    }
}

特點(diǎn)：

運(yùn)行時(shí)間和輸入無(wú)關(guān)，無(wú)論輸入是已排序，時(shí)間復(fù)雜度都是O(n^2)

數(shù)據(jù)移動(dòng)最少，交換的次數(shù)和數(shù)組大小是線性關(guān)系

思路：

在第i次迭代中，將第i個(gè)元素與每一個(gè)它左邊且比它大的的元素交換位置

現(xiàn)象：

設(shè)已排序的和未排序的交界處為 ↑，則每次循環(huán)， ↑ 從左往右移動(dòng)一個(gè)位置

↑ 左邊的元素（包括↑）且升序，但位置不固定(因?yàn)楹罄m(xù)可能會(huì)因插入而移動(dòng))

↑ 右邊的元素還不可見(jiàn)

步驟：

Move the pointer to the right.

Moving from right to left, exchange a[i] with each larger entry to its left.

java實(shí)現(xiàn)：

public static void sort(Comparable[] a) {
    int N = a.length;
    for (int i = 0; i < N; i++) {
        for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
            exch(a, j, j-1);
        }
    }
}

inversion（倒置）：An inversion is a pair of keys that are out of order

部分有序：An array is partially sorted if the number of inversions is ≤ c N.

特點(diǎn)：

運(yùn)行時(shí)間和輸入有關(guān)，當(dāng)輸入已排序時(shí)，時(shí)間復(fù)雜度是O(n);

For partially-sorted arrays, insertion sort runs in linear time.(交換的次數(shù)等于輸入中倒置(inversion)的個(gè)數(shù))

插入排序適合部分有序數(shù)組，也適合小規(guī)模數(shù)組

希爾排序是基于插入排序的。

思路：

Move entries more than one position at a time by h-sorting the array

按照h的步長(zhǎng)進(jìn)行插入排序

現(xiàn)象：

數(shù)組中任意間隔為h的元素都是有序的

A g-sorted array remains g-sorted after h-sorting it.

性質(zhì)：

遞增數(shù)列一般采用3x+1：1,4,13,40,121,364.....，使用這種遞增數(shù)列的希爾排序所需的比較次數(shù)不會(huì)超過(guò)N的若干倍乘以遞增數(shù)列的長(zhǎng)度。

最壞情況下，使用3x+1遞增數(shù)列的希爾排序的比較次數(shù)是O(N^(3/2))

java實(shí)現(xiàn)：

public static void sort(Comparable[] a) {
    int N = a.length;

    // 3x+1 increment sequence:  1, 4, 13, 40, 121, 364, 1093, ... 
    int h = 1;
    while (h < N/3) h = 3*h + 1; 

    while (h >= 1) {
        // h-sort the array
        for (int i = h; i < N; i++) {
            for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
                exch(a, j, j-h);
            }
        }
        h /= 3;
    }
}

目標(biāo)：Rearrange array so that result is a uniformly random permutation

shuffle sort思路

為數(shù)組的每一個(gè)位置生成一個(gè)隨機(jī)實(shí)數(shù)

排序這個(gè)生成的數(shù)組

Knuth shuffle demo

In iteration i, pick integer r between 0 and i uniformly at random.

Swap a[i] and a[r].

correct variant: between i and N – 1

Mergesort--Java sort for objects.

Quicksort--Java sort for primitive types.

下面看看這兩種排序算法

思路：

Divide array into two halves.

Recursively sort each half.

Merge two halves.

Given two sorted subarrays a[lo] to a[mid] and a[mid+1] to a[hi],replace with sorted subarray a[lo] to a[hi]

步驟：

先將所有元素復(fù)制到aux[]中，再歸并回a[]中。

歸并時(shí)的四個(gè)判斷：

左半邊用盡(取右半邊元素)

右半邊用盡(取左半邊元素)

右半邊的當(dāng)前元素小于左半邊的當(dāng)前元素(取右半邊的元素)

右半邊的當(dāng)前元素大于/等于左半邊的當(dāng)前元素(取左半邊的元素)

merging java實(shí)現(xiàn)：

 // stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
    // precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
 
    // copy to aux[]
    for (int k = lo; k <= hi; k++) {
        aux[k] = a[k]; 
    }

    // merge back to a[]
    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 (less(aux[j], aux[i])) a[k] = aux[j++];
        else                           a[k] = aux[i++];
    }
}

mergesort java實(shí)現(xiàn)：

// mergesort a[lo..hi] using auxiliary array aux[lo..hi]
private static void sort(Comparable[] a, Comparable[] 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); //歸并結(jié)果
}

自頂向下的歸并排序的軌跡圖

由圖可知，原地歸并排序的大致趨勢(shì)是，先局部排序，再擴(kuò)大規(guī)模；先左邊排序，再右邊排序；每次都是左邊一半局部排完且merge了，右邊一半才開(kāi)始從最局部的地方開(kāi)始排序。

改進(jìn)

對(duì)小規(guī)模子數(shù)組使用插入排序

測(cè)試數(shù)組是否已經(jīng)有序（左邊最大<右邊最小時(shí)，直接返回）

不將元素復(fù)制到輔助數(shù)組(節(jié)省時(shí)間而非空間)

思路：

先歸并微型數(shù)組，從兩兩歸并開(kāi)始(每個(gè)元素理解為大小為1的數(shù)組)

重復(fù)上述步驟，逐步擴(kuò)大歸并的規(guī)模，2,4,8.....

java實(shí)現(xiàn)：

public class MergeBU{
   private static void merge(...){ /* as before */ }
 
   public static void sort(Comparable[] a){
     int N = a.length;
     Comparable[] aux = new Comparable[N];
     for (int sz = 1; sz < N; sz = sz+sz)
     for (int lo = 0; lo < N-sz; lo += sz+sz)
     merge(a, aux, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
   }
}

自底向上的歸并排序的軌跡圖

由圖可知，自底向上歸并排序的大致趨勢(shì)是，先局部排序，逐步擴(kuò)大到全局排序；步調(diào)均勻，穩(wěn)步擴(kuò)大

思路：

Shuffle the array.

Partition(切分) so that, for some j

entry a[j] is in place

no larger entry to the left of j

no smaller entry to the right of j

Sort each piece recursively.

其中很重要的一步就是Partition(切分)，這個(gè)過(guò)程使得滿(mǎn)足以下三個(gè)條件:

對(duì)于某個(gè)j,a[j]已經(jīng)排定;

a[lo]到a[j-1]中的所有元素都不大于a[j];

a[j+1]到a[hi]中的所有元素都不小于a[j];

partition java實(shí)現(xiàn)

// partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <= a[j+1..hi]
// and return the index j.
private static int partition(Comparable[] a, int lo, int hi) {
    int i = lo;
    int j = hi + 1;
    Comparable v = a[lo];
    while (true) { 

        // find item on lo to swap
        while (less(a[++i], v))
            if (i == hi) break;

        // find item on hi to swap
        while (less(v, a[--j]))
            if (j == lo) break;      // redundant since a[lo] acts as sentinel

        // check if pointers cross
        if (i >= j) break;

        exch(a, i, j);
    }

    // put partitioning item v at a[j]
    exch(a, lo, j);

    // now, a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
    return j;
}

快排java實(shí)現(xiàn)：

public static void sort(Comparable[] a) {
    StdRandom.shuffle(a);
    sort(a, 0, a.length - 1);
}

// quicksort the subarray from a[lo] to a[hi]
private static 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);
    assert isSorted(a, lo, hi);
}

快排的軌跡圖

由圖可知，和歸并排序不同，快排的大致趨勢(shì)是，先全局大體有個(gè)走勢(shì)——左邊比右邊小，逐步細(xì)化到局部；也是先左后右；局部完成時(shí)全部排序也就完成了。

一些實(shí)現(xiàn)的細(xì)節(jié)：

原地切分：不使用輔助數(shù)組

別越界：測(cè)試條件(j == lo)是冗余的(a[lo]不可能比自己小)；

保持隨機(jī)性：初始時(shí)的隨機(jī)打亂跟重要

終止循環(huán)

處理切分元素值有重復(fù)的情況：這里可能出問(wèn)題

性質(zhì)：

快排是in-place的

快排不穩(wěn)定

改進(jìn)

對(duì)小規(guī)模子數(shù)組使用插入排序

三取樣切分

思路：

Let v be partitioning item a[lo].

Scan i from left to right.

(a[i] < v): exchange a[lt] with a[i]; increment both lt and i

(a[i] > v): exchange a[gt] with a[i]; decrement gt

(a[i] == v): increment i

主要是通過(guò)增加一個(gè)指針來(lái)實(shí)現(xiàn)的。普通的快拍只有l(wèi)o和high兩個(gè)指針，故只能記錄大于(high右邊)和小于(lo左邊)兩個(gè)區(qū)間，等于只能并入其中一個(gè)；這里增加了使用了lt,i,gt三個(gè)指針，從而達(dá)到記錄大于(gt右邊)、小于(lt左邊)和等于(lt和i之間)三個(gè)區(qū)間。

三切分的示意圖

三向切分的java實(shí)現(xiàn)：

// quicksort the subarray a[lo .. hi] using 3-way partitioning
private static void sort(Comparable[] a, int lo, int hi) { 
    if (hi <= lo) return;
    int lt = lo, gt = hi;
    Comparable v = a[lo];
    int i = lo;
    while (i <= gt) {
        int cmp = a[i].compareTo(v);
        if      (cmp < 0) exch(a, lt++, i++);
        else if (cmp > 0) exch(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);
}

思路：

Create max-heap with all N keys.

Repeatedly remove the maximum key.

swim:由下至上的堆有序化

sink:由上至下的對(duì)有序化

堆排序主要分為兩個(gè)階段：

堆的構(gòu)造

下沉排序

java實(shí)現(xiàn)如下：

public static void sort(Comparable[] pq) {
    int N = pq.length;
    //堆的構(gòu)造
    for (int k = N/2; k >= 1; k--)
        sink(pq, k, N);
    
    //下沉排序
    while (N > 1) {
        exch(pq, 1, N--);
        sink(pq, 1, N);
    }
}

堆排序的軌跡圖

由圖看出，堆排序的趨勢(shì)是，堆構(gòu)造階段，大致是降序的走勢(shì)，到了下沉階段，從右到左（或者說(shuō)從后往前）逐步有序

Significance： In-place sorting algorithm with N log N worst-case.

Mergesort: no, linear extra space.

Quicksort: no, quadratic time in worst case

缺點(diǎn)

Inner loop longer than quicksort’s.

Makes poor use of cache memory.

Not stable(不穩(wěn)定)

排序算法總結(jié)表

最好情況和最壞情況：參見(jiàn)上面的表格

關(guān)于穩(wěn)定性：

穩(wěn)定性，插入排序，歸并排序

不穩(wěn)定：選擇排序，快排，希爾排序，堆排序

原因： Long-distance exchange

關(guān)于額外空間：除了歸并排序需要線性的額外空間，其他都是in-place的

對(duì)于長(zhǎng)度為N的數(shù)組，選擇排序需要N^2/2次比較和N次交換(pf見(jiàn)P156)

對(duì)于隨機(jī)排列的長(zhǎng)度為N的且主鍵不重復(fù)的數(shù)組（pf見(jiàn)P157）

平均情況下插入排序需要~N^2/4次比較和~N^2/4次交換

最壞情況下需要~N^2/2次比較和~N^2/2次交換，

最好情況下需要N-1次比較和0次交換。

Mergesort uses at most N lg N compares and 6 N lg N array accesses to sort any array of size N. (pf見(jiàn)P173)

Mergesort uses extra space proportional to N.(The array aux[] needs to be of size N for the last merge.)

Any compare-based sorting algorithm must use at least lg ( N ! ) ~ N lg N compares in the worst-case.(pf見(jiàn)P177)

長(zhǎng)度為N的無(wú)重復(fù)數(shù)組排序，快速排序平均需要~2N ln N 次比較（以及1/6即1/3 N ln N的交換）

最多需要約N^2/2次比較

最少需要~N lg N 次比較

用下沉操作由N個(gè)元素構(gòu)造堆只需少于2N次比較以及少于N次交換(pf見(jiàn)P206)

將N個(gè)元素排序，堆排序只需少于（2NlgN+2N）次比較以及一半次數(shù)的交換(pf見(jiàn)P208)

作者@brianway更多文章：個(gè)人網(wǎng)站 | CSDN | oschina