七大經典、常用排序算法的原理、Java 實作以及算法分析

0. 前言

大家好，我是多選參數的程式鍋，一個正在 neng 作業系統、學資料結構和算法以及 Java 的硬核菜雞。資料結構和算法是我準備新開的坑，主要是因為自己在這塊确實很弱，需要大補（殘廢了一般）。這個坑以排序為開端，介紹了 7 種最經典、最常用的排序算法，分别是：冒泡排序、插入排序、選擇排序、歸并排序、快速排序、桶排序、計數排序、基數排序。對應的時間複雜度如下所示：

排序算法	時間複雜度	是否基于比較
冒泡、插入、選擇	O(n^2)	√
快排、歸并	O(nlogn)	√
桶、計數、基數	O(n)	×

整篇文章的主要知識提綱如圖所示：

接下去所用到的圖都來自于極客時間王争的專欄《資料結構與算法之美》，因為圖太好看了。

1. 排序算法分析

學習排序算法除了學習它的算法原理、代碼實作之外，最重要的是學會如何評價、分析一個排序算法。分析一個排序算法通常從以下幾點出發。

1.1. 執行效率

而對執行效率的分析，一般從這幾個方面來衡量：

• 最好情況、最壞情況、平均情況

  除了需要給出這三種情況下的時間複雜度還要給出對應的要排序的原始資料是怎麼樣的。

• 時間複雜度的系數、常數、低階

  大 O 時間複雜度反應的是算法時間随 n 的一個增長趨勢，比如 O(n^2) 表示算法時間随 n 的增加，呈現的是平方的增長趨勢。這種情況下往往會忽略掉系數、常數、低階等。但是實際開發過程中，排序的資料往往是 10 個、100 個、1000 個這樣規模很小的資料，是以在比較同階複雜度的排序算法時，這些系數、常數、低階不能省略。

• 比較次數和交換（或移動）次數

  在基于比較的算法中，會涉及到元素比較和元素交換等操作。是以分析的時候，還需要對比較次數和交換次數進行分析。

1.2. 記憶體消耗

記憶體消耗其實就是空間複雜度。針對排序算法來說，如果該排序算法的空間複雜度為 O(1)，那麼這個排序算法又稱為原地排序。

1.3. 穩定性

是什麼

穩定性是指待排序的序列中存在值相等的元素。在排序之後，相等元素的前後順序跟排序之前的是一樣的。

為什麼

我們将排序的原理和實作排序時用的大部分都是整數，但是實際開發過程中要排序的往往是一組對象，而我們隻是按照對象中的某個 key 來進行排序。

比如一個對象有兩個屬性，下單時間和訂單金額。在存入到資料庫的時候，這些對象已經按照時間先後的順序存入了。但是我們現在要以訂單金額為主要 key，在訂單金額相同的時候，以下單時間為 key。那麼在采用穩定的算法之後，隻需要按照訂單金額進行一次排序即可。比如有這麼三個資料，第一個資料是下單時間、第二資料是訂單金額：（20200515、20）、（20200516、10）、（20200517、30）、（20200518、20）。在采用穩定的算法之後，排序的情況如下：（20200516、10）、(20200515、20)、（20200518、20）、（20200517、30）可以發現在訂單金額相同的情況下是按訂單時間進行排序的。

2. 經典的常用排序算法

2.1. 冒泡排序

冒泡排序就是依次對兩個相鄰的元素進行比較，然後在不滿足大小條件的情況下進行元素交換。一趟冒泡排序下來至少會讓一個元素排好序（元素排序好的區域相當于有序區，是以冒泡排序中相當于待排序數組分成了兩個已排序區間和未排序區間）。是以為了将 n 個元素排好序，需要 n-1 趟冒泡排序（第 n 趟的時候就不需要）。

下面用冒泡排序對這麼一組資料4、5、6、3、2、1，從小到大進行排序。第一次排序情況如下：

img

可以看出，經過一次冒泡操作之後，6 這個元素已經存儲在正确的位置上了，要想完成有所有資料的排序，我們其實隻需要 5 次這樣的冒泡排序就行了。圖中給出的是帶第 6 次了的，但是第 6 次其實沒必要。

img

2.1.1. 優化

使用冒泡排序的過程中，如果有一趟冒泡過程中元素之間沒有發生交換，那麼就說明已經排序好了，可以直接退出不再繼續執行後續的冒泡操作了。

2.1.2. 實作

下面的冒泡排序實作是優化之後的：

/**
 * 冒泡排序：
 * 以升序為例，就是比較相鄰兩個數，如果逆序就交換，類似于冒泡；
 * 一次冒泡确定一個數的位置，因為要确定 n-1 個數，是以需要 n-1
 * 次冒泡；
 * 冒泡排序時，其實相當于把整個待排序序列分為未排序區和已排序區
 */
public void bubbleSort(int[] arr, int len) {
    // len-1 趟
    for (int j = 0; j < len-1; j++) {
        int sortedFlag = 0;
        // 一趟冒泡
        for (int i = 0; i < len-1-j; i++) {
            if (arr[i] > arr[i+1]) {
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
                sortedFlag = 1;
            }
        }

        // 該趟排序中沒有發生，表示已經有序
        if (0 == sortedFlag) {
            break;
        }
    }
}
           

複制

2.1.3. 算法分析

