本文首發(fā)于我的個(gè)人博客：尾尾部落

排序算法是最經(jīng)典的算法知識(shí)。因?yàn)槠鋵?shí)現(xiàn)代碼短，應(yīng)該廣，在面試中經(jīng)常會(huì)問到排序算法及其相關(guān)的問題。一般在面試中最常考的是快速排序和歸并排序等基本的排序算法，并且經(jīng)常要求現(xiàn)場(chǎng)手寫基本的排序算法。如果這些問題回答不好，估計(jì)面試就涼涼了。所以熟練掌握排序算法思想及其特點(diǎn)并能夠熟練地手寫代碼至關(guān)重要。

下面介紹幾種常見的排序算法：冒泡排序、選擇排序、插入排序、歸并排序、快速排序、希爾排序、堆排序、計(jì)數(shù)排序、桶排序、基數(shù)排序的思想，其代碼均采用Java實(shí)現(xiàn)。

1. 冒泡排序

冒泡排序是一種簡(jiǎn)單的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果它們的順序錯(cuò)誤就把它們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

算法描述

1. 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換它們兩個(gè)；
2. 對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)，這樣在最后的元素應(yīng)該會(huì)是最大的數(shù)；
3. 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)；
4. 重復(fù)步驟1~3，直到排序完成。

動(dòng)圖演示

冒泡排序

算法實(shí)現(xiàn)

public static void bubbleSort(int[] arr) {
    int temp = 0;
    for (int i = arr.length - 1; i > 0; i--) { // 每次需要排序的長(zhǎng)度
        for (int j = 0; j < i; j++) { // 從第一個(gè)元素到第i個(gè)元素
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }//loop j
    }//loop i
}// method bubbleSort

穩(wěn)定性

在相鄰元素相等時(shí)，它們并不會(huì)交換位置，所以，冒泡排序是穩(wěn)定排序。

適用場(chǎng)景

冒泡排序思路簡(jiǎn)單，代碼也簡(jiǎn)單，特別適合小數(shù)據(jù)的排序。但是，由于算法復(fù)雜度較高，在數(shù)據(jù)量大的時(shí)候不適合使用。

代碼優(yōu)化

在數(shù)據(jù)完全有序的時(shí)候展現(xiàn)出最優(yōu)時(shí)間復(fù)雜度，為O(n)。其他情況下，幾乎總是O( n^2 )。因此，算法在數(shù)據(jù)基本有序的情況下，性能最好。
要使算法在最佳情況下有O(n)復(fù)雜度，需要做一些改進(jìn)，增加一個(gè)swap的標(biāo)志，當(dāng)前一輪沒有進(jìn)行交換時(shí)，說明數(shù)組已經(jīng)有序，沒有必要再進(jìn)行下一輪的循環(huán)了，直接退出。

public static void bubbleSort(int[] arr) {
    int temp = 0;
    boolean swap;
    for (int i = arr.length - 1; i > 0; i--) { // 每次需要排序的長(zhǎng)度
        swap=false;
        for (int j = 0; j < i; j++) { // 從第一個(gè)元素到第i個(gè)元素
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swap=true;
            }
        }//loop j
        if (swap==false){
            break;
        }
    }//loop i
}// method bubbleSort

2. 選擇排序

選擇排序是一種簡(jiǎn)單直觀的排序算法，它也是一種交換排序算法，和冒泡排序有一定的相似度，可以認(rèn)為選擇排序是冒泡排序的一種改進(jìn)。

算法描述

1. 在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?/li>
2. 從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。
3. 重復(fù)第二步，直到所有元素均排序完畢。

動(dòng)圖演示

選擇排序

算法實(shí)現(xiàn)

public static void selectionSort(int[] arr) {
    int temp, min = 0;
    for (int i = 0; i < arr.length - 1; i++) {
        min = i;
        // 循環(huán)查找最小值
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[min] > arr[j]) {
                min = j;
            }
        }
        if (min != i) {
            temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
}

穩(wěn)定性

