前言

排序算法在計算機科學(xué)入門課程中很普遍洲押，在學(xué)習(xí)排序算法的時候武花，涉及到大量的各種核心算法概念，例如大O表示法杈帐，分治法体箕，堆和二叉樹之類的數(shù)據(jù)結(jié)構(gòu)，隨機算法，最佳累铅、最差和平均情況分析驶沼，時空權(quán)衡以及上限和下限，本文就介紹了十二種排序算法供大家學(xué)習(xí)争群。

簡介

排序算法是用來根據(jù)元素對應(yīng)的比較運算符重新排列給定的數(shù)組的算法回怜，輸出的數(shù)組是一個根據(jù)比較符從小到大或者從大到小依次排列的數(shù)組。比較運算符是用于確定相應(yīng)數(shù)據(jù)結(jié)構(gòu)中元素的新順序换薄，比如在整數(shù)數(shù)組里面玉雾，對應(yīng)的比較符號就是大于或者小于號，用戶也可以自己定義對應(yīng)的比較運算符轻要。

比如如果輸入是[4,2,3,1]复旬，按照從小到大輸出，結(jié)果應(yīng)該是[1,2,3,4]

特性

穩(wěn)定性

如果在數(shù)組中有兩個元素是相等的冲泥，在經(jīng)過某個排序算法之后驹碍，原來在前面的的那個元素仍然在另一個元素的前面，那么我們就說這個排序算法是穩(wěn)定的凡恍。

stable.jpg

如果在排序之后志秃，原來的兩個相等元素中在前面的一個元素被移到了后面，那么這個算法就是不穩(wěn)定的嚼酝。

unstable.jpg

比如排序之前數(shù)組為[3(a),2,3(b)]（其中a和b分別代表兩個不同的3）浮还，經(jīng)過某個排序算法之后是[2,3(a),3(b)]，那么這個算法就是穩(wěn)定的闽巩；如果變成了[2,3(b),3(a)]钧舌，那么這個算法是不穩(wěn)定的。

再比如在按照身高排隊去食堂打飯的過程中涎跨，小明和小剛的身高都是170洼冻，原來小明在小剛前面，但是經(jīng)過排序之后小明發(fā)現(xiàn)小剛到了他前面了隅很，這樣小明肯定對這個不穩(wěn)定的排序有意見撞牢。

時間復(fù)雜度

時間復(fù)雜度反映了算法的排序效率，通常用大O表示法來表示外构，通常暗示這個算法需要的最多操作次數(shù)的量級普泡，比如表示最多需要進行量級操作。

空間復(fù)雜度

空間復(fù)雜度反映了算法需要消耗的空間审编，比如表示只需要常數(shù)量級的空間撼班，不會隨著數(shù)組大小的變化而變化。

如果一個排序算法不需要額外的存儲空間垒酬，可以直接在原來的數(shù)組完成排序操作砰嘁，這個算法可以被稱之為原地算法件炉，空間復(fù)雜度是

比較排序、非比較排序

如果一個算法需要在排序的過程中使用比較操作來判斷兩個元素的大小關(guān)系矮湘，那么這個排序算法就是比較排序斟冕，大部分排序算法都是比較排序，比如冒泡排序缅阳、插入排序磕蛇、堆排序等等，這種排序算法的平均時間復(fù)雜度最快也只能是十办。

非比較排序比較典型的有計數(shù)排序秀撇、桶排序和基數(shù)排序，這類排序能夠脫離比較排序時間復(fù)雜度的束縛向族，達到級別的效率呵燕。

算法

首先定義基本的交換數(shù)組元素的基本方法，節(jié)省后面的代碼量件相。

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

冒泡排序

冒泡排序是從左到右依次比較相鄰的兩個元素再扭，如果前一個元素比較大，就把前一個元素和后一個交換位置夜矗，遍歷數(shù)組之后保證最后一個元素相對于前面的永遠是最大的刁笙。然后讓最后一個保持不變圃阳，重新遍歷前n-1個元素权谁，保證第n-1個元素在前n-1個元素里面是最大的鲸鹦。依此規(guī)律直到第2個元素是前2個元素里面最大的，排序就結(jié)束了逛揩。