• 冒泡排序是原地排序。因為冒泡過程中隻涉及到相鄰資料的交換，相當于隻需要開辟一個記憶體空間用來完成相鄰的資料交換即可。
• 在元素大小相等的時候，不進行交換，那麼冒泡排序就是穩定的排序算法。
• 冒泡排序的時間複雜度。
  • 當元素已經是排序好了的，那麼最好情況的時間複雜度是 O(n)。因為隻需要跑一趟，然後發現已經排好序了，那麼就可以退出了。
  • 當元素正好是倒序排列的，那麼需要進行 n-1 趟排序，最壞情況複雜度為 O(n^2)。

  • 一般情況下，平均時間複雜度是 O(n^2)。使用有序度和逆序度的方法來求時間複雜度，冒泡排序過程中主要是兩個操作：比較和交換。每交換一次，有序度就增加一，是以有序度增加的次數就是交換的次數。又因為有序度需要增加的次數等于逆序度，是以交換的次數其實就等于逆序度。

    是以當要對包含 n 個資料的數組進行冒泡排序時。最壞情況下，有序度為 0 ，那麼需要進行 n*(n-1)/2 次交換；最好情況下，不需要進行交換。我們取中間值 n*(n-1)/4，來表示初始有序度不是很高也不是很低的平均情況。由于平均情況下需要進行 n*(n-1)/4 次交換，比較操作肯定比交換操作要多。但是時間複雜度的上限是 O(n^2)，是以平均情況下的時間複雜度就是 O(n^2)。

    ★這種方法雖然不嚴格，但是很實用。主要是因為機率的定量分析太複雜，不實用。（PS：我就喜歡這種的）

    ”

2.2. 插入排序

**插入排序中将數組中的元素分成兩個區間：已排序區間和未排序區間（最開始的時候已排序區間的元素隻有數組的第一個元素），插入排序就是将未排序區間的元素依次插入到已排序區間（需要保持已排序區間的有序）。最終整個數組都是已排序區間，即排序好了。**假設要對 n 個元素進行排序，那麼未排序區間的元素個數為 n-1，是以需要 n-1 次插入。插入位置的查找可以從尾到頭周遊已排序區間也可以從頭到尾周遊已排序區間。

如圖所示，假設要對 4、5、6、1、3、2進行排序。左側橙紅色表示的是已排序區間，右側黃色的表示未排序區間。整個插入排序過程如下所示

img

2.2.1. 優化

• 采用希爾排序的方式。
• **使用哨兵機制。**比如要排序的數組是[2、1、3、4]，為了使用哨兵機制，首先需要将數組的第 0 位空出來，然後數組元素全都往後移動一格，變成[0、2、1、3、4]。那麼數組 0 的位置用來存放要插入的資料，這樣一來，判斷條件就少了一個，不用再判斷 j >= 0 這個條件了，隻需要使用 arr[j] > arr[0] 的條件就可以了。因為就算周遊到下标為 0 的位置，由于 0 處這個值跟要插入的值是一樣的，是以會退出循環，不會出現越界的問題。

2.2.2. 實作

這邊查找插入位置的方式采用從尾到頭周遊已排序區間，也沒有使用哨兵。

/**
 * 插入排序：
 * 插入排序也相當于把待排序序列分成已排序區和未排序區；
 * 每趟排序都将從未排序區選擇一個元素插入到已排序合适的位置；
 * 假設第一個元素屬于已排序區，那麼還需要插入 len-1 趟；
 */
public void insertSort(int[] arr, int len) {
    // len-1 趟
    for (int i = 1; i < len; i++) {
        // 一趟排序
        int temp = arr[i];
        int j;
        for (j = i-1; j >= 0; j--) {
            if (arr[j] > temp) {
                arr[j+1] = arr[j];
            } else {
                break;
            }
        }
        arr[j+1] = temp;
    }
}
           

複制

2.2.3. 算法分析

• 插入排序是原地算法。因為隻需要開辟一個額外的存儲空間來臨時存儲元素。
• 當比較元素時發現元素相等，那麼插入到相等元素的後面，此時就是穩定排序。也就是說隻有當有序區間中的元素大于要插入的元素時才移到到後面的位置，不大于（小于等于）了的話直接插入。
• 插入排序的時間複雜度。
  • 待排序的資料是有序的情況下，不需要搬移任何資料。那麼采用從尾到頭在已排序區間中查找插入位置的方式，最好時間複雜度是 O(n)。
  • 待排序的資料是倒序的情況，需要依次移動 1、2、3、...、n-1 個資料，是以最壞時間複雜度是 O(n^2)。

  • 平均時間複雜度是 O(n^2)。是以将一個資料插入到一個有序數組中的平均時間度是 O(n)，那麼需要插入 n-1 個資料，是以平均時間複雜度是 O(n^2)

    ★最好的情況是在這個數組中的末尾插入元素的話，不需要移動數組，時間複雜度是 O(1)，假如在數組開頭插入資料的話，那麼所有的資料都需要依次往後移動一位，是以時間複雜度是 O(n)。往數組第 k 個位置插入的話，那麼 k~n 這部分的元素都需要往後移動一位。是以此時插入的平均時間複雜度是 O(n)

    ”

2.2.4. VS 冒泡排序

冒泡排序和插入排序的時間複雜度都是 O(n^2)，都是原地穩定排序。而且冒泡排序不管怎麼優化，元素交換的次數是一個固定值，是原始資料的逆序度。插入排序是同樣的，不管怎麼優化，元素移動的次數也等于原始資料的逆序度。但是，從代碼的實作上來看，冒泡排序的資料交換要比插入排序的資料移動要複雜，冒泡排序需要 3 個指派操作，而插入排序隻需要一個指派操作。是以，雖然冒泡排序和插入排序在時間複雜度上都是 O(n^2)，但是如果希望把性能做到極緻，首選插入排序。其實該點分析的主要出發點就是在同階複雜度下，需要考慮系數、常數、低階等。