用數(shù)組實(shí)現(xiàn)的選擇排序是不穩(wěn)定的，用鏈表實(shí)現(xiàn)的選擇排序是穩(wěn)定的。
不過，一般提到排序算法時(shí)，大家往往會(huì)默認(rèn)是數(shù)組實(shí)現(xiàn)，所以選擇排序是不穩(wěn)定的。

適用場(chǎng)景

選擇排序?qū)崿F(xiàn)也比較簡(jiǎn)單，并且由于在各種情況下復(fù)雜度波動(dòng)小，因此一般是優(yōu)于冒泡排序的。在所有的完全交換排序中，選擇排序也是比較不錯(cuò)的一種算法。但是，由于固有的O(n^2)復(fù)雜度，選擇排序在海量數(shù)據(jù)面前顯得力不從心。因此，它適用于簡(jiǎn)單數(shù)據(jù)排序。

3. 插入排序

插入排序是一種簡(jiǎn)單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。

算法描述

1. 把待排序的數(shù)組分成已排序和未排序兩部分，初始的時(shí)候把第一個(gè)元素認(rèn)為是已排好序的。
2. 從第二個(gè)元素開始，在已排好序的子數(shù)組中尋找到該元素合適的位置并插入該位置。
3. 重復(fù)上述過程直到最后一個(gè)元素被插入有序子數(shù)組中。

動(dòng)圖演示

插入排序

算法實(shí)現(xiàn)

public static void insertionSort(int[] arr){
    for (int i=1; i<arr.length; ++i){
        int value = arr[i];
        int position=i;
        while (position>0 && arr[position-1]>value){
            arr[position] = arr[position-1];
            position--;
        }
        arr[position] = value;
    }//loop i
}

穩(wěn)定性

由于只需要找到不大于當(dāng)前數(shù)的位置而并不需要交換，因此，直接插入排序是穩(wěn)定的排序方法。

適用場(chǎng)景

插入排序由于O( n^2 )的復(fù)雜度，在數(shù)組較大的時(shí)候不適用。但是，在數(shù)據(jù)比較少的時(shí)候，是一個(gè)不錯(cuò)的選擇，一般做為快速排序的擴(kuò)充。例如，在STL的sort算法和stdlib的qsort算法中，都將插入排序作為快速排序的補(bǔ)充，用于少量元素的排序。又如，在JDK 7 java.util.Arrays所用的sort方法的實(shí)現(xiàn)中，當(dāng)待排數(shù)組長(zhǎng)度小于47時(shí)，會(huì)使用插入排序。

4. 歸并排序

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為2-路歸并。

算法描述

兩種方法

• 遞歸法（Top-down）

1. 申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列
2. 設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
3. 比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置
4. 重復(fù)步驟3直到某一指針到達(dá)序列尾
5. 將另一序列剩下的所有元素直接復(fù)制到合并序列尾

• 迭代法（Bottom-up）

原理如下（假設(shè)序列共有n個(gè)元素）：

1. 將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作，形成ceil(n/2)個(gè)序列，排序后每個(gè)序列包含兩/一個(gè)元素
2. 若此時(shí)序列數(shù)不是1個(gè)則將上述序列再次歸并，形成ceil(n/4)個(gè)序列，每個(gè)序列包含四/三個(gè)元素
3. 重復(fù)步驟2，直到所有元素排序完畢，即序列數(shù)為1

動(dòng)圖演示

歸并排序

算法實(shí)現(xiàn)

public static void mergeSort(int[] arr){
    int[] temp =new int[arr.length];
    internalMergeSort(arr, temp, 0, arr.length-1);
}
private static void internalMergeSort(int[] arr, int[] temp, int left, int right){
    //當(dāng)left==right的時(shí)，已經(jīng)不需要再劃分了
    if (left<right){
        int middle = (left+right)/2;
        internalMergeSort(arr, temp, left, middle);          //左子數(shù)組
        internalMergeSort(arr, temp, middle+1, right);       //右子數(shù)組
        mergeSortedArray(arr, temp, left, middle, right);    //合并兩個(gè)子數(shù)組
    }
}
// 合并兩個(gè)有序子序列
private static void mergeSortedArray(int arr[], int temp[], int left, int middle, int right){
    int i=left;      
    int j=middle+1;
    int k=0;
    while (i<=middle && j<=right){
        temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    }
    while (i <=middle){
        temp[k++] = arr[i++];
    }
    while ( j<=right){
        temp[k++] = arr[j++];
    }
    //把數(shù)據(jù)復(fù)制回原數(shù)組
    for (i=0; i<k; ++i){
        arr[left+i] = temp[i];
    }
}