因為這個排序的過程很像冒泡泡，找到最大的元素不停的移動到最后端麸俘，所以這個排序算法就叫冒泡排序辩稽。

Bubble sort

圖片來自這里

用Java代碼實現(xiàn)

private void bubbleSort(int[] nums) {
    for (int i = nums.length - 1; i >= 1; i--) { // 冒泡得到n-1個最大值
        for (int j = 1; j <= i; j++) {
            if (nums[j-1]>nums[j])
                swap(nums, j, j-1);           // 交換得到較大值
        }
    }
}

冒泡排序的最大特點就是代碼簡單，短短的五行代碼就能完成整個排序的操作从媚。

時間復(fù)雜度比較穩(wěn)定不管怎樣都需要次比較逞泄，所以是的時間復(fù)雜度。

空間復(fù)雜度是拜效，所有操作在原來的數(shù)組完成就可以了喷众，不需要額外的空間。

算法是穩(wěn)定的紧憾，在冒泡的過程中如果兩個元素相等到千，那么他們的位置是不會交換的。

選擇排序

選擇排序的思路比較簡單赴穗，先找到前n個元素中最大的值憔四，然后和最后一個元素交換膀息，這樣保證最后一個元素一定是最大的，然后找到前n-1個元素中的最大值了赵，和第n-1個元素進行交換潜支，然后找到前n-2個元素中最大值冗酿，和第n-2個元素交換胯究，依次類推到第2個元素净刮，這樣就得到了最后的排序數(shù)組。

其實整個過程和冒泡排序差不多蘸际，都是要找到最大的元素放到最后，不同點是冒泡排序是不停的交換元素，而選擇排序只需要在每一輪交換一次闯两。

selection sort

原圖來自這里

代碼實現(xiàn)：

private void selectionSort(int[] nums) {
    for (int i = nums.length - 1; i > 0; i--) {
        int maxIndex = 0;         // 最大元素的位置
        for (int j = 0; j <= i; j++) {
            if (nums[maxIndex]<nums[j]) {
                maxIndex = j;
            }
        }
        swap(nums, maxIndex, i);   // 把這個最大的元素移到最后
    }
}

時間復(fù)雜度和冒泡排序一樣比較穩(wěn)定似踱，都需要次比較轧简，所以時間復(fù)雜度是

空間復(fù)雜度是皮璧，不需要額外空間讯檐，是原地算法蕉拢。

選擇排序最簡單的版本是不穩(wěn)定的站宗，比如數(shù)組[1,3,2,2]库快，表示為[1,3,2(a),2(b)]闽铐，在經(jīng)過一輪遍歷之后變成了[1,2(b),2(a),3]隙咸，兩個2之間的順序因為第一個2和3的調(diào)換而顛倒了秕岛，所以不是穩(wěn)定排序遏考。

不過可以改進一下選擇排序變成穩(wěn)定的。原來不穩(wěn)定是因為交換位置導(dǎo)致的珠十，現(xiàn)在如果改成插入操作（不是使用數(shù)組而是鏈表桐智，把最大的元素插入到最后）的話捆憎，就能變成穩(wěn)定排序。比如[1,3,2(a),2(b)]，在第一輪中變成了[1,2(a),2(b),3]蛀柴，這樣就能夠保持相對位置，變成穩(wěn)定排序矫夯。

插入排序

插入排序的核心思想是遍歷整個數(shù)組名扛，保持當(dāng)前元素左側(cè)始終是排序后的數(shù)組，然后將當(dāng)前元素插入到前面排序完成的數(shù)組的對應(yīng)的位置茧痒，使其保持排序狀態(tài)。有點動態(tài)規(guī)劃的感覺融蹂，類似于先把前i-1個元素排序完成旺订，再插入第i個元素弄企，構(gòu)成i個元素的有序數(shù)組。

insertion sort

圖片來自這里

簡單代碼實現(xiàn)：

private void insertionSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {   // 從第二個元素開始遍歷
        int j = i;
        while (j>0&&nums[j]<nums[j-1]) {     // 將當(dāng)前元素移動到合適的位置
            swap(nums, j, j-1);
            j--;
        }
    }
}

