0. 前言

大家好，我是多選參數的程序鍋，一個正在搗鼓操作系統、學數據結構和算法以及 Java 的失業人員。數據結構和算法我已經學了有一段日子了，最近也開始在刷 LeetCode 上面的題目了，但是自己感覺在算法上還是 0 ，還得猛補啊。

今天這篇基于之前的 8 大排序算法基礎之上，增加一個堆排序，也就是這么 9 個排序算法：冒泡排序、插入排序、選擇排序、歸并排序、快速排序、堆排序、桶排序、計數排序、基數排序。它們對應的時間復雜度如下所示：

排序算法時間復雜度是否基于比較

冒泡、插入、選擇	O(n^2)	√
快排、歸并、堆排序	O(nlogn)	√
桶、計數、基數	O(n)	×

整篇文章的主要知識提綱如圖所示，本篇相關的代碼都可以從 https://github.com/DawnGuoDev/algorithm 獲取，另外，該倉庫除了包含了基礎的數據結構和算法實現之外，還會有數據結構和算法的筆記、LeetCode 刷題記錄（多種解法、Java 實現） 、一些優質書籍整理。

★

本文的圖很多都是從極客時間王爭老師專欄那邊拷貝過來或者截圖過來的，少部分圖是自己重新畫的。為什么不全都換成自己畫的圖？主要是我比較懶，我覺得圖能將自己要闡述的點解釋清楚，或者說和自己整理過后的文字結合的不錯，我覺得這個圖就沒必要重新畫了，人家的畫已經很好看了，也很清晰了，你將它重新畫，其實也是差不多，可能就是換個樣式而已，核心的東西還是沒有變。但是，在有些地方，我覺得別人的圖跟我闡述的內容不符合，或者不能很好地闡述我想表達的東西，又或者這個地方需要一個圖，那么我會畫一個。

”

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，從小到大進行排序。第一次排序情況如下：

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

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進行排序。左側橙紅色表示的是已排序區間，右側黃色的表示未排序區間。整個插入排序過程如下所示

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. 選擇排序

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

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

  最終得到?，使用大 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. 堆排序

堆是一種特殊的樹。只要滿足以下兩個條件就是一個堆。

• 堆是一個完全二叉樹。既然是完全二叉樹，那么使用數組存儲的方式將會很方便。

• 堆中的每個節點的值都必須大于等于（或小于等于）其子節點的值。對于大于等于子節點的堆又被稱為“大頂堆”；小于等于子節點的堆又被稱為“小頂堆”。

由于”堆是一個完全二叉樹“，因此一般堆使用數組來存儲，一是節省空間，二是通過數組的下標就可以找到父節點、左右子節點（數組下標最好從 1 開始，該節的代碼實現都將從數組下標為 1 的地方開始）。那么，借助堆這種數據結構實現的排序被稱為堆排序。堆排序是一種原地的、時間復雜度為 O(nlogn) 且不穩定的排序算法。

2.6.1. 實現

整個堆排序的實現分為建堆和排序兩個步驟。

建堆

首先是將待排序數組建立成一個堆，秉著能不借助額外數組則不借助的原則，我們可以直接在原數組上直接操作。這樣，建堆有兩個方法：

• 第一種方法類似于上述堆的操作中“往堆中插入一個元素”的思想。剛開始的時候假設堆中只有一個元素，也就是下標為 1 的元素。然后，將下標為 2 的元素插入堆中，并對堆進行調整。以此類推，將下標從 2 到 n 的元素依次插入到堆中。這種建堆方式相當于將待排序數組分成“堆區”和“待插入堆區”。

  如圖所示，我們將對待排序數據 7、5、19、8、4 進行建堆（大頂堆）。可以看到初始化堆就一個元素 7。之后將指針移到下標為 2 的位置，將 5 這個元素添加到堆中并從下往上進行堆化。之后，再將指針移到下標為 3 的位置，將 19 這個元素添加到堆中并從下往上進行堆化。依次類推。