穩(wěn)定性

因?yàn)槲覀冊(cè)谟龅较嗟鹊臄?shù)據(jù)的時(shí)候必然是按順序“抄寫”到輔助數(shù)組上的，所以，歸并排序同樣是穩(wěn)定算法。

適用場(chǎng)景

歸并排序在數(shù)據(jù)量比較大的時(shí)候也有較為出色的表現(xiàn)（效率上），但是，其空間復(fù)雜度O(n)使得在數(shù)據(jù)量特別大的時(shí)候（例如，1千萬數(shù)據(jù)）幾乎不可接受。而且，考慮到有的機(jī)器內(nèi)存本身就比較小，因此，采用歸并排序一定要注意。

5. 快速排序

快速排序是一個(gè)知名度極高的排序算法，其對(duì)于大數(shù)據(jù)的優(yōu)秀排序性能和相同復(fù)雜度算法中相對(duì)簡(jiǎn)單的實(shí)現(xiàn)使它注定得到比其他算法更多的寵愛。

算法描述

1. 從數(shù)列中挑出一個(gè)元素，稱為"基準(zhǔn)"（pivot），
2. 重新排序數(shù)列，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面（相同的數(shù)可以到任何一邊）。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作。
3. 遞歸地（recursively）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。

動(dòng)圖演示

快速排序

算法實(shí)現(xiàn)

public static void quickSort(int[] arr){
    qsort(arr, 0, arr.length-1);
}
private static void qsort(int[] arr, int low, int high){
    if (low >= high)
        return;
    int pivot = partition(arr, low, high);        //將數(shù)組分為兩部分
    qsort(arr, low, pivot-1);                   //遞歸排序左子數(shù)組
    qsort(arr, pivot+1, high);                  //遞歸排序右子數(shù)組
}
private static int partition(int[] arr, int low, int high){
    int pivot = arr[low];     //基準(zhǔn)
    while (low < high){
        while (low < high && arr[high] >= pivot) --high;
        arr[low]=arr[high];             //交換比基準(zhǔn)大的記錄到左端
        while (low < high && arr[low] <= pivot) ++low;
        arr[high] = arr[low];           //交換比基準(zhǔn)小的記錄到右端
    }
    //掃描完成，基準(zhǔn)到位
    arr[low] = pivot;
    //返回的是基準(zhǔn)的位置
    return low;
}

穩(wěn)定性

快速排序并不是穩(wěn)定的。這是因?yàn)槲覀儫o法保證相等的數(shù)據(jù)按順序被掃描到和按順序存放。

適用場(chǎng)景

快速排序在大多數(shù)情況下都是適用的，尤其在數(shù)據(jù)量大的時(shí)候性能優(yōu)越性更加明顯。但是在必要的時(shí)候，需要考慮下優(yōu)化以提高其在最壞情況下的性能。

6. 堆排序

堆排序(Heapsort)是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，它是選擇排序的一種?？梢岳脭?shù)組的特點(diǎn)快速定位指定索引的元素。堆排序就是把最大堆堆頂?shù)淖畲髷?shù)取出，將剩余的堆繼續(xù)調(diào)整為最大堆，再次將堆頂?shù)淖畲髷?shù)取出，這個(gè)過程持續(xù)到剩余數(shù)只有一個(gè)時(shí)結(jié)束。

樹的概念

關(guān)于樹的概念請(qǐng)參考：[算法總結(jié)] 二叉樹

堆的概念

堆是一種特殊的完全二叉樹（complete binary tree）。完全二叉樹的一個(gè)“優(yōu)秀”的性質(zhì)是，除了最底層之外，每一層都是滿的，這使得堆可以利用數(shù)組來表示（普通的一般的二叉樹通常用鏈表作為基本容器表示），每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)數(shù)組中的一個(gè)元素。
如下圖，是一個(gè)堆和數(shù)組的相互關(guān)系：