時間復(fù)雜度上区拳，插入排序在最好的情況拘领，也就是數(shù)組已經(jīng)排好序的時候，復(fù)雜度是樱调，在其他情況下都是约素。

空間復(fù)雜度是，不需要額外的空間笆凌，是原地算法圣猎。

插入排序是穩(wěn)定排序，每次交換都是相鄰元素的交換乞而，不會有選擇排序的那種跳躍式交換元素送悔。

希爾排序

希爾排序可以看作是一個冒泡排序或者插入排序的變形。希爾排序在每次的排序的時候都把數(shù)組拆分成若干個序列爪模，一個序列的相鄰的元素索引相隔的固定的距離gap欠啤，每一輪對這些序列進行冒泡或者插入排序，然后再縮小gap得到新的序列一一排序屋灌，直到gap為0

比如對于數(shù)組[5,2,4,3,1,2]洁段，第一輪gap=3拆分成[5,3]、[2,1]和[4,2]三個數(shù)組進行插入排序得到[3,1,2,5,2,4]共郭；第二輪gap=1祠丝，拆分成[3,2,2]和[1,5,4]進行插入排序得到[2,1,2,4,3,5]；最后gap=0落塑，全局插入排序得到[1,2,2,3,4,5]

shell sort

圖片來自這里

簡單代碼實現(xiàn)：

private void shellSor2(int[] nums) {
    int gap = nums.length >> 1;
    while (gap > 0) {
        for (int i = 0; i < gap; i++) {                        // 對每個子序列進行排序
            for (int j = i+gap; j < nums.length; j+=gap) {     // 插入排序的部分
                int temp = j;
                while (temp > i && nums[temp] < nums[temp-gap]) {
                    swap(nums, temp, temp-gap);
                    temp -= gap;
                }
            }
        }
        gap >>= 1;
    }
}

Donald Shell于1959年發(fā)布了這種排序算法纽疟，運行時間在很大程度上取決于它使用的間隔，在實際使用中憾赁，其時間復(fù)雜度仍然是一個懸而未決的問題污朽，基本在和之間。

空間復(fù)雜度是龙考，是原地算法蟆肆。

這個算法是不穩(wěn)定的，里面有很多不相鄰元素的交換操作晦款。

歸并排序

歸并排序是典型的使用分治思想（divide-and-conquer）解決問題的案例炎功。在排序的過程中，把原來的數(shù)組變成左右兩個數(shù)組缓溅，然后分別進行排序蛇损，當(dāng)左右的子數(shù)組排序完畢之后，再合并這兩個子數(shù)組形成一個新的排序數(shù)組。整個過程遞歸進行淤齐，當(dāng)只剩下一個元素或者沒有元素的時候就直接返回股囊。

merge sort

圖片來自這里

代碼如下：

private void mergeSort(int[] nums, int left, int right) {  // 需要左右邊界確定排序范圍
    if (left >= right) return;
    int mid = (left+right) / 2;

    mergeSort(nums, left, mid);                           // 先對左右子數(shù)組進行排序
    mergeSort(nums, mid+1, right);

    int[] temp = new int[right-left+1];                   // 臨時數(shù)組存放合并結(jié)果
    int i=left,j=mid+1;
    int cur = 0;
    while (i<=mid&&j<=right) {                            // 開始合并數(shù)組
        if (nums[i]<=nums[j]) temp[cur] = nums[i++];
        else temp[cur] = nums[j++];
        cur++;
    }
    while (i<=mid) temp[cur++] = nums[i++];
    while (j<=right) temp[cur++] = nums[j++];

    for (int k = 0; k < temp.length; k++) {             // 合并數(shù)組完成，拷貝到原來的數(shù)組中
        nums[left+k] = temp[k];
    }
}

時間復(fù)雜度上歸并排序能夠穩(wěn)定在的水平更啄，在每一級的合并排序數(shù)組過程中總的操作次數(shù)是稚疹，總的層級數(shù)是，相乘得到最后的結(jié)果就是

空間復(fù)雜度是祭务，因為在合并的過程中需要使用臨時數(shù)組來存放臨時排序結(jié)果内狗。

歸并排序是穩(wěn)定排序，保證原來相同的元素能夠保持相對的位置义锥。