• 第二種方法是將整個待排序數組都當成一個“堆”，但是這個“堆”不一定滿足堆的兩個條件，因此我們需要對其進行整體調整。那么，調整的時候是從數組的最后開始，依次往前調整。調整的時候，只需要調整該節點及其子樹滿足堆的要求，并且是從上往下的方式進行調整。由于，葉子節點沒有子樹，所以葉子節點沒必要調整，我們只需要從第一個非葉子節點開始調整（這邊的第一是從后往前數的第一個）。那么第一個非葉子節點的下標為 n/2，因此我們只需要對 n/2 到 1 的數組元素進行從上往下堆化即可（下標從 n/2 到 1 的數組元素所在節點都是非葉子節點，下標從 n/2+1 到 n 的數組元素所在節點都是葉子節點）。

  如圖所示，我們將對待排序數據 7、5、19、8、4、1、20、13、16 進行建堆（大頂堆）。可以看到整個過程是從 8 這個元素開始進行堆化。在對 8 進行堆化的時候，僅對 8 及其子樹進行堆化。在對 5 進行堆化的時候，僅對 5 及其子樹進行堆化。

我們將第二種思路實現成如下代碼段所示：

public void buildHeap(int[] datas, int len) {this.heap = datas;this.capacity = len - 1;this.count = len - 1;for (int i = this.count/2; i >=1; i--) {heapifyFromTop(i);} }public void heapifyFromTop(int begin) {while (true) {int i = begin; // i 是節點及其左右子節點中較大值的那個節點的下標/* 就是在節點及其左右子節點中選擇一個最大的值，與節點所處的位置進行；但是，需要注意的是假如這個值正好是節點本身，那么直接退出循環；否則需要進行交換，然后從交換之后的節點開始繼續堆化 */if (begin * 2 <= this.count && this.heap[begin] < this.heap[2 * begin]) {i = 2 * begin;}if ((2 * begin + 1) <= this.count && this.heap[i] < this.heap[2 * begin + 1]) {i = 2 * begin + 1;}if (i == begin) {break;}swap(begin, i);begin = i;} } ★

為什么下標從 n/2 到 1 的數組元素所在節點都是非葉子節點，下標從 n/2+1 到 n 的數組元素所在節點都是葉子節點？這個算是完全二叉樹的一個特性。嚴格的證明暫時沒有，不嚴謹的證明還是有的。這里采用反證法，假如 n/2 + 1 不是葉子節點，那么它的左子節點下標應該為 n+2，但是整個完全二叉樹最大的節點的下標為 n。所以 n/2 + 1 不是葉子節點不成立，即 n/2 + 1 是葉子節點。那么同理可證 n/2 + 1 到 n 也是如此。而對于下標為 n/2 的節點來說，它的左子節點有的話下標應該為 n，n 在數組中有元素，因此 n/2 有左子節點，即 n/2 不是葉子節點。同理可證 1 到 n/2 都不是葉子節點。

”

排序

建完堆（大頂堆）之后，接下去的步驟是排序。那么具體該怎么實現排序呢？

此時，我們可以發現，堆頂的元素是最大的，即數組中的第一個元素是最大的。實現排序的過程大致如下：我們把它跟最后一個元素交換，那最大元素就放到了下標為 n 的位置。此時堆頂元素不是最大，因此需要進行堆化。采用從上而下的堆化方法（參考刪除堆頂元素的堆化方法），將剩下的 n-1 個數據構建成堆。最后一個數據因為已知是最大了，所以不用參與堆化了。n-1 個數據構建成堆之后，再將堆頂的元素（下標為 1 的元素）和下標為 n-1 的元素進行交換。一直重復這個過程，直至堆中只剩一個元素，此時排序工作完成。如圖所示，這是整個過程的示意圖。

下面將排序的過程使用 Java 實現，如下所示。那么講建堆和排序的過程結合在一起之后就是完整的堆排序了。

public void heapSort() {while (this.count > 1) {swap(this.count, 1);this.count--;heapifyFromTop(1);} } ★

詳細的代碼看文章開頭給出的 Github 地址。

”

2.6.2. 算法分析

時間復雜度

堆排序的時間復雜度是由建堆和排序兩個步驟的時間復雜度疊加而成。

• 建堆的時間復雜度

在采用第二方式建堆時，從粗略的角度來看，每個節點進行堆化的時間復雜度是 O(logn)，那么 n/2 個節點堆化的總時間復雜度為 O(nlogn)。但是這此時粗略的計算，更加精確的計算結果不是 O(nlogn)，而是 O(n)。

因為葉子節點不需要進行堆化，所以需要堆化的節點從倒數第二層開始。每個節點需要堆化的過程中，需要比較和交換的次數，跟這個節點的高度 k 成正比。那么所有節點的高度之和，就是所有節點堆化的時間復雜度。假設堆頂節點對應的高度為 h ，那么整個節點對應的高度如圖所示（以滿二叉樹為例，最后一層葉子節點不考慮）。

那么將每個非葉子節點的高度求和為

求解這個公式可將兩邊同時乘以 2 得到 S2，

然后再減去 S1，從而就得到 S1

由于

所以最終時間復雜度為 O(2n-logn)，也就是 O(n)。

• 排序的時間復雜度

排序過程中，我們需要進行 (n-1) 次堆化，每次堆化的時間復雜度是 O(logn)，那么排序階段的時間復雜度為 O(nlogn)。

• 總的時間復雜度

那么，整個總的時間復雜度為 O(nlogn)。

★

不對建堆過程的時間復雜度進行精確計算，也就是建堆以 O(nlogn) 的時間復雜度算的話，那么總的時間復雜度還是 O(nlogn)。

”

穩定與否

堆排序不是穩定的排序算法。因為在排序階段，存在將堆的最后一個節點跟堆頂點進行互換的操作，所以有可能會改變相同數據的原始相對順序。比如下面這樣一組待排序 20、16、13、13 ，在排序時，第二個 13 會跟 20 交換，從而更換了兩個 13 的相對順序。

是否原地

堆排序是原地排序算法，因為堆排序的過程中的兩個步驟中都只需要極個別臨時存儲空間。

2.6.3. 總結

在實際開發中，為什么快速排序要比堆排序性能要好？

對于同樣的數據，在排序過程中，堆排序算法的數據交換次數要多于快速排序

對于基于比較的排序算法來說，整個排序過程就是由比較和交換這兩個操作組成。快速排序中，交換的次數不會比逆序度多。但是堆排序的過程，第一步是建堆，這個過程存在大量的比較交換操作，并且很有可能會打亂數據原有的相對先后順序，導致原數據的有序度降低。比如，在對一組已經按從小到大的順序排列的數據進行堆排序時，那么建堆過程會將這組數據構建成大頂堆，而這一操作將會讓數據變得更加無序。而采用快速排序的方法時，只需要比較而不需要交換。

★

最直接的方式就是做個試驗看一下，對交換次數進行統計。

”

堆排序的訪問方式沒有快速排序友好

快速排序來說，數據是順序訪問的。而堆排序，數據是跳著訪問的。訪問的數據量如何很大的話，那么堆排序可能對 CPU 緩存不太友好。

2.7. 桶排序

**桶排序的核心思想就是將要排序的數據分到幾個有序的桶里，每個桶里的數據再單獨進行排序。**桶內排序完成之后，再把每個桶里的數據按照順序依次取出，組成的序列就是有序的了。一般步驟是：

• 先確定要排序的數據的范圍；

• 然后根據范圍將數據分到桶中（可以選擇桶的數量固定，也可以選擇桶的大小固定）；

• 之后對每個桶進行排序；

• 之后將桶中的數據進行合并；

2.7.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.7.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.7.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.8. 計數排序

計數排序跟桶排序類似，可以說計數排序其實是桶排序的一種特殊情況。**當要排序的 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.8.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.8.2. 算法分析

• 非原地算法

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

• 穩定算法

  前面也提到了，假如采用從后往前遍歷的方式話，那么是穩定算法。

• 時間復雜度

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

2.8.3. 總結

• 計數排序只能用在數據范圍不大的場景中，如果數據范圍 k 比要排序的數據 n 大很多，就不適合用計數排序了。

• 計數排序只能直接對非負整數進行排序，如果要排序的數據是其他類型的，需要在不改變相對大小的情況下，轉化為非負整數。比如當要排序的數是精確到小數點后一位時，就需要將所有的數據的值都先乘以 10，轉換為整數。再比如排序的數據中有負數時，數據的范圍是[-1000,1000]，那么就需要先將每個數據加上 1000，轉換為非負整數。

2.9. 基數排序

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

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

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

2.9.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.9.2. 算法分析

• 非原地算法

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

• 穩定算法

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

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

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

2.9.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(nlogn)	O(nlogn)	O(nlogn)	√	×
  桶排序	O(n)	O(n)	O(nlogn)	×	√
  計數排序	O(n+k)	O(n+k)	O(n+k)	×	√
  基數排序	O(kn)	O(kn)	O(kn)	×	√

6. 巨人的肩膀

極客時間，《數據結構與算法之美》，王爭

《算法圖解》

往期推薦

URL 去重的 6 種方案！(附詳細代碼)

多圖證明，Java到底是值傳遞還是引用傳遞？

阿里為什么推薦使用LongAdder，而不是volatile？

關注下方二維碼，收獲更多干貨！

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的万字详解|手撕 9大排序算法！的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。