image

對(duì)于給定的某個(gè)結(jié)點(diǎn)的下標(biāo) i，可以很容易的計(jì)算出這個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)、孩子結(jié)點(diǎn)的下標(biāo)：

• Parent(i) = floor(i/2)，i 的父節(jié)點(diǎn)下標(biāo)
• Left(i) = 2i，i 的左子節(jié)點(diǎn)下標(biāo)
• Right(i) = 2i + 1，i 的右子節(jié)點(diǎn)下標(biāo)

二叉堆一般分為兩種：最大堆和最小堆。
最大堆：
最大堆中的最大元素值出現(xiàn)在根結(jié)點(diǎn)（堆頂）
堆中每個(gè)父節(jié)點(diǎn)的元素值都大于等于其孩子結(jié)點(diǎn)（如果存在）

image

image

堆排序原理

堆排序就是把最大堆堆頂?shù)淖畲髷?shù)取出，將剩余的堆繼續(xù)調(diào)整為最大堆，再次將堆頂?shù)淖畲髷?shù)取出，這個(gè)過程持續(xù)到剩余數(shù)只有一個(gè)時(shí)結(jié)束。在堆中定義以下幾種操作：

• 最大堆調(diào)整（Max-Heapify）：將堆的末端子節(jié)點(diǎn)作調(diào)整，使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn)
• 創(chuàng)建最大堆（Build-Max-Heap）：將堆所有數(shù)據(jù)重新排序，使其成為最大堆
• 堆排序（Heap-Sort）：移除位在第一個(gè)數(shù)據(jù)的根節(jié)點(diǎn)，并做最大堆調(diào)整的遞歸運(yùn)算
  繼續(xù)進(jìn)行下面的討論前，需要注意的一個(gè)問題是：數(shù)組都是 Zero-Based，這就意味著我們的堆數(shù)據(jù)結(jié)構(gòu)模型要發(fā)生改變

image

相應(yīng)的，幾個(gè)計(jì)算公式也要作出相應(yīng)調(diào)整：

• Parent(i) = floor((i-1)/2)，i 的父節(jié)點(diǎn)下標(biāo)
• Left(i) = 2i + 1，i 的左子節(jié)點(diǎn)下標(biāo)
• Right(i) = 2(i + 1)，i 的右子節(jié)點(diǎn)下標(biāo)

堆的建立和維護(hù)

堆可以支持多種操作，但現(xiàn)在我們關(guān)心的只有兩個(gè)問題：

1. 給定一個(gè)無序數(shù)組，如何建立為堆？
2. 刪除堆頂元素后，如何調(diào)整數(shù)組成為新堆？

先看第二個(gè)問題。假定我們已經(jīng)有一個(gè)現(xiàn)成的大根堆?，F(xiàn)在我們刪除了根元素，但并沒有移動(dòng)別的元素。想想發(fā)生了什么：根元素空了，但其它元素還保持著堆的性質(zhì)。我們可以把最后一個(gè)元素（代號(hào)A）移動(dòng)到根元素的位置。如果不是特殊情況，則堆的性質(zhì)被破壞。但這僅僅是由于A小于其某個(gè)子元素。于是，我們可以把A和這個(gè)子元素調(diào)換位置。如果A大于其所有子元素，則堆調(diào)整好了；否則，重復(fù)上述過程，A元素在樹形結(jié)構(gòu)中不斷“下沉”，直到合適的位置，數(shù)組重新恢復(fù)堆的性質(zhì)。上述過程一般稱為“篩選”，方向顯然是自上而下。

刪除后的調(diào)整，是把最后一個(gè)元素放到堆頂，自上而下比較

刪除一個(gè)元素是如此，插入一個(gè)新元素也是如此。不同的是，我們把新元素放在末尾，然后和其父節(jié)點(diǎn)做比較，即自下而上篩選。

插入是把新元素放在末尾，自下而上比較

那么，第一個(gè)問題怎么解決呢？