快速排序

快速排序（有時稱為分區(qū)交換排序）是一種高效的排序算法柳沙。由英國計算機科學(xué)家Tony Hoare于1959年開發(fā)并于1961年發(fā)表，它在現(xiàn)在仍然是一種常用的排序算法缨该。如果實現(xiàn)方法恰當(dāng)偎行，它可以比主要競爭對手（歸并排序和堆排序）快兩到三倍。

其核心的思路是取第一個元素（或者最后一個元素）作為分界點贰拿，把整個數(shù)組分成左右兩側(cè)蛤袒，左邊的元素小于或者等于分界點元素，而右邊的元素大于分界點元素膨更，然后把分界點移到中間位置妙真，對左右子數(shù)組分別進行遞歸，最后就能得到一個排序完成的數(shù)組荚守。當(dāng)子數(shù)組只有一個或者沒有元素的時候就結(jié)束這個遞歸過程珍德。

其中最重要的是將整個數(shù)組根據(jù)分界點元素劃分成左右兩側(cè)的邏輯，目前有兩種算法矗漾，圖片展示的是第一種锈候。

quick sort

圖片來自這里

第一種實現(xiàn)，也是圖片中的排序邏輯的實現(xiàn)：

private void quickSort(int[] nums, int left, int right) {
    if (left >= right) return;
    int lo = left+1;               // 小于分界點元素的最右側(cè)的指針
    int hi = right;                // 大于分界點元素的最左側(cè)的指針
    while (lo<=hi) {
        if (nums[lo]>nums[left]) { // 交換元素確保左側(cè)指針指向元素小于分界點元素
            swap(nums, lo, hi);
            hi--;
        } else {
            lo++;
        }
    }
    lo--;                          // 回到小于分界點元素數(shù)組的最右側(cè)
    swap(nums, left, lo);          // 將分界點元素移到左側(cè)數(shù)組最右側(cè)
    quickSort2(nums, left, lo-1);
    quickSort2(nums, lo+1, right);
}

第二種敞贡，不用hi來標(biāo)記大于分界點元素的最右側(cè)泵琳，而是只用一個lo來標(biāo)記最左側(cè)。在遍歷整個數(shù)組的過程中誊役，如果發(fā)現(xiàn)了一個小于等于分界點元素的元素获列，就和lo+1位置的元素交換，然后lo自增蛔垢，這樣可以保證lo的左側(cè)一定都是小于等于分界點元素的击孩，遍歷到最后lo的位置就是新的分界點位置，和最開始的分界點元素位置互換鹏漆。

private void quickSort(int[] nums, int left, int right) {
    if (left>=right) return;
    int cur = left + 1;                   // 從左側(cè)第二個元素開始
    int lo = left;                        // 分界點為第一個元素
    while (cur <= right) {
        if (nums[cur] <= nums[left]) {    // 交換位置保證lo的左側(cè)都是小于num[left]
            swap(nums, lo+1, cur);
            lo ++;
        }
        cur++;
    }
    swap(nums, left, lo);                 // 把分界點元素移動到新的分界位置
    quickSort(nums, left, lo-1);
    quickSort(nums, lo+1, right);
}

時間復(fù)雜度在最佳情況是巩梢，但是如果分界點元素選擇不當(dāng)可能會惡化到创泄，但是這種情況比較少見（比如數(shù)組完全逆序），如果隨機選擇分界點的話且改，時間復(fù)雜度能夠穩(wěn)定在验烧。另外如果元素中相同元素數(shù)量比較多的話，也會降低排序性能又跛。

空間復(fù)雜度在水平，屬于堆棧調(diào)用若治，在最壞的情況下空間復(fù)雜度還是慨蓝，平均情況下復(fù)雜度是

快速排序是不穩(wěn)定的，因為包含跳躍式交換元素位置端幼。

堆排序

堆排序是一個效率要高得多的選擇排序礼烈，首先把整個數(shù)組變成一個最大堆，然后每次從堆頂取出最大的元素婆跑，這樣依次取出的最大元素就形成了一個排序的數(shù)組此熬。堆排序的核心分成兩個部分，第一個是新建一個堆滑进，第二個是彈出堆頂元素后重建堆犀忱。