2.3. 選擇排序

選擇排序也分為已排序區間和未排序區間（剛開始的已排序區間沒有資料），選擇排序每趟都會從未排序區間中找到最小的值（從小到大排序的話）放到已排序區間的末尾。

img

2.3.1. 實作

/**
 * 選擇排序：
 * 選擇排序将待排序序列分成未排序區和已排序區；
 * 第一趟排序的時候整個待排序序列是未排序區；
 * 每一趟排序其實就是從未排序區選擇一個最值，放到已排序區；
 * 跑 len-1 趟就好
 */
public void switchSort(int[] arr, int len) {
    // len-1 趟，0-i 為已排序區
    for (int i = 0; i < len-1; i++) {
        int minIndex = i;
        for (int j = i+1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}
           

複制

2.3.2. 算法分析

• 選擇排序是原地排序，因為隻需要用來存儲最小值所處位置的額外空間和交換時所需的額外空間。
• 選擇排序不是一個穩定的算法。因為選擇排序是從未排序區間中找一個最小值，并且和前面的元素交換位置，這會破壞穩定性。比如 1、5、5、2 這樣一組資料中，使用排序算法的話。當找到 2 為 5、5、2 目前未排序區間最小的元素時，2 會與第一個 5 交換位置，那麼兩個 5 的順序就變了，就破壞了穩定性。
• 時間複雜度分析。最好、最壞、平均都是 O(n^2)，因為無論待排序數組情況怎麼樣，就算是已經有序了，都是需要依次周遊完未排序區間，需要比較的次數依次是 n-1、n-2，是以時間複雜度是 O(n^2)。

2.4. 歸并排序（Merge Sort）

**歸并排序的核心思想就是我要對一個數組進行排序：首先将數組分成前後兩部分，然後對兩部分分别進行排序，排序好之後再将兩部分合在一起，那整個數組就是有序的了。對于分出的兩部分可以采用相同的方式進行排序。**這個思想就是分治的思想，就是先将大問題分解成小的子問題來解決，子問題解決之後，大問題也就解決了。而對于子問題的求解也是一樣的套路。這個套路有點類似于遞歸的方式，是以分治算法一般使用遞歸來實作。分治是一種解決問題的處理思想，而遞歸是一種實作它的程式設計方法。

2.4.1. 實作

下面使用遞歸的方式來實作歸并排序。遞歸的遞推公式是：merge_sort(p...r) = merge(merge_sort(p...q), merge_sort(q+1...r))，終止條件是 p>=r，不再遞歸下去了。整個實作過程是先調用

__mergeSort()

函數将兩部分分别排好序，之後再使用數組合并的方式将兩個排序好的部分進行合并。

/**
 * 歸并排序
 */
public void mergeSort(int[] arr, int len) {
    __mergerSort(arr, 0, len-1);
}

private void __mergerSort(int[] arr, int begin, int end) {
    if (begin == end){
        return;
    }

    __mergerSort(arr, begin, (begin+end)/2);
    __mergerSort(arr, (begin+end)/2 + 1, end);
    merge(arr, begin, end);
    return;
}

private void merge(int[] arr, int begin, int end) {
    int[] copyArr = new int[end-begin+1];
    System.arraycopy(arr, begin, copyArr, 0, end-begin+1);

    int mid = (end - begin + 1)/2;
    int i = 0;  // begin - mid 的指針
    int j =  mid;   // mid - end 的指針
    int count = begin;  // 合并之後數組的指針

    while (i <= mid-1 && j <= end - begin) {
        arr[count++] = copyArr[i] < copyArr[j] ? copyArr[i++] : copyArr[j++];
    }

    while (i <= mid-1) {
        arr[count++] = copyArr[i++];
    }

    while (j <= end - begin) {
        arr[count++] = copyArr[j++];
    }
}
           

複制

2.4.2. 算法分析

• 歸并排序可以是穩定的排序算法，隻要確定合并時，如果遇到兩個相等值的，前半部分那個相等的值是在後半部分那個相等的值的前面即可保證是穩定的排序算法。

• 歸并排序的時間複雜度為 O(nlogn)，無論是最好、最壞還是平均情況都一樣。

  歸并的時間複雜度分析則是遞歸代碼的時間複雜度的分析。假設求解問題 a 可以分為對 b、c 兩個子問題的求解。那麼問題 a 的時間是 T(a) 、求解 b、c 的時間分别是 T(b) 和 T(c)，那麼 T(a) = T(b) +T(c) + K。k 等于将 b、c 兩個子問題的結果合并問題 a 所消耗的時間。

  套用上述的套路，假設對 n 個元素進行歸并排序需要的時間是 T(n)，子問題歸并排序的時間是 T(n/2)，合并操作的時間複雜度是 O(n)。是以，T(n) =2 * T(n/2) +O(n)，T(1) = C。最終得到：

  T(n)= 2*T(n/2) + n

  = 2*(2*T(n/4)+ n/2)+n = 2^2*T(n/4) + 2*n

  = 2^2*(2*T(n/8)+n/4) + 2*n = 2^3*T(n/8) + 3*n

  = ....

  = 2^k*T(n/2^K) + k*n

  = ....

  = 2^(log_2^n)*T(1) + log_2^n*n

  最終得到

T(n) = Cn + nlon_2^n

，使用大 O 時間複雜表示 T(n)=O(nlogn)。

歸并排序中，無論待排數列是有序還是倒序，最終遞歸的層次都是到隻有一個數組為主，是以歸并排序跟待排序列沒有什麼關系，最好、最壞、平均的時間複雜度都是 O(nlogn)。

• 歸并排序并不是原地排序，因為在歸并排序的合并函數中，還需要額外的存儲空間，這個存儲空間是 O(n)。遞歸過程中，空間複雜度并不能像時間複雜度那樣累加。因為在每次遞歸下去的過程中，雖然合并操作都會申請額外的記憶體空間，但是合并之後，這些申請的記憶體空間就會被釋放掉。是以其實主要考慮最大問題合并時所需的空間複雜度即可，該空間複雜度為 O(n)。

2.5. 快速排序（Quick Sort）

快速排序利用的也是分治思想，核心思想是從待排數組中選擇一個元素，然後将待排數組劃分成兩個部分：左邊部分的元素都小于該元素的值，右邊部分的元素都大于該元素的值，中間是該元素的值。然後對左右兩個部分套用相同的處理方法，也就是将左邊部分的元素再劃分成左右兩部分，右邊部分的元素也再劃分成左右兩部分。以此類推，當遞歸到隻有一個元素的時候，就說明此時數組是有序了的。

2.5.1. 實作

首先要對下标從 begin 到 end 之間的資料進行分區，可以選擇 begin 到 end 之間的任意一個資料作為 pivot（分區點），一般是最後一個資料作為分區點。之後周遊 begin 到 end 之間的資料，将小于 pivot 的放在左邊，大于的 pivot 的放在右邊，将pivot 放在中間（位置 p）。經過這一操作之後，數組 begin 到 end 之間的資料就被分成了三個部分：begin 到 p-1、p、p+1 到 end。最後，傳回 pivot 的下标。那麼這個過程一般有三種方式：

• 首先說明這種方法不可取。在不考慮空間消耗的情況下，分區操作可以非常簡單。使用兩個臨時數組 X 和 Y，周遊 begin 到 end 之間的資料，将小于 pivot 的資料都放到數組 X 中，将大于 pivot 的資料都放到數組 Y 中，最後将數組 X 拷貝到原數組中，然後再放入 pivot，最後再放入數組 Y。但是采用這種方式之後，快排就不是原地排序算法了，是以可以采用以下兩種方法在原數組的基礎之上完成分區操作。
• 第一種方法還是使用兩個指針：i 和 j，i 和 j 一開始都放置在 begin 初。之後 j 指針開始周遊，如果 j 指針所指的元素小于等于 pivot，那麼則将 j 指針的元素放到 i 指針的處，i 指針的元素放置于 j 處，然後 i 後移，j 後移。如果 j 指針所指的元素大于 pivot 那麼 j 後移即可。首先個人覺得其實整個數組被分成三個區域：0-i-1 的為小于等于 pivot 的區域，i-j-1 為大于 pivot 的區域，j 之後的區域是未排序的區域。
• 第二種方法還是使用兩個指針：i 和 j，i 從 begin 處開始，j 從 end 處開始。首先 j 從 end 開始往前周遊，當遇到小于 pivot 的時候停下來，然後此時 i 從 begin 開始往後周遊，當遇到大于 pivot 的時候停下來，此時交換 i 和 j 處的元素。之後 j 繼續移動，重複上述過程，直至 i >= j。

在傳回 pivot 的下标 q 之後，再根據分治的思想，将 begin 到 q-1 之間的資料和下标 q+1 到 end 之間的資料進行遞歸。這邊一定要 q-1 和 q+1 而不能是 q 和 q+1 是因為：考慮資料已經有序的極端情況，一開始是對 begin 到 end；當分區之後 q 的位置還是 end 的位置，那麼相當于死循環了。最終，當區間縮小至 1 時，說明所有的資料都有序了。

如果用遞推公式來描述上述的過程的話，遞推公式：quick_sort(begin...end) = quick_sort(begin...q-1) + quick_sort(q+1...end)，終止條件是：begin >= end。将這兩個公式轉化為代碼之後，如下所示：

/**
 * 快速排序
 */
public void quickSort(int[] arr, int len) {
    __quickSort(arr, 0, len-1);
}

// 注意邊界條件
private void __quickSort(int[] arr, int begin, int end) {
    if (begin >= end) {
        return;
    }

    // 一定要是 p-1！
    int p = partition(arr, begin, end); // 先進行大緻排序，并擷取區分點
    __quickSort(arr, begin, p-1);
    __quickSort(arr, p+1, end);
}

private int partition(int[] arr, int begin, int end) {
    int pValue = arr[end];

    // 整兩個指針，兩個指針都從頭開始
    // begin --- i-1（含 i-1）：小于 pValue 的區
    // i --- j-1（含 j-1）：大于 pValue 的區
    // j --- end：未排序區
    int i = begin;
    int j = begin;
    while (j <= end) {
        if (arr[j] <= pValue) {
            int temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
            i++;
            j++;
        } else {
            j++;
        }
    }

    return i-1;
}
           

複制

2.5.2. 優化

• 由于分區點很重要（為什麼重要見算法分析），是以可以想方法尋找一個好的分區點來使得被分區點分開的兩個分區中，資料的數量差不多。下面介紹兩種比較常見的算法：
  • **三數取中法。就是從區間的首、尾、中間分别取出一個數，然後對比大小，取這 3 個數的中間值作為分區點。**但是，如果排序的數組比較大，那“三數取中”可能不夠了，可能就要“五數取中”或者“十數取中”，也就是間隔某個固定的長度，取資料進行比較，然後選擇中間值最為分區點。
  • 随機法。随機法就是從排序的區間中，随機選擇一個元素作為分區點。随機法不能保證每次分區點都是比較好的，但是從機率的角度來看，也不太可能出現每次分區點都很差的情況。是以平均情況下，随機法取分區點還是比較好的。
• 遞歸可能會棧溢出，最好的方式是使用非遞歸的方式；

2.5.3. 算法分析

• 快排不是一個穩定的排序算法。因為分區的過程涉及到交換操作，原本在前面的元素可能會被交換到後面去。比如 6、8、7、6、3、5、9、4 這個數組中。在經過第一次分區操作之後，兩個 6 的順序就會發生改變。
• 快排是一種原地的排序算法。

• 快排的最壞時間複雜度是 O(n^2)，最好時間複雜度是O(nlogn)，平均時間複雜度是 O(nlogn)。

  快排也是使用遞歸來實作，那麼遞歸代碼的時間複雜度處理方式和前面類似。

  快排的時間複雜度取決于 pivot 的選擇，通過合理地選擇 pivot 來使得算法的時間複雜度盡可能不出現 O(n^2) 的情況。

  • 假設每次分區操作都可以把數組分成大小接近相等的兩個小區間，那麼快排的時間複雜度和歸并排序一樣，都是 O(nlogn)。
  • 但是分區操作不一定都能把數組分成大小接近相等的兩個小區間。極端情況如數組中的數組已經有序了，如果還是取最後一個元素作為分割點，左邊區間是 n-1 個數，右邊區間沒有任何數。此時， T(n)=T(n-1)+n，最終時間複雜度退化為 O(n^2)。大部分情況下，采用遞歸樹的方法可得到時間複雜度是 O(nlogn)。由于極端情況是少數，是以平均時間複雜度是 O(nlogn)。

2.5.4. VS 歸并排序

首先從思想上來看：歸并排序的處理過程是由下到上的，先處理子問題，然後對子問題的解再合并；而快排正好相反，處理過程是由上到下的，先分區，再處理子問題。

從性能上來看：歸并是一個穩定的、時間複雜度為 O(nlogn) 的排序算法，但是歸并并不是一個原地排序算法（是以歸并沒有快排應用廣泛）。而快速排序算法時間複雜度不一定是 O(nlogn)，最壞情況下是 O(n^2)，而且不是一個穩定的算法，但是通過設計可以讓快速排序成為一個原地排序算法。

2.6. 桶排序

**桶排序的核心思想就是将要排序的資料分到幾個有序的桶裡，每個桶裡的資料再單獨進行排序。**桶内排序完成之後，再把每個桶裡的資料按照順序依次取出，組成的序列就是有序的了。一般步驟是：

• 先确定要排序的資料的範圍；
• 然後根據範圍将資料分到桶中（可以選擇桶的數量固定，也可以選擇桶的大小固定）；
• 之後對每個桶進行排序；
• 之後将桶中的資料進行合并；

img

2.6.1. 實作

public void buckerSort(int[] arr, int len, int bucketCount) {

    // 确定資料的範圍
    int minVal = arr[0];
    int maxVal = arr[0];
    for (int i = 1; i < len; ++i) {
        if (arr[i] < minVal) {
            minVal = arr[i];
        } else if (arr[i] > maxVal){
            maxVal = arr[i];
        }
    }

    // 确認每個桶的所表示的範圍
    bucketCount =  (maxVal - minVal + 1) < bucketCount ? (maxVal - minVal + 1) : bucketCount;
    int bucketSize = (maxVal - minVal + 1) / bucketCount;
    bucketCount = (maxVal -  minVal + 1) % bucketCount == 0 ? bucketCount : bucketCount + 1;

    int[][] buckets = new int[bucketCount][bucketSize];
    int[] indexArr = new int[bucketCount];  // 數組位置記錄

    // 将資料依次放入桶中
    for (int i = 0; i < len; i++) {
        int bucketIndex = (arr[i] - minVal) / bucketSize;
        if (indexArr[bucketIndex] == buckets[bucketIndex].length) {
            expandCapacity(buckets, bucketIndex);
        }
        buckets[bucketIndex][indexArr[bucketIndex]++] = arr[i];
    }

    // 桶内排序
    for (int i = 0; i < bucketCount; ++i) {
        if (indexArr[i] != 0) {
            quickSort(buckets[i], 0, indexArr[i] - 1);
        }
    }

    // 桶内資料依次取出
    int index = 0;
    for (int i = 0; i < bucketCount; ++i) {
        for (int j = 0; j < indexArr[i]; ++j) {
            arr[index++] = buckets[i][j];
        }
    }

    // 列印
    for (int i = 0; i < len; ++i) {
        System.out.print(arr[i] + " ");
    }
    System.out.println();
}

// 對數組進行擴容
public void expandCapacity(int[][] buckets, int bucketIndex) {
    int[] newArr = new int[buckets[bucketIndex].length * 2];
    System.arraycopy(buckets[bucketIndex], 0, newArr, 0, buckets[bucketIndex].length);
    buckets[bucketIndex] = newArr;
}
           

複制

2.6.2. 算法分析

• 最好時間複雜度為 O(n)，最壞時間複雜度為 O(nlogn)，平均時間複雜度為 O(n)。

  如果要排序的資料為 n 個，把這些資料均勻地分到 m 個桶内，每個桶就有 k=n/m 個元素。每個桶使用快速排序，時間複雜度為 O(k.logk)。m 個 桶的時間複雜度就是 O(m*k*logk)，轉換的時間複雜度就是 O(n*log(n/m))。當桶的數量 m 接近資料個數 n 時，log(n/m) 就是一個非常小的常量，這個時候桶排序的時間複雜度接近 O(n)。

  如果資料經過桶的劃分之後，每個桶的資料很不平均，比如一個桶中包含了所有資料，那麼桶排序就退化為 O(nlogn) 的排序算法了。

  這邊的平均時間複雜度為 O(n) 沒有經過嚴格運算，隻是采用粗略的方式得出的。因為桶排序大部分情況下，都能将資料進行大緻均分，而極少情況出現所有的資料都在一個桶裡。

• 非原地算法

  因為桶排序的過程中，需要建立 m 個桶這個的空間複雜度就肯定不是 O(1) 了。在桶内采用快速排序的情況下，桶排序的空間複雜度應該是 O(n)。

• 桶排序的穩定與否，主要看兩塊：1.将資料放入桶中的時候是否按照順序放入；2.桶内采用的排序算法。是以将資料放入桶中是按照順序的，并且桶内也采用穩定的排序算法的話，那麼整個桶排序則是穩定的。既然能穩定的話，那麼一般算穩定的。

2.6.3. 總結

• 桶排序對要排序的資料的要求是非常苛刻的。
  • 首先，要排序的資料需要很容易被劃分到 m 個桶。并且，桶與桶之間有着天然的大小順序，這樣子每個桶内的資料都排序完之後，桶與桶之間的資料不需要再進行排序；
• 其次，資料在各個桶中的分布是比較均勻的。如果資料經過桶的劃分之後，每個桶的資料很不平均，比如一個桶中包含了所有資料，那麼桶排序就退化為 O(nlogn) 的排序算法了。

• **桶排序适合應用在外部排序中。**比如要排序的資料有 10 GB 的訂單資料，但是記憶體隻有幾百 MB，無法一次性把 10GB 的資料全都加載到記憶體中。這個時候，就可以先掃描 10GB 的訂單資料，然後确定一下訂單資料的所處的範圍，比如訂單的範圍位于 1~10 萬元之間，那麼可以将所有的資料劃分到 100 個桶裡。再依次掃描 10GB 的訂單資料，把 1~1000 元之内的訂單存放到第一個桶中，1001~2000 元之内的訂單資料存放到第二個桶中，每個桶對應一個檔案，檔案的命名按照金額範圍的大小順序編号如 00、01，即第一個桶的資料輸出到檔案 00 中。

  理想情況下，如果訂單資料是均勻分布的話，每個檔案的資料大約是 100MB，依次将這些檔案的資料讀取到記憶體中，利用快排來排序，再将排序好的資料存放回檔案中。最後隻要按照檔案順序依次讀取檔案中的資料，并将這些資料寫入到一個檔案中，那麼這個檔案中的資料就是排序好了的。

  但是，訂單資料不一定是均勻分布的。劃分之後可能還會存在比較大的檔案，那就繼續劃分。比如訂單金額在 1~1000 元之間的比較多，那就将這個區間繼續劃分為 10 個小區間，1~100、101~200 等等。如果劃分之後還是很大，那麼繼續劃分，直到所有的檔案都能讀入記憶體。

  ★外部排序就是資料存儲在磁盤中，資料量比較大，記憶體有限，無法将資料全部加載到記憶體中。

  ”

2.7. 計數排序

計數排序跟桶排序類似，可以說計數排序其實是桶排序的一種特殊情況。**當要排序的 n 個資料，所處的範圍并不大的時候，比如最大值是 K，那麼就可以把資料劃分到 K 個桶，每個桶内的資料值都是相同的，**進而省掉了桶内排序的時間。可以說計數排序和桶排序的差別其實也就在于桶的大小粒度不一樣。

下面通過舉例子的方式來看一下計數排序的過程。假設數組 A 中有 8 個資料，值在 0 到 5 之間，分别是：2、5、3、0、2、3、0、3。

• 首先使用大小為 6 的數組 C[6] 來存儲每個值的個數，下标對應具體值。進而得到，C[6] 的情況為：2、0、2、3、0、1。
• 那麼，值為 3 分的資料個數有 3 個，小于 3 分的資料個數有 4 個，是以值為 3 的資料在有序數組 R 中所處的位置應該是 4、5、6。為了快速計算出位置，對 C[6] 這個數組進行變化，C[k] 裡存儲小于等于值 k 的資料個數。變化之後的數組為 2、2、4、7、7、8。
• 之後我們從後往前依次掃描資料 A（從後往前是為了穩定），比如掃描到 3 的時候，從資料 C 中取出下标為 3 的值，是7（也就說到目前為止，包含自己在内，值小于等于 3 的資料個數有 7 個），那麼 3 就是數組 R 中第 7 個元素，也就是下标為 6。當然 3 放入到數組 R 中後，C[3] 要減 1，變成 6，表示此時未排序的資料中小于等于 3 的資料個數有 6 個。
• 以此類推，當掃描到第 2 個值為 3 的資料的時候，就會将這個資料放入到 R 中下标為 5 的位置。當掃描完整個數組 A 後，數組 R 内的資料就是按照值從小到大的有序排列了。

2.7.1. 實作

/**
 * 計數排序，暫時隻能處理整數（包括整數和負數）
 * @param arr
 * @param len
 */
public void countingSort(int[] arr, int len) {
    // 确定範圍
    int minVal = arr[0];
    int maxVal = arr[0];
    for (int i = 1; i < len; ++i) {
        if (maxVal < arr[i]) {
            maxVal = arr[i];
        } else if (arr[i] < minVal) {
            minVal = arr[i];
        }
    }

    // 對資料進行處理
    for (int i = 0; i < len; ++i) {
        arr[i] = arr[i] - minVal;
    }
    maxVal = maxVal - minVal;

    // 周遊資料數組，求得計數數組的個數
    int[] count = new int[maxVal + 1];
    for (int i = 0; i < len; ++i) {
        count[arr[i]] ++;
    }
    printAll(count, maxVal + 1);

    // 對計數數組進行優化
    for (int i = 1; i < maxVal + 1; ++i) {
        count[i] = count[i - 1] + count[i];
    }
    printAll(count, maxVal + 1);

    // 進行排序，從後往前周遊（為了穩定）
    int[] sort = new int[len];
    for (int i = len - 1; i >= 0; --i) {
        sort[count[arr[i]] - 1] = arr[i] + minVal;
        count[arr[i]]--;
    }
    printAll(sort, len);
}
           

複制

2.7.2. 算法分析

• 非原地算法

  計數排序相當于桶排序的特例一樣。計數排序需要額外的 k 個記憶體空間和 n 個新的記憶體空間存放排序之後的數組。

• 穩定算法

  前面也提到了，假如采用從後往前周遊的方式話，那麼是穩定算法。

• 時間複雜度

  最好、最壞、平均時間複雜度都是一樣，為 O(n+k)，k 為資料範圍。這個從代碼的實作可以看出，無論待排數組的情況怎麼樣，都是要循環同樣的次數。

2.7.3. 總結

• 計數排序隻能用在資料範圍不大的場景中，如果資料範圍 k 比要排序的資料 n 大很多，就不适合用計數排序了。
• 計數排序隻能直接對非負整數進行排序，如果要排序的資料是其他類型的，需要在不改變相對大小的情況下，轉化為非負整數。比如當要排序的數是精确到小數點後一位時，就需要将所有的資料的值都先乘以 10，轉換為整數。再比如排序的資料中有負數時，資料的範圍是[-1000,1000]，那麼就需要先将每個資料加上 1000，轉換為非負整數。

2.8. 基數排序

桶排序和計數排序都适合範圍不是特别大的情況（請注意是範圍），但是桶排序的範圍可以比計數排序的範圍稍微大一點。假如資料的範圍很大很大，比如對手機号這種的，桶排序和技術排序顯然不适合，因為需要的桶的數量也是十分巨大的。此時，可以使用基數排序。**基數排序的思想就是将要排序的資料拆分成位，然後逐位按照先後順序進行比較。**比如手機号中就可以從後往前，先按照手機号最後一位來進行排序，之後再按照倒數第二位來進行排序，以此類推。當按照第一位重新排序之後，整個排序就算完成了。

需要注意的是**，按照每位排序的過程需要穩定的**，因為假如後一次的排序不穩定，前一次的排序結果将功虧一篑。比如，第一次對個位進行排序結果為 21、11、42、22、62，此時 21 在 22 前面；第二次對十位的排序假如是不穩定的話，22 可能跑到 21 前面去了。那麼整個排序就錯了，對個位的排序也就相當于白費了。

下面舉個字元串的例子，整個基數排序的過程如下圖所示：

img

2.8.1. 實作

/**
 * 基數排序
 * @param arr
 * @param len
 */
public void radixSort(int[] arr, int len, int bitCount) {
    int exp = 1;
    for (int i = 0; i < bitCount; ++i) {
        countingSort(arr, len, exp);
        exp = exp * 10;
    }
}

public int getBit(int value, int exp) {
    return (value / exp) % 10;
}
/**
     * 計數排序，暫時隻能處理整數（包括整數和負數）
     * @param arr
     * @param len
     */
public void countingSort(int[] arr, int len, int exp) {

    // 确定範圍
    int maxVal = getBit(arr[0], exp);
    for (int i = 1; i < len; ++i) {
        if (maxVal < getBit(arr[i], exp)) {
            maxVal = getBit(arr[i], exp);
        }
    }

    // 周遊資料數組，求得計數數組的個數
    int[] count = new int[maxVal + 1];
    for (int i = 0; i < len; ++i) {
        count[getBit(arr[i], exp)] ++;
    }

    // 對計數數組進行優化
    for (int i = 1; i < maxVal + 1; ++i) {
        count[i] = count[i - 1] + count[i];
    }

    // 進行排序，從後往前周遊（為了穩定）
    int[] sort = new int[len];
    for (int i = len - 1; i >= 0; --i) {
        sort[count[getBit(arr[i], exp)] - 1] = arr[i];
        count[getBit(arr[i], exp)]--;
    }
    System.arraycopy(sort, 0, arr, 0, len);
    printAll(sort, len);
}
           

複制

2.8.2. 算法分析

• 非原地算法

  是不是原地算法其實看針對每一位排序時所使用的算法。為了確定基數排序的時間複雜度以及每一位的穩定性，一般采用計數排序，計數排序是非原地算法，是以可以把基數排序當成非原地排序。

• 穩定算法

  因為基數排序需要確定每一位進行排序時都是穩定的，是以整個基數排序時穩定的。

• 時間複雜度是 O(kn)，k 是數組的位數

  最好、最壞、平均的時間複雜度都是 O(n)。因為無論待排數組的情況怎麼樣，基數排序其實都是周遊每一位，對每一位進行排序。假如每一位排序的過程中使用計數排序，時間複雜度為 O(n)。假如有 k 位的話，那麼則需要 k 次桶排序或者計數排序。是以總的時間複雜度是 O(kn)，當 k 不大時，比如手機号是 11 位，那麼基數排序的時間複雜度就近似于 O(n)。也可以從代碼中看出。

2.8.3. 總結

• 基數排序的一個要求是排序的資料要是等長的。當不等長時候可以在前面或者後面補 0，比如字元串排序的話，就可以在後面補 0，因為 ASCII 碼中所有的字母都大于 “0”，是以補 “0” 不會影響到原有的大小排序。

  基數排序的另一個要求就是資料可以分割出獨立的 “位” 來比較，而且位之間存在遞進關系：如果 a 資料的高位比 b 資料大，那麼剩下的低位就不用比較了。

  除此之外，每一個位的資料範圍不能太大，要能用線性排序算法來排序，否則，基數排序時間複雜度無法達到 O(n)。

3. 排序函數

幾乎所有程式設計語言都會提供排序函數，比如 C 語言中 qsort()、C++ STL 中的 sort()/stable_sort()、Java 中的 Collections.sort()。這些排序函數，并不會隻采用一種排序算法，而是多種排序算法的結合。當然主要使用的排序算法都是 O(nlogn) 的。

• glibc 的 qsort() 排序函數。qsort() 會優先使用歸并排序算法。當排序的資料量很大時，會使用快速排序。使用排序算法的時候也會進行優化，如使用 “三數取中法”、在堆上手動實作一個棧來模拟遞歸來解決。在快排的過程中，如果排序的區間的元素個數小于等于 4 時，則使用插入排序。而且在插入排序中還用到了哨兵機制，減少了一次判斷。

  ★在小規模資料面前 O(n^2) 時間複雜度的算法并不一定比 O(nlogn)的算法執行時間長。主要是因為時間複雜度會将系數和低階去掉。

  ”

• Array.sort() 排序函數，使用 TimSort 算法。TimSort 算法是一種歸并算法和插入排序算法混合的排序算法。基本工作過程就是：

  整個排序過程，分段選擇政策可以保證 O(nlogn) 的時間複雜度。TimSort 主要利用了待排序列中可能有些片段已經基本有序的特性。之後，對于小片段采用插入算法進行合并，合并成大片段。最後，再使用歸并排序的方式進行合并，進而完成排序工作。

  • 掃描數組，确定其中的單調上升段和單調下降段，将嚴格下降段反轉；
  • 定義最小基本片段長度，長度不滿足的單調片段通過插入排序的方式形成滿足長度的單調片段（就是長度大于等于所要求的最小基本片段長度）
  • 反複歸并一些相鄰片段，過程中避免歸并長度相差很大的片段，直至整個排序完成。

4. 附加知識

4.1. 有序度、逆序度

在以從小到大為有序的情況中，有序度是數組中有序關系的元素對的個數，用數學公式表示如下所示。

如果 i < j，那麼 a[i] < a[j]
           

複制

比如 2、4、3、1、5、6 這組資料的有序度是 11；倒序排列的數組，有序度是 0；一個完全有序的數組，有序度為滿有序度，為 n*(n-1)/2，比如1、2、3、4、5、6，有序度就是 15。

逆序度的定義正好跟有序度的定義相反

如果 i < j，那麼 a[i] > a[j]
           

複制

關于逆序度、有序度、滿有序度滿足如下公式

逆序度 = 滿有序度 - 有序度
           

複制

排序的過程其實就是減少逆序度，增加有序度的過程，如果待排序序列達到滿有序度了，那麼此時的序列就是有序了。

5. 總結

• 冒泡排序、選擇排序可能就停留在理論的層面，實際開發應用中不多，但是插入排序還是挺有用的，有些排序算法優化的時候就會用到插入排序，比如在排序資料量小的時候會先選擇插入排序。
• 冒泡、選擇、插入三者的時間複雜度一般都是按 n^2 來算。**并且這三者都有一個共同特點，那就是都會将排序數列分成已排序和未排序兩部分。**外層循環一次，其實是讓有序部分增加一個，是以外層循環相當于對有序部分和未排序部分進行分割。而外層循環次數就是待排序的資料的個數；内層循環則主要負責處理未排序部分的元素。
• 快排的分區過程和分區思想其實特别好用，在解決很多非排序的問題上都會遇到。比如如何在 O(n) 的時間複雜度内查找一個 k 最值的問題（還用到分治，更多是分區這種方式）；比如将一串字元串劃分成字母和數字兩部分（其實就是分區，是以需要注意分區過程的應用）。以後看到類似分區什麼的，可以想想快排分區過程的操作。
• 快排和歸并使用都是分治的思想，都可使用遞歸的方式實作。隻是歸并是從下往上的處理過程，是先進行子問題處理，然後再合并；而快排是從上往下的處理過程，是先進行分區，而後再進行子問題處理。
• 桶排序、計數排序、基數排序的時間複雜度是線性的，是以這類排序算法叫做線性排序。之是以這能做到線性排序，主要是因為這三種算法都不是基于比較的排序算法，不涉及到元素之間的比較操作。但是這三種算法對排序的資料要求很苛刻。如果資料特征比較符合這些排序算法的要求，這些算法的複雜度可以達到 O(n)。
• 桶排序、計數排序針對範圍不大的資料是可行的，它們的基本思想都是将資料劃分為不同的桶來實作排序。

• 各種算法比較

  排序算法平均時間複雜度最好時間複雜度最壞時間複雜度是否是原地排序是否穩定冒泡O(n^2)O(n)O(n^2)√√插入O(n^2)O(n)O(n^2)√√選擇O(n^2)O(n^2)O(n^2)√×歸并O(nlogn)O(nlogn)O(nlogn)× O(n)√快排O(nlogn)O(nlogn)O(n^2)√×桶排序O(n)O(n)O(nlogn)×√計數排序O(n+k)O(n+k)O(n+k)×√基數排序O(kn)O(kn)O(kn)×√

巨人的肩膀

1. 極客時間，《資料結構與算法之美》，王争
2. 《算法圖解》