常規(guī)方法是從第一個(gè)非葉子結(jié)點(diǎn)向下篩選，直到根元素篩選完畢。這個(gè)方法叫“篩選法”，需要循環(huán)篩選n/2個(gè)元素。

但我們還可以借鑒“插入排序”的思路。我們可以視第一個(gè)元素為一個(gè)堆，然后不斷向其中添加新元素。這個(gè)方法叫做“插入法”，需要循環(huán)插入(n-1)個(gè)元素。

由于篩選法和插入法的方式不同，所以，相同的數(shù)據(jù)，它們建立的堆一般不同。大致了解堆之后，堆排序就是水到渠成的事情了。

動(dòng)圖演示

image

算法描述

我們需要一個(gè)升序的序列，怎么辦呢？我們可以建立一個(gè)最小堆，然后每次輸出根元素。但是，這個(gè)方法需要額外的空間（否則將造成大量的元素移動(dòng)，其復(fù)雜度會(huì)飆升到O(n^2) ）。如果我們需要就地排序（即不允許有O(n)空間復(fù)雜度），怎么辦？

有辦法。我們可以建立最大堆，然后我們倒著輸出，在最后一個(gè)位置輸出最大值，次末位置輸出次大值……由于每次輸出的最大元素會(huì)騰出第一個(gè)空間，因此，我們恰好可以放置這樣的元素而不需要額外空間。很漂亮的想法，是不是？

算法實(shí)現(xiàn)

public class ArrayHeap {
    private int[] arr;
    public ArrayHeap(int[] arr) {
        this.arr = arr;
    }
    private int getParentIndex(int child) {
        return (child - 1) / 2;
    }
    private int getLeftChildIndex(int parent) {
        return 2 * parent + 1;
    }
    private void swap(int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    /**
     * 調(diào)整堆。
     */
    private void adjustHeap(int i, int len) {
        int left, right, j;
        left = getLeftChildIndex(i);
        while (left <= len) {
            right = left + 1;
            j = left;
            if (j < len && arr[left] < arr[right]) {
                j++;
            }
            if (arr[i] < arr[j]) {
                swap(array, i, j);
                i = j;
                left = getLeftChildIndex(i);
            } else {
                break; // 停止篩選
            }
        }
    }
    /**
     * 堆排序。
     * */
    public void sort() {
        int last = arr.length - 1;
        // 初始化最大堆
        for (int i = getParentIndex(last); i >= 0; --i) {
            adjustHeap(i, last);
        }
        // 堆調(diào)整
        while (last >= 0) {
            swap(0, last--);
            adjustHeap(0, last);
        }
    }

}

穩(wěn)定性

堆排序存在大量的篩選和移動(dòng)過程，屬于不穩(wěn)定的排序算法。

適用場(chǎng)景

堆排序在建立堆和調(diào)整堆的過程中會(huì)產(chǎn)生比較大的開銷，在元素少的時(shí)候并不適用。但是，在元素比較多的情況下，還是不錯(cuò)的一個(gè)選擇。尤其是在解決諸如“前n大的數(shù)”一類問題時(shí)，幾乎是首選算法。

7. 希爾排序（插入排序的改良版）

在希爾排序出現(xiàn)之前，計(jì)算機(jī)界普遍存在“排序算法不可能突破O(n2)”的觀點(diǎn)。希爾排序是第一個(gè)突破O(n2)的排序算法，它是簡(jiǎn)單插入排序的改進(jìn)版。希爾排序的提出，主要基于以下兩點(diǎn)：

1. 插入排序算法在數(shù)組基本有序的情況下，可以近似達(dá)到O(n)復(fù)雜度，效率極高。
2. 但插入排序每次只能將數(shù)據(jù)移動(dòng)一位，在數(shù)組較大且基本無序的情況下性能會(huì)迅速惡化。

算法描述

先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，具體算法描述：

• 選擇一個(gè)增量序列t1，t2，…，tk，其中ti>tj，tk=1；
• 按增量序列個(gè)數(shù)k，對(duì)序列進(jìn)行 k 趟排序；
• 每趟排序，根據(jù)對(duì)應(yīng)的增量ti，將待排序列分割成若干長(zhǎng)度為m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為1 時(shí)，整個(gè)序列作為一個(gè)表來處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。

動(dòng)圖演示

image

算法實(shí)現(xiàn)

Donald Shell增量

public static void shellSort(int[] arr){
    int temp;
    for (int delta = arr.length/2; delta>=1; delta/=2){                              //對(duì)每個(gè)增量進(jìn)行一次排序
        for (int i=delta; i<arr.length; i++){              
            for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){ //注意每個(gè)地方增量和差值都是delta
                temp = arr[j-delta];
                arr[j-delta] = arr[j];
                arr[j] = temp;
            }
        }//loop i
    }//loop delta
}