新建堆不需要額外的空間，而是使用原來的數(shù)組扶关，一個數(shù)組在另一個維度上可以當(dāng)作一個完全二叉樹（除了最后一層之外其他的每一層都被完全填充阴汇，并且所有的節(jié)點都向左對齊），對于下標(biāo)為i的元素节槐，他的子節(jié)點是2*i+1和2*i+2（前提是沒有超出邊界）搀庶。在新建堆的時候從左向右開始遍歷，當(dāng)遍歷到一個元素的時候铜异，重新排列從這個元素節(jié)點到根節(jié)點的所有元素哥倔，保證滿足最大堆的要求（父節(jié)點比子節(jié)點要大）。遍歷完整個數(shù)組的時候揍庄，這個最大堆就完成了咆蒿。

在彈出根節(jié)點之后（把根節(jié)點的元素和樹的最底層最右側(cè)的元素互換），堆被破壞币绩，需要重建蜡秽。從根節(jié)點開始和兩個子節(jié)點比較，如果父節(jié)點比最大的子節(jié)點小缆镣，那么就互換父節(jié)點和最大的子節(jié)點芽突，然后把互換后在子節(jié)點位置的父節(jié)點當(dāng)作新的父節(jié)點，和它的子節(jié)點比較董瞻，如此往復(fù)直到最后一層寞蚌，這樣最大堆就重建完畢了田巴。

heap sort

圖片來自這里

簡單java代碼：

private void heapSort(int[] nums) {
    heapify(nums);                                 // 新建一個最大堆
    for (int i = nums.length - 1; i >= 1; i--) {
        swap(nums, 0, i);                       // 彈出最大堆的堆頂放在最后
        rebuildHeap(nums, 0,i-1);          // 重建最大堆
    }
}

private void heapify(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        int par = (i-1)>>1;                       // 找到父節(jié)點
        int child = i;                            // 定義子節(jié)點
        while (child>0&&nums[par]<nums[child]) {  // 從子節(jié)點到根節(jié)點構(gòu)建最大堆
            swap(nums, par, child);
            child = par;
            par = (par-1) >> 1;
        }
    }
}

private void rebuildHeap(int[] nums, int par, int last) {
    int left = 2*par+1;                           // 左子節(jié)點
    int right = 2*par+2;                          // 右子節(jié)點
    int maxIndex = left;

    if (right<=last && nums[right]>nums[left]) {  // 找到最大子節(jié)點
        maxIndex = right;
    }

    if (left<=last && nums[par] < nums[maxIndex]) {// 和最大子節(jié)點比較
        swap(nums, par, maxIndex);                 // 互換到最大子節(jié)點
        rebuildHeap(nums, maxIndex, last);         // 重建最大子節(jié)點代表的子樹
    }
}

時間復(fù)雜度穩(wěn)定在，因為在構(gòu)建堆的時候時間遍歷數(shù)組對于每個元素需要進行次比較挟秤，時間復(fù)雜度是壹哺。在彈出每個元素重建堆需要的復(fù)雜度，時間復(fù)雜度也是艘刚，所以整體的時間復(fù)雜度是

空間復(fù)雜度是管宵，在原數(shù)組進行所有操作就可以了。

堆排序是不穩(wěn)定攀甚，堆得構(gòu)建和重建的過程都會打亂元素的相對位置箩朴。

堆排序的代碼量相對于其他的排序算法來說是比較多的，理解上也比較難秋度，涉及到最大堆和二叉樹等相關(guān)概念炸庞。雖然在實際使用中相對于快速排序不是那么好用，但是最壞情況下的的時間復(fù)雜度也是優(yōu)于快排的荚斯〔壕樱空間使用是恒定的，是優(yōu)于歸并排序事期。

二叉搜索樹排序

二叉樹搜索排序用數(shù)組內(nèi)的所有元素構(gòu)建一個搜索二叉樹滥壕，然后用中序遍歷重新將所有的元素填充回原來的數(shù)組中。因為搜索二叉樹不能用數(shù)組來表示刑赶，所以必須使用額外的數(shù)據(jù)結(jié)構(gòu)來構(gòu)建二叉樹捏浊。