O(n^(3/2)) by Knuth

public static void shellSort2(int[] arr){
    int delta = 1;
    while (delta < arr.length/3){//generate delta
        delta=delta*3+1;    // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
    }         
    int temp;
    for (; delta>=1; delta/=3){
        for (int i=delta; i<arr.length; i++){              
            for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){
                temp = arr[j-delta];
                arr[j-delta] = arr[j];
                arr[j] = temp;
            }
        }//loop i
    }//loop delta
}

希爾排序的增量

希爾排序的增量數(shù)列可以任取，需要的唯一條件是最后一個(gè)一定為1（因?yàn)橐ＷC按1有序）。但是，不同的數(shù)列選取會(huì)對(duì)算法的性能造成極大的影響。上面的代碼演示了兩種增量。
切記：增量序列中每?jī)蓚€(gè)元素最好不要出現(xiàn)1以外的公因子?。ê茱@然，按4有序的數(shù)列再去按2排序意義并不大）。
下面是一些常見的增量序列。

• 第一種增量是最初Donald Shell提出的增量，即折半降低直到1。據(jù)研究，使用希爾增量，其時(shí)間復(fù)雜度還是O(n2)。

第二種增量Hibbard：{1, 3, ..., 2^{k-1}。該增量序列的時(shí)間復(fù)雜度大約是O(n}1.5)。

第三種增量Sedgewick增量：(1, 5, 19, 41, 109,...)，其生成序列或者是94^i - 92^i + 1或者是4^i - 3*2^i + 1。

穩(wěn)定性

我們都知道插入排序是穩(wěn)定算法。但是，Shell排序是一個(gè)多次插入的過程。在一次插入中我們能確保不移動(dòng)相同元素的順序，但在多次的插入中，相同元素完全有可能在不同的插入輪次被移動(dòng)，最后穩(wěn)定性被破壞，因此，Shell排序不是一個(gè)穩(wěn)定的算法。

適用場(chǎng)景

Shell排序雖然快，但是畢竟是插入排序，其數(shù)量級(jí)并沒有后起之秀--快速排序O(n㏒n)快。在大量數(shù)據(jù)面前，Shell排序不是一個(gè)好的算法。但是，中小型規(guī)模的數(shù)據(jù)完全可以使用它。

計(jì)數(shù)排序

計(jì)數(shù)排序不是基于比較的排序算法，其核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開辟的數(shù)組空間中。 作為一種線性時(shí)間復(fù)雜度的排序，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。

算法描述

1. 找出待排序的數(shù)組中最大和最小的元素；
2. 統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)；
3. 對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開始，每一項(xiàng)和前一項(xiàng)相加）；
4. 反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1。

動(dòng)圖演示

image

算法實(shí)現(xiàn)

public static void countSort(int[] a, int max, int min) {
     int[] b = new int[a.length];//存儲(chǔ)數(shù)組
     int[] count = new int[max - min + 1];//計(jì)數(shù)數(shù)組

     for (int num = min; num <= max; num++) {
        //初始化各元素值為0，數(shù)組下標(biāo)從0開始因此減min
        count[num - min] = 0;
     }

     for (int i = 0; i < a.length; i++) {
        int num = a[i];
        count[num - min]++;//每出現(xiàn)一個(gè)值，計(jì)數(shù)數(shù)組對(duì)應(yīng)元素的值+1
     }

     for (int num = min + 1; num <= max; num++) {
        //加總數(shù)組元素的值為計(jì)數(shù)數(shù)組對(duì)應(yīng)元素及左邊所有元素的值的總和
        count[num - min] += sum[num - min - 1]
     }

     for (int i = 0; i < a.length; i++) {
          int num = a[i];//源數(shù)組第i位的值
          int index = count[num - min] - 1;//加總數(shù)組中對(duì)應(yīng)元素的下標(biāo)
          b[index] = num;//將該值存入存儲(chǔ)數(shù)組對(duì)應(yīng)下標(biāo)中
          count[num - min]--;//加總數(shù)組中，該值的總和減少1。
     }

     //將存儲(chǔ)數(shù)組的值一一替換給源數(shù)組
     for(int i=0;i<a.length;i++){
         a[i] = b[i];
     }
}

穩(wěn)定性

最后給 b 數(shù)組賦值是倒著遍歷的，而且放進(jìn)去一個(gè)就將C數(shù)組對(duì)應(yīng)的值（表示前面有多少元素小于或等于A[i]）減去一。如果有相同的數(shù)x1,x2，那么相對(duì)位置后面那個(gè)元素x2放在（比如下標(biāo)為4的位置），相對(duì)位置前面那個(gè)元素x1下次進(jìn)循環(huán)就會(huì)被放在x2前面的位置3。從而保證了穩(wěn)定性。

適用場(chǎng)景

排序目標(biāo)要能夠映射到整數(shù)域，其最大值最小值應(yīng)當(dāng)容易辨別。例如高中生考試的總分?jǐn)?shù)，顯然用0-750就OK啦；又比如一群人的年齡，用個(gè)0-150應(yīng)該就可以了，再不濟(jì)就用0-200嘍。另外，計(jì)數(shù)排序需要占用大量空間，它比較適用于數(shù)據(jù)比較集中的情況。

桶排序

桶排序又叫箱排序，是計(jì)數(shù)排序的升級(jí)版，它的工作原理是將數(shù)組分到有限數(shù)量的桶子里，然后對(duì)每個(gè)桶子再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排序），最后將各個(gè)桶中的數(shù)據(jù)有序的合并起來。

計(jì)數(shù)排序是桶排序的一種特殊情況，可以把計(jì)數(shù)排序當(dāng)成每個(gè)桶里只有一個(gè)元素的情況。網(wǎng)絡(luò)中很多博文寫的桶排序?qū)嶋H上都是計(jì)數(shù)排序，并非標(biāo)準(zhǔn)的桶排序，要注意辨別。

算法描述

1. 找出待排序數(shù)組中的最大值max、最小值min
2. 我們使用 動(dòng)態(tài)數(shù)組ArrayList 作為桶，桶里放的元素也用 ArrayList 存儲(chǔ)。桶的數(shù)量為(max-min)/arr.length+1
3. 遍歷數(shù)組 arr，計(jì)算每個(gè)元素 arr[i] 放的桶
4. 每個(gè)桶各自排序
5. 遍歷桶數(shù)組，把排序好的元素放進(jìn)輸出數(shù)組

圖片演示

image

算法實(shí)現(xiàn)

public static void bucketSort(int[] arr){
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < arr.length; i++){
        max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }
    //桶數(shù)
    int bucketNum = (max - min) / arr.length + 1;
    ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
    for(int i = 0; i < bucketNum; i++){
        bucketArr.add(new ArrayList<Integer>());
    }
    //將每個(gè)元素放入桶
    for(int i = 0; i < arr.length; i++){
        int num = (arr[i] - min) / (arr.length);
        bucketArr.get(num).add(arr[i]);
    }
    //對(duì)每個(gè)桶進(jìn)行排序
    for(int i = 0; i < bucketArr.size(); i++){
        Collections.sort(bucketArr.get(i));
    }
    System.out.println(bucketArr.toString());
}

穩(wěn)定性

可以看出，在分桶和從桶依次輸出的過程是穩(wěn)定的。但是，由于我們?cè)趯?duì)每個(gè)桶進(jìn)行排序時(shí)使用了其他算法，所以，桶排序的穩(wěn)定性依賴于這一步。如果我們使用了快排，顯然，算法是不穩(wěn)定的。

適用場(chǎng)景