bst sort

圖片來自這里

簡單代碼如下：

private int[] bstSort(int[] nums) {
    TreeNode root = new TreeNode(nums[0]);   // 構(gòu)建根節(jié)點
    for (int i = 1; i < nums.length; i++) {  // 將所有的元素插入到二叉搜索樹中
        buildTree(root, nums[i]);
    }
    inorderTraversal(root, nums, new int[1]);// 中序遍歷獲取二叉樹中的所有節(jié)點
    return nums;
}

private void inorderTraversal(TreeNode node, int[] nums, int[] pos) {
    if (node == null) return;
    inorderTraversal(node.left, nums, pos);
    nums[pos[0]++] = node.val;
    inorderTraversal(node.right, nums, pos);
}

private void buildTree(TreeNode node, int num) {
    if (node == null) return;
    if (num >= node.val) {                   // 插入到右子樹中
        if (node.right == null) {
            node.right = new TreeNode(num);
        } else {
            buildTree(node.right, num);
        }
    } else {                                 // 插入到左子樹中
        if (node.left == null) {
            node.left = new TreeNode(num);
        } else {
            buildTree(node.left, num);
        }
    }
}

static class TreeNode {   // 樹節(jié)點的數(shù)據(jù)結(jié)構(gòu)
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

時間復(fù)雜度上面根據(jù)原數(shù)組變化比較大，最差情況是整個數(shù)組是已經(jīng)排好序的撞叨，這樣二叉樹會變成一個鏈表結(jié)構(gòu)金踪，時間復(fù)雜度退化到了，但是最優(yōu)和平均情況下時間復(fù)雜度在水平牵敷。

空間復(fù)雜度是胡岔，因為要構(gòu)建一個包含n個元素的二叉搜索樹。

這個算法是穩(wěn)定枷餐，在構(gòu)建二叉樹的過程中能夠保證元素順序的一致性靶瘸。

計數(shù)排序

計數(shù)排序是一個最基本的非比較排序，能夠?qū)r間復(fù)雜度提高到的水平毛肋，但是使用上比較有局限性怨咪，通常只能應(yīng)用在鍵的變化范圍比較小的情況下，如果鍵的變化范圍特別大润匙，建議使用基數(shù)排序诗眨。

計數(shù)排序的過程是創(chuàng)建一個長度為數(shù)組中最小和最大元素之差的數(shù)組，分別對應(yīng)數(shù)組中的每個元素孕讳，然后用這個新的數(shù)組來統(tǒng)計每個元素出現(xiàn)的頻率匠楚，然后遍歷新的數(shù)組巍膘，根據(jù)每個元素出現(xiàn)的頻率把元素放回到老的數(shù)組中，得到已經(jīng)排好序的數(shù)組芋簿。

counting sort

圖片來自這里

簡單代碼實現(xiàn)：

private void countSort(int[] nums) {
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for (int num : nums) {            // 找到最大最小值
        min = Math.min(min, num);
        max = Math.max(max, num);
    }
    int[] count = new int[max-min+1]; // 建立新數(shù)組
    for (int num : nums) {            // 統(tǒng)計每個元素出現(xiàn)頻率
        count[num-min]++;
    }
    int cur = 0;
    for (int i = 0; i < count.length; i++) {  // 根據(jù)出現(xiàn)頻率把計數(shù)數(shù)組中的元素放回到舊數(shù)組中
        while (count[i]>0) {
            nums[cur++] = i+min;
            count[i]--;
        }
    }
}

計數(shù)排序能夠?qū)r間復(fù)雜度降低到（r為數(shù)組元素變化范圍）峡懈，不過這是對于數(shù)組元素的變化范圍不是特別大。隨著范圍的變大与斤，計數(shù)排序的性能就會逐漸降低肪康。

空間復(fù)雜度為，隨著數(shù)組元素變化范圍的增大幽告，空間復(fù)雜度也會變大梅鹦。

計數(shù)排序是穩(wěn)定的，原來排在前面的相同在計數(shù)的時候冗锁，仍然是排在每個計數(shù)位置的前面，在最后復(fù)原的時候也是從每個計數(shù)位的前面開始復(fù)原嗤栓，所以最后相對位置還是相同的冻河。

桶排序

桶排序是將所有的元素分布到一系列的區(qū)間（也可以稱之為桶）里面，然后對每個桶里面的所有元素分別進行排序的算法茉帅。

首先新建一個桶的數(shù)組叨叙，每個桶的規(guī)則需要提前制定好，比如元素在0_{9為一個桶堪澎、10}19為一個桶擂错。然后遍歷整個待排序的數(shù)組，把元素分配到對應(yīng)的桶里面樱蛤。接下來單獨對每個桶里面的元素進行排序钮呀，排序算法可以選擇比較排序或者非比較排序，得到排序后的數(shù)組昨凡。最后把所有的桶內(nèi)的元素還原到原數(shù)組里面得到最后的排序數(shù)組爽醋。

bucket sort

圖片來自這里

private void bucketSort(int[] nums) {
    int INTERVAL = 100;               // 定義桶的大小
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for (int num : nums) {            // 找到數(shù)組元素的范圍
        min = Math.min(min, num);
        max = Math.max(max, num);
    }
    int count = (max - min + 1);      // 計算出桶的數(shù)量
    int bucketSize = (count % INTERVAL == 0) ?( count / INTERVAL) : (count / INTERVAL+1);
    List<Integer>[] buckets = new List[bucketSize];
    for (int num : nums) {            // 把所有元素放入對應(yīng)的桶里面
        int quotient = (num-min) / INTERVAL;
        if (buckets[quotient] == null) buckets[quotient] = new ArrayList<>();
        buckets[quotient].add(num);
    }
    int cur = 0;
    for (List<Integer> bucket : buckets) {
        if (bucket != null) {
            bucket.sort(null);       // 對每個桶進行排序
            for (Integer integer : bucket) {  // 還原桶里面的元素到原數(shù)組
                nums[cur++] = integer;
            }
        }
    }
}

時間復(fù)雜度上桶排序和計數(shù)排序一樣，是的水平便脊，但是隨著數(shù)據(jù)元素范圍的增大蚂四，時間消耗也在增大。

空間復(fù)雜度也是哪痰，需要額外的空間來保存所有的桶和桶里面的元素遂赠。

桶排序是穩(wěn)定的（前提是桶內(nèi)排序的邏輯是穩(wěn)定的），和計數(shù)排序的邏輯類似晌杰，遍歷過程插入桶的過程中沒有改變相同元素的相對位置跷睦，排序也沒有改變，最后的還原也沒有改變乎莉。

基數(shù)排序

基數(shù)排序和桶排序有點相似送讲，基數(shù)排序中需要把元素送入對應(yīng)的桶中奸笤，不過規(guī)則是根據(jù)所有數(shù)字的某一位上面的數(shù)字來分類。

假設(shè)當(dāng)前數(shù)組的所有元素都是正數(shù)哼鬓，桶的數(shù)量就固定在了10個监右，然后計算出最大元素的位數(shù)。首先根據(jù)每個元素的最低位進行分組异希，比如1就放入1這個桶健盒，13就放入3這個桶，111也放入1這個桶称簿，然后把所有的數(shù)字根據(jù)桶的順序取出來扣癣，依次還原到原數(shù)組里面。在第二輪從第二位開始分組憨降，比如1（看作01）放入0這個桶父虑，13放入1這個桶，111也放入1這個桶授药，再把所有的元素從桶里面依次取出放入原數(shù)組士嚎。經(jīng)過最大元素位數(shù)次的這樣的操作之后，還原得到的數(shù)組就是一個已經(jīng)排好序的數(shù)組悔叽。

radix sort

圖片來自這里

考慮到數(shù)組里面還有負數(shù)的情況莱衩，可以把桶的大小擴大到19個，分別代表對應(yīng)位在-9~9之間的數(shù)字娇澎，代碼如下：