桶排序可用于最大最小值相差較大的數(shù)據(jù)情況，但桶排序要求數(shù)據(jù)的分布必須均勻，否則可能導(dǎo)致數(shù)據(jù)都集中到一個(gè)桶中。比如[104,150,123,132,20000], 這種數(shù)據(jù)會(huì)導(dǎo)致前4個(gè)數(shù)都集中到同一個(gè)桶中。導(dǎo)致桶排序失效。

基數(shù)排序

基數(shù)排序(Radix Sort)是桶排序的擴(kuò)展，它的基本思想是：將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。
排序過程：將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長(zhǎng)度，數(shù)位較短的數(shù)前面補(bǔ)零。然后，從最低位開始，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個(gè)有序序列。

算法描述

1. 取得數(shù)組中的最大數(shù)，并取得位數(shù)；
2. arr為原始數(shù)組，從最低位開始取每個(gè)位組成radix數(shù)組；
3. 對(duì)radix進(jìn)行計(jì)數(shù)排序（利用計(jì)數(shù)排序適用于小范圍數(shù)的特點(diǎn)）；

動(dòng)圖

image

算法實(shí)現(xiàn)

public abstract class Sorter {
     public abstract void sort(int[] array);
}
 
public class RadixSorter extends Sorter {
     
     private int radix;
     
     public RadixSorter() {
          radix = 10;
     }
     
     @Override
     public void sort(int[] array) {
          // 數(shù)組的第一維表示可能的余數(shù)0-radix，第二維表示array中的等于該余數(shù)的元素
          // 如：十進(jìn)制123的個(gè)位為3，則bucket[3][] = {123}
          int[][] bucket = new int[radix][array.length];
          int distance = getDistance(array); // 表示最大的數(shù)有多少位
          int temp = 1;
          int round = 1; // 控制鍵值排序依據(jù)在哪一位
          while (round <= distance) {
               // 用來計(jì)數(shù)：數(shù)組counter[i]用來表示該位是i的數(shù)的個(gè)數(shù)
               int[] counter = new int[radix];
               // 將array中元素分布填充到bucket中，并進(jìn)行計(jì)數(shù)
               for (int i = 0; i < array.length; i++) {
                    int which = (array[i] / temp) % radix;
                    bucket[which][counter[which]] = array[i];
                    counter[which]++;
               }
               int index = 0;
               // 根據(jù)bucket中收集到的array中的元素，根據(jù)統(tǒng)計(jì)計(jì)數(shù)，在array中重新排列
               for (int i = 0; i < radix; i++) {
                    if (counter[i] != 0)
                         for (int j = 0; j < counter[i]; j++) {
                              array[index] = bucket[i][j];
                              index++;
                         }
                    counter[i] = 0;
               }
               temp *= radix;
               round++;
          }
     }
     
     private int getDistance(int[] array) {
          int max = computeMax(array);
          int digits = 0;
          int temp = max / radix;
          while(temp != 0) {
               digits++;
               temp = temp / radix;
          }
          return digits + 1;
     }
     
     private int computeMax(int[] array) {
          int max = array[0];
          for(int i=1; i<array.length; i++) {
               if(array[i]>max) {
                    max = array[i];
               }
          }
          return max;
     }
}

穩(wěn)定性

通過上面的排序過程，我們可以看到，每一輪映射和收集操作，都保持從左到右的順序進(jìn)行，如果出現(xiàn)相同的元素，則保持他們?cè)谠紨?shù)組中的順序?？梢?，基數(shù)排序是一種穩(wěn)定的排序。

適用場(chǎng)景

基數(shù)排序要求較高，元素必須是整數(shù)，整數(shù)時(shí)長(zhǎng)度10W以上，最大值100W以下效率較好，但是基數(shù)排序比其他排序好在可以適用字符串，或者其他需要根據(jù)多個(gè)條件進(jìn)行排序的場(chǎng)景，例如日期，先排序日，再排序月，最后排序年 ，其它排序算法可是做不了的。

總結(jié)

image

參考

1. LeetCode領(lǐng)扣:面試 | 常用的排序算法總結(jié)

2. 飛翔的貓咪: 用Java寫算法

3. bubkoo: 常見排序算法