private void radixSort(int[] nums) {
    int max = -1;
    int min = 1;
    for (int num : nums) {         // 計算最大最小值
        max = Math.max(max, num);
        min = Math.min(min, num);
    }
    max = Math.max(max, -min);     // 求得絕對值最大的值
    int digits = 0;
    while (max > 0) {              // 計算絕對值最大的值的位數(shù)
        max /= 10;
        digits++;
    }
    List<Integer>[] buckets = new List[19]; // 建一個包含所有位數(shù)的數(shù)組
    for (int i = 0; i < buckets.length; i++) {
        buckets[i] = new ArrayList<>();
    }
    int pos;
    int cur;
    for (int i = 0, mod = 1; i < digits; i++, mod*=10) { // 對十進制每一位進行基數(shù)排序
        for (int num : nums) {                 // 掃描數(shù)組將值放入對應(yīng)的桶
            pos = (num / mod) % 10;
            buckets[pos+9].add(num);
        }
        cur = 0;
        for (List<Integer> bucket : buckets) { // 將桶內(nèi)元素放回到數(shù)組里面
            if (bucket!=null) {
                for (Integer integer : bucket) {
                    nums[cur++] = integer;
                }
                bucket.clear();                // 將桶清空
            }
        }
    }
}

時間復(fù)雜度基本在水平笨蚁，其中為key的總數(shù)量，為絕對值最大的數(shù)字的十進制位數(shù)趟庄。

空間復(fù)雜度是括细。

基數(shù)排序是一個穩(wěn)定排序算法，在排序添加元素的過程中沒有改變相同元素的相互位置岔激。

TimSort

Timsort是由Tim Peters在2002年實現(xiàn)的勒极，自Python 2.3以來，它一直是Python的標(biāo)準(zhǔn)排序算法虑鼎。Java在JDK中使用Timsort對非基本類型進行排序辱匿。Android平臺和GNU Octave還將其用作默認排序算法。

Timsort是一種穩(wěn)定的混合排序算法炫彩，同時應(yīng)用了二分插入排序和歸并排序的思想匾七，在時間上擊敗了其他所有排序算法。它在最壞情況下的時間復(fù)雜度為優(yōu)于快速排序江兢；最佳情況的時間復(fù)雜度為昨忆，優(yōu)于歸并排序和堆排序。

由于使用了歸并排序杉允，使用額外的空間保存數(shù)據(jù)邑贴，TimSort空間復(fù)雜度是

由于篇幅原因席里，TimSort的具體實現(xiàn)過程暫且就不講了六剥，會有一篇專門的文章來介紹TimSort栅屏。

總結(jié)

排序算法	最好情況	平均情況	最差情況	空間復(fù)雜度	穩(wěn)定性
冒泡排序					?
選擇排序
插入排序					?
希爾排序
二叉樹排序					?
歸并排序					?
快速排序
堆排序
計數(shù)排序	-				?
桶排序	-				?
基數(shù)排序	-				?
TimSort					?

備注：為排序數(shù)字的范圍苹粟，是數(shù)字總位數(shù)镀梭，是數(shù)字總個數(shù)

上面的表格總結(jié)了講到的排序算法的時間和空間復(fù)雜度以及穩(wěn)定性等，在實際應(yīng)用中會有各種排序算法變形的問題鹏浅，都可以通過優(yōu)化排序算法來達到優(yōu)化算法的目的柒凉。

如果對時間復(fù)雜度要求比較高并且鍵的分布范圍比較廣帘皿，可以使用歸并排序稠腊、快速排序和堆排序躁染。

如果不能使用額外的空間，那么快速排序和堆排序都是不錯的選擇架忌。

如果規(guī)定了排序的鍵的范圍吞彤，可以優(yōu)先考慮使用桶排序。

如果不想寫太多的代碼同時時間復(fù)雜度沒有太高的要求叹放，可以考慮冒泡排序备畦、選擇排序和插入排序。

如果排序的過程中沒有復(fù)雜的額外操作许昨，直接使用編程語言內(nèi)置的排序算法就行了。

參考

超詳細十大經(jīng)典排序算法總結(jié)（java代碼）
十大經(jīng)典排序算法
十大經(jīng)典排序算法（動圖演示）
Sorting algorithm
Timsort
Data Structure - Sorting Techniques
This is the fastest sorting algorithm ever
TimSort
Timsort: The Fastest sorting algorithm for real-world problems

更多內(nèi)容請看我的個人博客