0.算法概述

0.1 算法分類

1、時間復雜度O(n^2)級排序算法：

• 選擇排序
• 插入排序
• 冒泡排序

2、時間復雜度O(nlogn)級排序算法：

• 快速排序
• 希爾排序
• 歸并排序
• 堆排序

3、時間復雜度O(n)級排序算法：

• 桶排序
• 基數排序
• 計數排序

4、比較類排序

• 交換排序
  • 冒泡排序 Bubble Sort
  • 快速排序 Quick Sort
• 插入排序
  • 簡單插入排序 Insertion Sort
  • 希爾排序 Shell Sort
• 選擇排序
  • 簡單選擇排序 Selection Sort
  • 堆排序 Heap Sort
• 歸并排序
  • 二路歸并排序 Merge Sort
  • 多路歸并排序 Merge Sort
• 非比較排序
  • 計數排序 Counting Sort
  • 基數排序 Radix Sort
  • 桶排序 Bucket Sort

0.2 算法復雜度

0.3 相關概念

時空復雜度：

時間復雜度：時間隨著問題（數據）規模的擴大而如何變化的：一般講時間復雜度都是講”最壞“的；

• 不考慮必須要做的操作：循環、賦初值、程序初始化：----->O(1)
• 不考慮常數項：2n -----> n
• 不考慮低次項：n^（2+n）-----> n^2

空間復雜度：算法需要用到的額外空間，不包括該問題必須分配的空間；

分類：

• 非線性時間比較類排序：通過比較來決定元素間的相對次序，由于其時間復雜度不能突破O(nlogn)，因此稱為非線性時間比較類排序；

• 線性時間非比較類排序：不通過比較來決定元素間的相對次序，它可以突破基于比較排序的時間下界，以線性時間運行，因此稱為線性時間非比較類排序；

• 內排序：所有排序操作都在內存中完成；

• 外排序：由于數據太大，因此把數據放在磁盤中，而排序通過磁盤和內存的數據傳輸才能進行；

穩定性：

• 假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，則稱這種排序算法是穩定的；否則稱為不穩定的。

推薦的標準來源于面試筆試的考察情況：

冒泡排序 ■■□□□
快速排序 ■■■■■
插入排序 ■■■□□
希爾排序 ■□□□□
歸并排序 ■■■■■
選擇排序 ■■□□□
堆排序 ■■■■□
計數排序 ■■□□□
基數排序 ■□□□□
桶排序 ■□□□□
根據上面的情況，相信你會有所側重地學習排序算法。

1. 冒泡排序（Bubble Sort）

依次比較兩個相鄰的元素，如果順序（如從大到小、首字母從Z到A）錯誤就把他們交換過來。走訪元素的工作是重復地進行直到沒有相鄰元素需要交換，也就是說該元素列已經排序完成。

1.1 算法描述：

• 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個；
• 對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數；
• 針對所有的元素重復以上的步驟，除了最后一個；
• 持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較；

1.2 圖解演示

1.3 代碼實現

冒泡排序第一種寫法：

代碼如下：

public static void bubbleSort(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {for (int j = 0; j < arr.length - 1 - i; j++) {if (arr[j] > arr[j + 1]) {// 如果左邊的數大于右邊的數，則交換，保證右邊的數字最大swap(arr, j, j + 1);}}}
}
// 交換元素
private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

1.4 優化過程

• 一邊比較一邊向后兩兩交換，將最大值 / 最小值冒泡到最后一位；

• 經過優化的寫法：使用一個變量記錄當前輪次的比較是否發生過交換，如果沒有發生交換表示已經有序，不再繼續排序；

• 進一步優化的寫法：除了使用變量記錄當前輪次是否發生交換外，再使用一個變量記錄上次發生交換的位置，下一輪排序時到達上次交換的位置就停止比較；

  最外層的 for 循環每經過一輪，剩余數字中的最大值就會被移動到當前輪次的最后一位，中途也會有一些相鄰的數字經過交換變得有序。總共比較次數是 (n-1)+(n-2)+(n-3)+…+1(n?1)+(n?2)+(n?3)+…+1。

冒泡排序第二種寫法：

第二種寫法是在第一種寫法的改良基礎下而來，代碼如下：

public static void bubbleSort(int[] arr) {// 初始時 swapped 為 true，否則排序過程無法啟動boolean swapped = true;for (int i = 0; i < arr.length - 1; i++) {// 如果沒有發生過交換，說明剩余部分已經有序，排序完成if (!swapped) break;// 設置 swapped 為 false，如果發生交換，則將其置為 trueswapped = false;for (int j = 0; j < arr.length - 1 - i; j++) {if (arr[j] > arr[j + 1]) {// 如果左邊的數大于右邊的數，則交換，保證右邊的數字最大swap(arr, j, j + 1);// 表示發生了交換swapped = true;}}}
}

最外層的 for 循環每經過一輪，剩余數字中的最大值仍然是被移動到當前輪次的最后一位。這種寫法相對于第一種寫法的優點是：如果一輪比較中沒有發生過交換，則立即停止排序，因為此時剩余數字一定已經有序了。

看下動圖演示：

圖中可以看出：

第一輪排序將數字 66 移動到最右邊；
第二輪排序將數字 55 移動到最右邊，同時中途將 11 和 22 排了序；
第三輪排序時，沒有發生交換，表明排序已經完成，不再繼續比較。

冒泡排序的第三種寫法：

第三種寫法比較少見，它是在第二種寫法的基礎上進一步優化：

經過再一次的優化，代碼看起來就稍微有點復雜了。最外層的 while 循環每經過一輪，剩余數字中的最大值仍然是被移動到當前輪次的最后一位。

在下一輪比較時，只需比較到上一輪比較中，最后一次發生交換的位置即可。因為后面的所有元素都沒有發生過交換，必然已經有序了。

最好情況：在數組已經有序的情況下，只需遍歷一次，由于沒有發生交換，排序結束。

最差情況：數組順序為逆序，每次比較都會發生交換。

代碼如下：

public static void bubbleSort(int[] arr) {boolean swapped = true;// 最后一個沒有經過排序的元素的下標int indexOfLastUnsortedElement = arr.length - 1;// 上次發生交換的位置int swappedIndex = -1;while (swapped) {swapped = false;for (int i = 0; i < indexOfLastUnsortedElement; i++) {if (arr[i] > arr[i + 1]) {// 如果左邊的數大于右邊的數，則交換，保證右邊的數字最大swap(arr, i, i + 1);// 表示發生了交換swapped = true;// 更新交換的位置swappedIndex = i;}}// 最后一個沒有經過排序的元素的下標就是最后一次發生交換的位置indexOfLastUnsortedElement = swappedIndex;}
}

1.5 性能分析

時間復雜度、空間復雜度：

• ? 第一種寫法的比較次數為 (n-1)+(n-2)+(n-3)+…+1，總比較次數為 (n^2)/2，所以時間復雜度為 O(n^2)，使用空間只有 i、j 兩個變量，所以空間復雜度為 O(1);

• ? 第二種寫法在數組已經有序的情況下比較次數為 n-1，只需比較一輪即可完成排序，此時時間復雜度為 O(n)，最壞的情況和第一種寫法一樣，平均時間復雜度仍是 O(n^2)使用的空間最多 i、j、swapped、temp 四個變量，最好的情況下只有 i、j、swapped 三個變量，所以空間復雜度為 O(1);

• ? 第三種寫法時間復雜度和第二種寫法一樣，平均時間復雜度是 O(n^2)只是實際運行效率比第二種寫法好一些；使用的空間最多 swapped、indexOfLastUnsortedElement、swappedIndex、i、temp 五個變量，最好的情況下沒有 temp 變量，所以空間復雜度為 O(1)。

穩定性：

? 冒泡排序就是把小的元素往前調或者把大的元素往后調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。所以，如果兩個元素相等，是不會再交換的；如果兩個相等的元素沒有相鄰，那么即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩定排序算法。

2. 選擇排序（Selection Sort）

選擇排序（Selectionsort）是一種簡單直觀的排序算法。它的工作原理是：第一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最小（大）元素，然后放到已排序的序列的末尾。以此類推，直到全部待排序的數據元素的個數為零。

2.1 算法描述：

n個記錄的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。具體算法描述如下：

• 初始狀態：無序區為N[1…n]，有序區為空；
• 第i趟排序(i=1,2,3…n-1)開始時，當前有序區和無序區分別為N[1…i-1]和N(i…n）。該趟排序從當前無序區中選出關鍵字最小的記錄 N[m]，將它與無序區的第1個記錄N交換，使N[1…i]和N[i+1…n)分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區；
• n-1趟結束，數組有序化了。

2.2 圖解演示

2.3 代碼實現

public static void selectionSort(int[] arr) {int minIndex;for (int i = 0; i < arr.length - 1; i++) {minIndex = i;for (int j = i + 1; j < arr.length; j++) {if (arr[minIndex] > arr[j]) {// 記錄最小值的下標minIndex = j;}}// 將最小元素交換至首位int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}
}

2.4 優化過程

二元選擇排序：

選擇排序算法也是可以優化的，既然每輪遍歷時找出了最小值，何不把最大值也順便找出來呢？這就是二元選擇排序的思想。

使用二元選擇排序，每輪選擇時記錄最小值和最大值，可以把數組需要遍歷的范圍縮小一倍。

public static void selectionSort2(int[] arr) {int minIndex, maxIndex;// i 只需要遍歷一半for (int i = 0; i < arr.length / 2; i++) {minIndex = i;maxIndex = i;for (int j = i + 1; j < arr.length - i; j++) {if (arr[minIndex] > arr[j]) {// 記錄最小值的下標minIndex = j;}if (arr[maxIndex] < arr[j]) {// 記錄最大值的下標maxIndex = j;}}
// 如果 minIndex 和 maxIndex 都相等，那么他們必定都等于 i，且后面的所有數字都與 arr[i] 相等，此時已經排序完成if (minIndex == maxIndex) break;// 將最小元素交換至首位int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;
// 如果最大值的下標剛好是 i，由于 arr[i] 和 arr[minIndex] 已經交換了，所以這里要更新 maxIndex 的值。if (maxIndex == i) maxIndex = minIndex;// 將最大元素交換至末尾int lastIndex = arr.length - 1 - i;temp = arr[lastIndex];arr[lastIndex] = arr[maxIndex];arr[maxIndex] = temp;}
}

我們使用 minIndex 記錄最小值的下標，maxIndex 記錄最大值的下標。每次遍歷后，將最小值交換到首位，最大值交換到末尾，就完成了排序。

由于每一輪遍歷可以排好兩個數字，所以最外層的遍歷只需遍歷一半即可。

二元選擇排序中有一句很重要的代碼，它位于交換最小值和交換最大值的代碼中間：

if (maxIndex == i) maxIndex = minIndex;

這行代碼的作用處理了一種特殊情況：如果最大值的下標等于 i，也就是說 arr[i] 就是最大值，由于 arr[i] 是當前遍歷輪次的首位，它已經和 arr[minIndex] 交換了，所以最大值的下標需要跟蹤到 arr[i] 最新的下標 minIndex。

二元選擇排序的效率：
在二元選擇排序算法中，數組需要遍歷的范圍縮小了一倍。那么這樣可以使選擇排序的效率提升一倍嗎？

從代碼可以看出，雖然二元選擇排序最外層的遍歷范圍縮小了，但 for 循環內做的事情翻了一倍。也就是說二元選擇排序無法將選擇排序的效率提升一倍。但實測會發現二元選擇排序的速度確實比選擇排序的速度快一點點，它的速度提升主要是因為兩點：

• 在選擇排序的外層 for 循環中，i 需要加到 arr.length - 1 ，二元選擇排序中 i 只需要加到 arr.length / 2
• 在選擇排序的內層 for 循環中，j 需要加到 arr.length ，二元選擇排序中 j 只需要加到 arr.length - i

二元選擇排序雖然比選擇排序要快，但治標不治本，二元選擇排序中做的優化無法改變其時間復雜度，二元選擇排序的時間復雜度仍然是 O(n^2)；只使用有限個變量，空間復雜度 O(1)。

2.5 性能分析

時間復雜度：

? 擇排序的交換操作介于 0 和 (n - 1)次之間。選擇排序的比較操作為 n (n - 1） / 2 次之間。選擇排序的賦值操作介于 0 和 3 (n - 1） 次之間。比較次數O(n^2）

比較次數與關鍵字的初始狀態無關，總的比較次數N=(n-1）+(n-2）+…+1=n*(n-1）/2。交換次數O(n），最好情況是，已經有序，交換0次；最壞情況交換n-1次，逆序交換n/2次，由于選擇排序在進行排序時無論數組是非有序都需要進行相同次數的尋找和比較，所以最好和最差情況下的時間復雜度都是O(n^2)

空間復雜度：

? 分配變量時不考慮，臨時變量分配完在一次for循環后就消失，沒有用到額外的空間，所以空間復雜度為O(1)。

穩定性：

? 選擇排序是給每個位置選擇當前元素最小的，比如給第一個位置選擇最小的，在剩余元素里面給第二個元素選擇第二小的，依次類推，直到第n-1個元素，第n個元素不用選擇了，因為只剩下它一個最大的元素了。那么，在一趟選擇，如果一個元素比當前元素小，而該小的元素又出現在一個和當前元素相等的元素后面，那么交換后穩定性就被破壞了。舉個例子，序列{5,8,5,2,9}，我們知道第一遍選擇第1個元素5會和2交換，那么原序列中兩個5的相對前后順序就被破壞了，所以選擇排序是一個不穩定的排序算法。

2.6 拓展

現在讓我們思考一下，冒泡排序和選擇排序有什么異同？

• 相同點：
  • 都是兩層循環，時間復雜度都為 O(n^2)；都只使用有限個變量，空間復雜度 O(1)。
• 不同點：
  • 冒泡排序在比較過程中就不斷交換，而選擇排序增加了一個變量保存最小值 / 最大值的下標，遍歷完成后才交換，減少了交換次數。
• 事實上還有一個非常重要的不同點，那就是：
  • 冒泡排序法是穩定的，選擇排序法是不穩定的。

那么排序算法的穩定性有什么意義呢？

? 其實它只在一種情況下有意義：當要排序的內容是一個對象的多個屬性，且其原本的順序存在意義時，如果我們需要在二次排序后保持原有排序的意義，就需要使用到穩定性的算法。排序算法的穩定性與效率、可靠性都無關。

舉個例子，如果我們要對一組商品排序，商品存在兩個屬性：價格和銷量。當我們按照價格從高到低排序后，要再按照銷量對其排序，這時，如果要保證銷量相同的商品仍保持價格從高到低的順序，就必須使用穩定性算法。

? 當然，算法的穩定性與具體的實現有關。在修改比較的條件后，穩定性排序算法可能會變成不穩定的。如冒泡算法中，如果將「左邊的數大于右邊的數，則交換」這個條件修改為「左邊的數大于或等于右邊的數，則交換」，冒泡算法就變得不穩定了。同樣地，不穩定排序算法也可以經過修改，達到穩定的效果。

思考一下，選擇排序算法如何實現穩定排序呢？

? 實現的方式有很多種，這里給出一種最簡單的思路：新開一個數組，將每輪找出的最小值依次添加到新數組中，選擇排序算法就變成穩定的了。

? 但如果將尋找最小值的比較條件由arr[minIndex] > arr[j]修改為arr[minIndex] >= arr[j]，即使新開一個數組，選擇排序算法依舊是不穩定的。所以分析算法的穩定性時，需要結合具體的實現邏輯才能得出結論，我們通常所說的算法穩定性是基于一般實現而言的。

3. 插入排序（Insertion Sort）

插入排序的思想非常簡單，生活中有一個很常見的場景：在打撲克牌時，我們一邊抓牌一邊給撲克牌排序，每次摸一張牌，就將它插入手上已有的牌中合適的位置，逐漸完成整個排序。

3.1 算法描述

插入排序有兩種寫法：

• 交換法：在新數字插入過程中，不斷與前面的數字交換，直到找到自己合適的位置。

• 移動法：在新數字插入過程中，與前面的數字不斷比較，前面的數字不斷向后挪出位置，當新數字找到自己的位置后，插入一次即可。

• 具體算法描述如下：

• 從第一個元素開始，該元素可以認為已經被排序；

• 取出下一個元素，在已經排序的元素序列中從后向前掃描；

• 如果該元素（已排序）大于新元素，將該元素移到下一位置；

• 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置；

• 將新元素插入到該位置后；

• 重復步驟2~5。

3.2 圖解演示

3.3 代碼演示：

public static void insertSort(int[] arr) {// 從第二個數開始，往前插入數字for (int i = 1; i < arr.length; i++) {// j 記錄當前數字下標int j = i;// 當前數字比前一個數字小，則將當前數字與前一個數字交換while (j >= 1 && arr[j] < arr[j - 1]) {swap(arr, j, j - 1);// 更新當前數字下標j--;}}
}
private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

3.4 優化過程

移動法插入排序：

? 我們發現，在交換法插入排序中，每次交換數字時，swap 函數都會進行三次賦值操作。但實際 上，新插入的這個數字并不一定適合與它交換的數字所在的位置。也就是說，它剛換到新的位置上不久，下一次比較后，如果又需要交換，它馬上又會被換到前一個數字的位置。

? 我們可以想到一種優化方案：讓新插入的數字先進行比較，前面比它大的數字不斷向后移動，直到找到適合這個新數字的位置后，新數字只做一次插入操作即可。整個過程就像是已經有一些數字坐成了一排，這時一個新的數字要加入，所以這一排數字不斷地向后騰出位置，當新的數字找到自己合適的位置后，就可以直接坐下了。重復此過程，直到排序結束。

動圖演示：

這種方案我們需要把新插入的數字暫存起來，代碼如下：

public static void insertSort(int[] arr) {// 從第二個數開始，往前插入數字for (int i = 1; i < arr.length; i++) {int currentNumber = arr[i];int j = i - 1;// 尋找插入位置的過程中，不斷地將比 currentNumber 大的數字向后挪while (j >= 0 && currentNumber < arr[j]) {arr[j + 1] = arr[j];j--;}// 兩種情況會跳出循環：1. 遇到一個小于或等于 currentNumber 的數字，跳出循環，currentNumber 就坐到它后面。// 2. 已經走到數列頭部，仍然沒有遇到小于或等于 currentNumber 的數字，也會跳出循環，此時 j 等于 -1，currentNumber 就坐到數列頭部。arr[j + 1] = currentNumber;}
}

3.5 性能分析

時間復雜度：

? 在插入排序中，當待排序數組是有序時，是最優的情況，只需當前數跟前一個數比較一下就可以了，這時一共需要比較N- 1次，時間復雜度為O(n)。

? 最壞的情況是待排序數組是逆序的，此時需要比較次數最多，總次數記為：1+2+3+…+N-1，所以，插入排序最壞情況下的時間復雜度為O(n^2)。

? 平均來說，A[1…j-1]中的一半元素小于A[j]，一半元素大于A[j]，插入排序在平均情況運行時間與最壞情況運行時間一樣，是輸入規模的二次函數，時間復雜度為O(n^2) 。

空間復雜度：

? 由于插入排序是就地排序的，沒有用到單獨的空間，插入排序的空間復雜度為常數階：O(1)。

穩定性：

? 如果待排序的序列中存在兩個或兩個以上具有相同關鍵詞的數據，排序后這些數據的相對次序保持不變，即它們的位置保持不變，通俗地講，就是兩個相同的數的相對順序不會發生改變，則該算法是穩定的；如果排序后，數據的相對次序發生了變化，則該算法是不穩定的。關鍵詞相同的數據元素將保持原有位置不變，所以該算法是穩定的 。

3.6 應用分析

• 插入排序適用于已經有部分數據已經排好，并且排好的部分越大越好。一般在輸入規模大于1000的場合下不建議使用插入排序。
• 比冒泡排序的效率高，冒泡排序需要兩兩比較兩兩交換，時間基本快一倍。
• 比選擇排序快一點，因為如果前面的數組基本有序，平均上比較一半就找到位置，選擇排序總要從頭到尾找一遍。

4.快速排序（Quick Sort）

它的時間復雜度也是 O(nlogn)O(nlogn)，但它在時間復雜度為 O(nlogn)O(nlogn) 級的幾種排序算法中，大多數情況下效率更高，所以快速排序的應用非常廣泛。再加上快速排序所采用的分治思想非常實用，使得快速排序深受面試官的青睞，所以掌握快速排序的思想尤為重要。

4.1算法描述

快速排序算法的基本思想是：

• 從數組中取出一個數，稱之為基數（pivot）
• 遍歷數組，將比基數大的數字放到它的右邊，比基數小的數字放到它的左邊。遍歷完成后，數組被分成了左右兩個區域
• 將左右兩個區域視為兩個數組，重復前兩個步驟，直到排序完成

4.2 圖解演示

4.3 代碼實現

①快速排序遞歸框架

根據我們分析出的思路，先搭出快速排序的架子：

public static void quickSort(int[] arr) {quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int start, int end) {// 將數組分區，并獲得中間值的下標int middle = partition(arr, start, end);// 對左邊區域快速排序quickSort(arr, start, middle - 1);// 對右邊區域快速排序quickSort(arr, middle + 1, end);
}
public static int partition(int[] arr, int start, int end) {// TODO: 將 arr 從 start 到 end 分區，左邊區域比基數小，右邊區域比基數大，然后返回中間值的下標
}

? partition 意為“劃分”，我們期望 partition 函數做的事情是：將 arr 從 start 到 end 這一區間的值分成兩個區域，左邊區域的每個數都比基數小，右邊區域的每個數都比基數大，然后返回中間值的下標。

? 只要有了這個函數，我們就能寫出快速排序的遞歸函數框架。首先調用 partition 函數得到中間值的下標 middle，然后對左邊區域執行快速排序，也就是遞歸調用 quickSort(arr, start, middle - 1)，再對右邊區域執行快速排序，也就是遞歸調用 quickSort(arr, middle + 1, end)。

現在還有一個問題，何時退出這個遞歸函數呢？

②退出遞歸的邊界條件

? 很容易想到，當某個區域只剩下一個數字的時候，自然不需要排序了，此時退出遞歸函數。實際上還有一種情況，就是某個區域只剩下 0 個數字時，也需要退出遞歸函數。當 middle 等于 start 或者 end 時，就會出現某個區域剩余數字為 0。

? 在遞歸之前，先判斷此區域剩余數字是否為 0 個或者 1 個，當數字至少為 2 個時，才執行這個區域的快速排序。因為我們知道 middle >= start && middle <= end 必然成立，所以判斷剩余區域的數字為 0 個或者 1 個也就是指 start 或 end 與 middle 相等或相差 1。

我們來分析一下這四個判斷條件：

• 當 start == middle 時，相當于 quickSort(arr, start, middle - 1) 中的 start == end + 1

• 當 start == middle - 1 時，相當于 quickSort(arr, start, middle - 1) 中的 start == end

• 當 middle == end 時，相當于 quickSort(arr, middle + 1, end) 中的 start == end + 1

• 當 middle == end -1 時，相當于 quickSort(arr, middle + 1, end) 中的 start == end

  由上文所說的 middle >= start && middle <= end 可以推出，除了start == end || start == end + 1這兩個條件之外，其他的情況下 start 都小于 end。我們需要知道，這里的 start >= end 實際上只有兩種情況：

• start == end: 表明區域內只有一個數字

• start == end + 1: 表明區域內一個數字也沒有
  不會存在 start 比 end 大 2 或者大 3 之類的。

所以最終我們可以得出判斷條件為：

public static void quickSort(int[] arr, int start, int end) {// 如果區域內的數字少于 2 個，退出遞歸if (start >= end) return;// 將數組分區，并獲得中間值的下標int middle = partition(arr, start, end);// 對左邊區域快速排序quickSort(arr, start, middle - 1);// 對右邊區域快速排序quickSort(arr, middle + 1, end);
}

③基數的選擇

基數的選擇沒有固定標準，隨意選擇區間內任何一個數字做基數都可以。通常來講有三種選擇方式：

• 選擇第一個元素作為基數
• 選擇最后一個元素作為基數
• 選擇區間內一個隨機元素作為基數

選擇的基數不同，算法的實現也不同。實際上第三種選擇方式的平均時間復雜度是最優的。

? 為什么說隨機選擇剩余數組中的一個元素作為基數的方案平均復雜度是最優的呢？要理清這個問題，我們先來看一下什么情況下快速排序算法的時間復雜度最高，一共有兩種情況：數組為正序、數組為逆序，理想中的快速排序在第 k 輪遍歷中，可以排好 2^{k-1}個基數。當數組原本為正序或逆序時，我們將第一個數作為基數的話，每輪分區后，都有一個區域是空的，也就是說數組中剩下的數字都被分到了同一個區域！這就導致了每一輪遍歷只能排好一個基數。所以總的比較次數為 (n - 1) + (n - 2) + (n - 3) + … + 1 次，由等差數列求和公式可以計算出總的比較次數為 n(n - 1)/2 次，此時快速排序的時間復雜度達到了 O(n^2)級。

選擇第一個元素作為基數：

// 將 arr 從 start 到 end 分區，左邊區域比基數小，右邊區域比基數大，然后返回中間值的下標
public static int partition(int[] arr, int start, int end) {// 取第一個數為基數int pivot = arr[start];// 從第二個數開始分區int left = start + 1;// 右邊界int right = end;
}

④分區算法實現

? 快速排序中最重要的便是分區算法，也就是 partition 函數。partition 函數需要做的事情就是將 arr 從 start 到 end 分區，左邊區域比基數小，右邊區域比基數大，然后返回中間值的下標。那么首先我們要做的事情就是選擇一個基數，基數我們一般稱之為 pivot，意為“軸”。整個數組就像圍繞這個軸進行旋轉，小于軸的數字旋轉到左邊，大于軸的數字旋轉到右邊。

⑤最簡單的分區算法

? 分區的方式也有很多種，最簡單的思路是：從 left 開始，遇到比基數大的數，就交換到數組最后，并將 right 減一，直到 left 和 right 相遇，此時數組就被分成了左右兩個區域。再將基數和中間的數交換，返回中間值的下標即可。

public static void quickSort(int[] arr) {quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int start, int end) {// 如果區域內的數字少于 2 個，退出遞歸if (start >= end) return;// 將數組分區，并獲得中間值的下標int middle = partition(arr, start, end);// 對左邊區域快速排序quickSort(arr, start, middle - 1);// 對右邊區域快速排序quickSort(arr, middle + 1, end);
}
// 將 arr 從 start 到 end 分區，左邊區域比基數小，右邊區域比基數大，然后返回中間值的下標
public static int partition(int[] arr, int start, int end) {// 取第一個數為基數int pivot = arr[start];// 從第二個數開始分區int left = start + 1;// 右邊界int right = end;// left、right 相遇時退出循環while (left < right) {// 找到第一個大于基數的位置while (left < right && arr[left] <= pivot) left++;// 交換這兩個數，使得左邊分區都小于或等于基數，右邊分區大于或等于基數if (left != right) {exchange(arr, left, right);right--;}}// 如果 left 和 right 相等，單獨比較 arr[right] 和 pivotif (left == right && arr[right] > pivot) right--;// 將基數和中間數交換if (right != start) exchange(arr, start, right);// 返回中間值的下標return right;
}
private static void exchange(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

? 因為我們選擇了數組的第一個元素作為基數，并且分完區后，會執行將基數和中間值交換的操作，這就意味著交換后的中間值會被分到左邊區域。所以我們需要保證中間值的下標是分區完成后，最后一個比基數小的值，這里我們用 right 來記錄這個值。

? 這段代碼有一個細節。首先，在交換 left 和 right 之前，我們判斷了 left != right，這是因為如果剩余的數組都比基數小，則 left 會加到 right 才停止，這時不應該發生交換。因為 right 已經指向了最后一個比基數小的值。

? 但這里的攔截可能會攔截到一種錯誤情況，如果剩余的數組只有最后一個數比基數大，left 仍然加到 right 停止了，但我們并沒有發生交換。所以我們在退出循環后，單獨比較了 arr[right] 和 pivot。

實際上，這行單獨比較的代碼非常巧妙，一共處理了三種情況：

• 一是剛才提到的剩余數組中只有最后一個數比基數大的情況
• 二是 left 和 right 區間內只有一個值，則初始狀態下， left == right，所以 while (left < right) 根本不會進入，所以此時我們單獨比較這個值和基數的大小關系
• 三是剩余數組中每個數都比基數大，此時 right 會持續減小，直到和 left 相等退出循環，此時 left 所在位置的值還沒有和 pivot 進行比較，所以我們單獨比較 left 所在位置的值和基數的大小關系

⑥雙指針分區算法

? 除了上述的分區算法外，還有一種雙指針的分區算法更為常用：從 left 開始，遇到比基數大的數，記錄其下標；再從 right 往前遍歷，找到第一個比基數小的數，記錄其下標；然后交換這兩個數。繼續遍歷，直到 left 和 right 相遇。然后就和剛才的算法一樣了，交換基數和中間值，并返回中間值的下標。

public static void quickSort(int[] arr) {quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int start, int end) {// 如果區域內的數字少于 2 個，退出遞歸if (start >= end) return;// 將數組分區，并獲得中間值的下標int middle = partition(arr, start, end);// 對左邊區域快速排序quickSort(arr, start, middle - 1);// 對右邊區域快速排序quickSort(arr, middle + 1, end);
}
// 將 arr 從 start 到 end 分區，左邊區域比基數小，右邊區域比基數大，然后返回中間值的下標
public static int partition(int[] arr, int start, int end) {// 取第一個數為基數int pivot = arr[start];// 從第二個數開始分區int left = start + 1;// 右邊界int right = end;while (left < right) {// 找到第一個大于基數的位置while (left < right && arr[left] <= pivot) left++;// 找到第一個小于基數的位置while (left < right && arr[right] >= pivot) right--;// 交換這兩個數，使得左邊分區都小于或等于基數，右邊分區大于或等于基數if (left < right) {exchange(arr, left, right);left++;right--;}}// 如果 left 和 right 相等，單獨比較 arr[right] 和 pivotif (left == right && arr[right] > pivot) right--;// 將基數和軸交換exchange(arr, start, right);return right;
}
private static void exchange(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

同樣地，我們需要在退出循環后，單獨比較 left 和 right 的值。

4.4 性能分析

時間復雜度：

快速排序的每一次遍歷，都將基數擺到了最終位置上。第一輪遍歷排好 1 個基數，第二輪遍歷排好 2 個基數（每個區域一個基數，但如果某個區域為空，則此輪只能排好一個基數），第三輪遍歷排好 4 個基數（同理，最差的情況下，只能排好一個基數），以此類推。總遍歷次數為 logn～n 次，每輪遍歷的時間復雜度為 O(n)，所以很容易分析出快速排序的時間復雜度為 O(nlogn)～ O(n^2)，平均時間復雜度為 O(nlogn)，最壞的時間復雜度為 O(n^2)，

空間復雜度：

? 空間復雜度與遞歸的層數有關，每層遞歸會生成一些臨時變量，所以空間復雜度為 O(logn) ~ O(n)，平均空間復雜度為 O(logn)。

穩定性：

? 從代碼實現中可以分析出，快速排序是一種不穩定的排序算法，在分區過程中，相同數字的相對順序可能會被修改。

4.5快速排序的優化思路

如何解決這樣的問題呢？其實思路也很簡單，只要我們每輪選擇的基數不是剩余數組中最大或最小的值就可以了。具體方案有很多種，其中較常用的有三種：

• 第一種就是我們在前文中提到的，每輪選擇基數時，從剩余的數組中隨機選擇一個數字作為基數。這樣每輪都選到最大或最小值的概率就會變得很低了。所以我們才說用這種方式選擇基數，其平均時間復雜度是最優的

• 第二種解決方案是在排序之前，先用洗牌算法將數組的原有順序打亂，以防止原數組正序或逆序。

• 第三種就是既然數組重復排序的情況如此常見，那么我們可以在快速排序之前先對數組做個判斷，如果已經有序則直接返回，如果是逆序則直接倒序即可。在 Java 內部封裝的 Arrays.sort() 的源碼中就采用了此解決方案。

5.希爾排序（Shell Sort）

希爾排序和冒泡、選擇、插入等排序算法一樣，逐漸被快速排序所淘汰，但作為承上啟下的算法，不可否認的是，希爾排序身上始終閃耀著算法之美。希爾排序本質上是對插入排序的一種優化，它利用了插入排序的簡單，又克服了插入排序每次只交換相鄰兩個元素的缺點。

5.1 算法描述

它的基本思想是：

• 將待排序數組按照一定的間隔分為多個子數組，每組分別進行插入排序。這里按照間隔分組指的不是取連續的一段數組，而是每跳躍一定間隔取一個值組成一組
• 逐漸縮小間隔進行下一輪排序
• 最后一輪時，取間隔為 11，也就相當于直接使用插入排序。但這時經過前面的「宏觀調控」，數組已經基本有序了，所以此時的插入排序只需進行少量交換便可完成

每一遍排序的間隔在希爾排序中被稱之為增量，所有的增量組成的序列稱之為增量序列，也就是本例中的。增量依次遞減，最后一個增量必須為 1，所以希爾排序又被稱之為「縮小增量排序」。要是以專業術語來描述希爾排序，可以分為以下兩個步驟：

• 定義增量序列 D_m > D_{m-1} > D_{m-2} > … > D_1 = 1
• 對每個D_k進行「D_k間隔排序」

有一條非常重要的性質保證了希爾排序的效率：

「D_{k+1}間隔」有序的序列，在經過「D_k間隔排序」排序后，仍然是有序的增量序列的選擇會極大地影響希爾排序的效率。

5.2 圖解演示

5.3 代碼實現

代碼實現如下：

public static void shellSort(int[] arr) {// 間隔序列，在希爾排序中我們稱之為增量序列for (int gap = arr.length / 2; gap > 0; gap /= 2) {// 分組for (int groupStartIndex = 0; groupStartIndex < gap; groupStartIndex++) {// 插入排序for (int currentIndex = groupStartIndex + gap; currentIndex < arr.length; currentIndex += gap) {// currentNumber 站起來，開始找位置int currentNumber = arr[currentIndex];int preIndex = currentIndex - gap;while (preIndex >= groupStartIndex && currentNumber < arr[preIndex]) {// 向后挪位置arr[preIndex + gap] = arr[preIndex];preIndex -= gap;}// currentNumber 找到了自己的位置，坐下arr[preIndex + gap] = currentNumber;}}}
}

? 這份代碼與我們上文中提到的思路是一模一樣的，先分組，再對每組進行插入排序。同樣地，這里的插入排序也可以采用交換元素的方式。

5.4 優化過程

? 實際上，這段代碼可以優化一下。我們現在的處理方式是：處理完一組間隔序列后，再回來處理下一組間隔序列，這非常符合人類思維。但對于計算機來說，它更喜歡從第 gap 個元素開始，按照順序將每個元素依次向前插入自己所在的組這種方式。雖然這個過程看起來是在不同的間隔序列中不斷跳躍，但站在計算機的角度，它是在訪問一段連續數組。

代碼實現如下：

public static void shellSort(int[] arr) {// 間隔序列，在希爾排序中我們稱之為增量序列for (int gap = arr.length / 2; gap > 0; gap /= 2) {// 從 gap 開始，按照順序將每個元素依次向前插入自己所在的組for (int i = gap; i < arr.length; i++) {// currentNumber 站起來，開始找位置int currentNumber = arr[i];// 該組前一個數字的索引int preIndex = i - gap;while (preIndex >= 0 && currentNumber < arr[preIndex]) {// 向后挪位置arr[preIndex + gap] = arr[preIndex];preIndex -= gap;}// currentNumber 找到了自己的位置，坐下arr[preIndex + gap] = currentNumber;}}
}

5.5增量序列

? 增量序列的選擇會極大地影響希爾排序的效率。增量序列如果選得不好，希爾排序的效率可能比插入排序效率還要低，舉個例子：

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-VhSU36io-1620379072803)(C:\Users\86178\AppData\Roaming\Typora\typora-user-images\image-20210504124048637.png)]

在這個例子中，我們發現，原數組 8 間隔、4 間隔、2 間隔都已經有序了，使用希爾排序時，真正起作用的只有最后一輪 1 間隔排序，也就是直接插入排序。希爾排序反而比直接使用插入排序多執行了許多無用的邏輯。于是人們發現：增量元素不互質，則小增量可能根本不起作用。

事實上，希爾排序的增量序列如何選擇是一個數學界的難題，但它也是希爾排序算法的核心優化點。Knuth 增量序列：D_1 = 1; D_{k+1} = 3 * D_k + 1也就是1,4,13,40,…，數學界猜想它的平均時間復雜度為 O(n^{3/2})；

以 Knuth 增量序列為例，使用 Knuth 序列進行希爾排序的代碼如下：

public static void shellSortByKnuth(int[] arr) {// 找到當前數組需要用到的 Knuth 序列中的最大值int maxKnuthNumber = 1;while (maxKnuthNumber <= arr.length / 3) {maxKnuthNumber = maxKnuthNumber * 3 + 1;}// 增量按照 Knuth 序列規則依次遞減for (int gap = maxKnuthNumber; gap > 0; gap = (gap - 1) / 3) {// 從 gap 開始，按照順序將每個元素依次向前插入自己所在的組for (int i = gap; i < arr.length; i++) {// currentNumber 站起來，開始找位置int currentNumber = arr[i];// 該組前一個數字的索引int preIndex = i - gap;while (preIndex >= 0 && currentNumber < arr[preIndex]) {// 向后挪位置arr[preIndex + gap] = arr[preIndex];preIndex -= gap;}// currentNumber 找到了自己的位置，坐下arr[preIndex + gap] = currentNumber;}}
}

5.6 性能分析

時間復雜度：

? 增量序列的選擇，Shell排序的執行時間依賴于增量序列。

好的增量序列的共同特征：

• 最后一個增量必須為1；

• 應該盡量避免序列中的值(尤其是相鄰的值)互為倍數的情況。

  有人通過大量的實驗，給出了較好的結果：當n較大時，比較和移動的次數約在n^{1.25到(1.6n)}1.25之間。

  事實上，希爾排序時間復雜度非常難以分析，它的平均復雜度界于 O(n) 到 O(n^2) 之間，普遍認為它最好的時間復雜度為 O(n^{1.3})，

空間復雜度：

? 希爾排序的空間復雜度為 O(1)，只需要常數級的臨時變量。

穩定性：

? 雖然插入排序是穩定的排序算法，但希爾排序是不穩定的。在增量較大時，排序過程可能會破壞原有數組中相同關鍵字的相對次序。

5.7 希爾排序與 O(n^2)級排序算法的本質區別

希爾排序憑什么可以打破時間復雜度 O(n^2)的魔咒呢？它和之前介紹的 O(n^2)級排序算法的本質區別是什么？

只要理解了這一點，我們就能知道為什么希爾排序能夠承上啟下，啟發出之后的一系列 O(n^2)級以下的排序算法，這個問題我們可以用逆序對來理解。

當我們從小到大排序時，在數組中的兩個數字，如果前面一個數字大于后面的數字，則這兩個數字組成一個逆序對。

排序算法本質上就是一個消除逆序對的過程。

對于隨機數組，逆序對的數量是 O(n^2)級的，如果采用「交換相鄰元素」的辦法來消除逆序對，每次最多只能消除一組逆序對，因此必須執行 O(n^2)級的交換次數，這就是為什么冒泡、插入、選擇算法只能到 O(n^2)級的原因。反過來說，基于交換元素的排序算法要想突破 O(n^2)級，必須通過一些比較，交換間隔比較遠的元素，使得一次交換能消除一個以上的逆序對。

希爾排序算法就是通過這種方式，打破了在空間復雜度為 O(1)的情況下，時間復雜度為 O(n^2)的魔咒，此后的快排、堆排等等算法也都是基于這樣的思路實現的。

6.歸并排序（Merge Sort）

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

6.1算法描述

• 把長度為n的輸入序列分成兩個長度為n/2的子序列；
• 對這兩個子序列分別采用歸并排序；
• 將兩個排序好的子序列合并成一個最終的排序序列。

6.2 算法圖解

6.3 代碼實現

6.3.1如何將兩個有序的列表合并成一個有序的列表？

? 在第二個列表向第一個列表逐個插入的過程中，由于第二個列表已經有序，所以后續插入的元素一定不會在前面插入的元素之前。在逐個插入的過程中，每次插入時，只需要從上次插入的位置開始，繼續向后尋找插入位置即可。這樣一來，我們最多只需要將兩個有序數組遍歷一次就可以完成合并。在向數組中不斷插入新數字時，原數組需要不斷騰出位置，這是一個比較復雜的過程，而且這個過程必然導致增加一輪遍歷。有一個替代方案：只要開辟一個長度等同于兩個數組長度之和的新數組，并使用兩個指針來遍歷原有的兩個數組，不斷將較小的數字添加到新數組中，并移動對應的指針即可。

代碼實現如下：

// 將兩個有序數組合并為一個有序數組
private static int[] merge(int[] arr1, int[] arr2) {int[] result = new int[arr1.length + arr2.length];int index1 = 0, index2 = 0;while (index1 < arr1.length && index2 < arr2.length) {if (arr1[index1] <= arr2[index2]) {result[index1 + index2] = arr1[index1++];//index1++;} else {result[index1 + index2] = arr2[index2++];//index2++;}}// 將剩余數字補到結果數組之后while (index1 < arr1.length) {result[index1 + index2] = arr1[index1++];//index1++;}while (index2 < arr2.length) {result[index1 + index2] = arr2[index2++];//index2++;}return result;
}

6.3.2將數組拆分成有序數組

拆分過程使用了二分的思想，這是一個遞歸的過程，歸并排序使用的遞歸框架如下：

6.3.3歸并排序的優化：減少臨時空間的開辟

為了減少在遞歸過程中不斷開辟空間的問題，我們可以在歸并排序之前，先開辟出一個臨時空間，在遞歸過程中統一使用此空間進行歸并即可。

public static void mergeSort(int[] arr) {if (arr.length == 0) return;int[] result = new int[arr.length];mergeSort(arr, 0, arr.length - 1, result);
}// 對 arr 的 [start, end] 區間歸并排序
private static void mergeSort(int[] arr, int start, int end, int[] result) {// 只剩下一個數字，停止拆分if (start == end) return;int middle = (start + end) / 2;// 拆分左邊區域，并將歸并排序的結果保存到 result 的 [start, middle] 區間mergeSort(arr, start, middle, result);// 拆分右邊區域，并將歸并排序的結果保存到 result 的 [middle + 1, end] 區間mergeSort(arr, middle + 1, end, result);// 合并左右區域到 result 的 [start, end] 區間merge(arr, start, end, result);
}// 將 result 的 [start, middle] 和 [middle + 1, end] 區間合并
private static void merge(int[] arr, int start, int end, int[] result) {int end1 = (start + end) / 2;int start2 = end1 + 1;// 用來遍歷數組的指針int index1 = start;int index2 = start2;while (index1 <= end1 && index2 <= end) {if (arr[index1] <= arr[index2]) {result[index1 + index2 - start2] = arr[index1++];} else {result[index1 + index2 - start2] = arr[index2++];}}// 將剩余數字補到結果數組之后while (index1 <= end1) {result[index1 + index2 - start2] = arr[index1++];}while (index2 <= end) {result[index1 + index2 - start2] = arr[index2++];}// 將 result 操作區間的數字拷貝到 arr 數組中，以便下次比較while (start <= end) {arr[start] = result[start++];}
}

? 其中， mergeSort(int[] arr) 函數是對外暴露的公共方法，內部調用了私有的mergeSort(int[] arr, int start, int end) 函數，這個函數用于對 arr 的 [start, end] 區間進行歸并排序。

? 可以看到，我們在這個函數中，將原有數組不斷地二分，直到只剩下最后一個數字。此時嵌套的遞歸開始返回，一層層地調用merge(int[] arr1, int[] arr2)函數，也就是我們剛才寫的將兩個有序數組合并為一個有序數組的函數。

? 這就是最經典的歸并排序，只需要一個二分拆數組的遞歸函數和一個合并兩個有序列表的函數即可。

? 我們統一使用 result 數組作為遞歸過程中的臨時數組，所以merge 函數接收的參數不再是兩個數組，而是 result 數組中需要合并的兩個數組的首尾下標。根據首尾下標可以分別計算出兩個有序數組的首尾下標 start1、end1、start2、end2，之后的過程就和之前合并兩個有序數組的代碼類似了。

6.3.4原地歸并排序？

? 現在的歸并排序看起來仍"美中不足"，那就是仍然需要開辟額外的空間，能不能實現不開辟額外空間的歸并排序呢？好像是可以做到的。在一些文章中，將這樣的歸并排序稱之為 In-Place Merge Sort，直譯為原地歸并排序。

public static void mergeSort(int[] arr) {if (arr.length == 0) return;mergeSort(arr, 0, arr.length - 1);
}// 對 arr 的 [start, end] 區間歸并排序
private static void mergeSort(int[] arr, int start, int end) {// 只剩下一個數字，停止拆分if (start == end) return;int middle = (start + end) / 2;// 拆分左邊區域mergeSort(arr, start, middle);// 拆分右邊區域mergeSort(arr, middle + 1, end);// 合并左右區域merge(arr, start, end);
}// 將 arr 的 [start, middle] 和 [middle + 1, end] 區間合并
private static void merge(int[] arr, int start, int end) {int end1 = (start + end) / 2;int start2 = end1 + 1;// 用來遍歷數組的指針int index1 = start;int index2 = start2;while (index1 <= end1 && index2 <= end) {if (arr[index1] <= arr[index2]) {index1++;} else {// 右邊區域的這個數字比左邊區域的數字小，于是它站了起來int value = arr[index2];int index = index2;// 前面的數字不斷地后移while (index > index1) {arr[index] = arr[index - 1];index--;}// 這個數字坐到 index1 所在的位置上arr[index] = value;// 更新所有下標，使其前進一格index1++;index2++;end1++;}}
}
/*
這段代碼在合并 arr 的 [start, middle] 區間和 [middle + 1, end] 區間時，將兩個區間較小的數字移動到 index1 的位置，并且將左邊區域不斷后移，目的是給新插入的數字騰出位置。最后更新兩個區間的下標，繼續合并更新后的區間。
*/

? 分析代碼可以看出，這樣實現的歸并本質上是插入排序！前文已經說到，在插入排序中，騰出位置是一個比較復雜的過程，而且這個過程必然導致增加一輪遍歷。在這兩份代碼中，每一次合并數組時，都使用了兩層循環，目的就是不斷騰挪位置以插入新數字，可以看出這里合并的效率是非常低的。這兩種排序算法的時間復雜度都達到了 O(n^2)級，不能稱之為歸并排序。它們只是借用了歸并排序的遞歸框架而已。

? 也就是說，所謂的原地歸并排序事實上并不存在，許多算法書籍中都沒有收錄這種算法。它打著歸并排序的幌子，賣的是插入排序的思想，實際排序效率比歸并排序低得多。

6.4 性能分析

時間復雜度：

歸并排序的復雜度比較容易分析，拆分數組的過程中，會將數組拆分 logn 次，每層執行的比較次數都約等于 n 次，所以時間復雜度是 O(nlogn)。

空間復雜度：

空間復雜度是 O(n)，主要占用空間的就是我們在排序前創建的長度為n的result數組。

穩定性：

? 分析歸并的過程可知，歸并排序是一種穩定的排序算法。其中，對算法穩定性非常重要的一行代碼是：

if (arr[index1] <= arr[index2]) {
result[index1 + index2 - start2] = arr[index1++];
}
在這里我們通過arr[index1] <= arr[index2]來合并兩個有序數組，保證了原數組中，相同的元素相對順序不會變化，如果這里的比較條件寫成了arr[index1] < arr[index2]，則歸并排序將變得不穩定。

6.5 應用分析

? 總結起來，歸并排序分成兩步，一是拆分數組，二是合并數組，它是分治思想的典型應用。分治的意思是“分而治之”，分的時候體現了二分的思想，治是一個滾雪球的過程，將 1 個數字組成的有序數組合并成一個包含 2 個數字的有序數組，再將 2 個數字組成的有序數組合并成包含 4 個數字的有序數組…

? 由于性能較好，且排序穩定，歸并排序應用非常廣泛，Arrays.sort() 源碼中的 TimSort就是歸并排序的優化版。

7.堆排序（Heap Sort）

? 數組、鏈表都是一維的數據結構，相對來說比較容易理解，而堆是二維的數據結構，對抽象思維的要求更高，所以許多程序員「談堆色變」。但堆又是數據結構進階必經的一步，我們不妨靜下心來，將其梳理清楚。

堆：符合以下兩個條件之一的完全二叉樹：

根節點的值 ≥ 子節點的值，這樣的堆被稱之為最大堆，或大頂堆；

根節點的值 ≤ 子節點的值，這樣的堆被稱之為最小堆，或小頂堆。

7.1算法描述

堆排序過程如下：

• 用數列構建出一個大頂堆，取出堆頂的數字；
• 調整剩余的數字，構建出新的大頂堆，再次取出堆頂的數字；
• 循環往復，完成整個排序。

整體的思路就是這么簡單，我們需要解決的問題有兩個：

• 如何用數列構建出一個大頂堆；

• 取出堆頂的數字后，如何將剩余的數字調整成新的大頂堆。

  構建大頂堆 & 調整堆
  構建大頂堆有兩種方式：

  方案一：從 0 開始，將每個數字依次插入堆中，一邊插入，一邊調整堆的結構，使其滿足大頂堆的要求；
  方案二：將整個數列的初始狀態視作一棵完全二叉樹，自底向上調整樹的結構，使其滿足大頂堆的要求。
  方案二更為常用，動圖演示如下：

  7.2圖解演示

  

在介紹堆排序具體實現之前，我們先要了解完全二叉樹的幾個性質。將根節點的下標視為 0，則完全二叉樹有如下性質：

• 對于完全二叉樹中的第 i 個數，它的左子節點下標：left = 2i + 1
• 對于完全二叉樹中的第 i 個數，它的右子節點下標：right = left + 1
• 對于有 n 個元素的完全二叉樹(n≥2)，它的最后一個非葉子結點的下標：n/2 - 1

7.3 代碼實現

堆排序代碼如下：

public static void heapSort(int[] arr) {// 構建初始大頂堆buildMaxHeap(arr);for (int i = arr.length - 1; i > 0; i--) {// 將最大值交換到數組最后swap(arr, 0, i);// 調整剩余數組，使其滿足大頂堆maxHeapify(arr, 0, i);}
}
// 構建初始大頂堆
private static void buildMaxHeap(int[] arr) {// 從最后一個非葉子結點開始調整大頂堆，最后一個非葉子結點的下標就是 arr.length / 2-1for (int i = arr.length / 2 - 1; i >= 0; i--) {maxHeapify(arr, i, arr.length);}
}
// 調整大頂堆，第三個參數表示剩余未排序的數字的數量，也就是剩余堆的大小
private static void maxHeapify(int[] arr, int i, int heapSize) {// 左子結點下標int l = 2 * i + 1;// 右子結點下標int r = l + 1;// 記錄根結點、左子樹結點、右子樹結點三者中的最大值下標int largest = i;// 與左子樹結點比較if (l < heapSize && arr[l] > arr[largest]) {largest = l;}// 與右子樹結點比較if (r < heapSize && arr[r] > arr[largest]) {largest = r;}if (largest != i) {// 將最大值交換為根結點swap(arr, i, largest);// 再次調整交換數字后的大頂堆maxHeapify(arr, largest, heapSize);}
}
private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

? 堆排序的第一步就是構建大頂堆，對應代碼中的 buildMaxHeap 函數。我們將數組視作一顆完全二叉樹，從它的最后一個非葉子結點開始，調整此結點和其左右子樹，使這三個數字構成一個大頂堆。

? 調整過程由 maxHeapify 函數處理， maxHeapify 函數記錄了最大值的下標，根結點和其左右子樹結點在經過比較之后，將最大值交換到根結點位置。這樣，這三個數字就構成了一個大頂堆。

? 需要注意的是，如果根結點和左右子樹結點任何一個數字發生了交換，則還需要保證調整后的子樹仍然是大頂堆，所以子樹會執行一個遞歸的調整過程。

? 這里的遞歸比較難理解，我們打個比方：構建大頂堆的過程就是一堆數字比賽誰更大。比賽過程分為初賽、復賽、決賽，每場比賽都是三人參加。但不是所有人都會參加初賽，只有葉子結點和第一批非葉子結點會進行三人組初賽。初賽的冠軍站到三人組的根結點位置，然后繼續參加后面的復賽。

? 而有的人生來就在上層，比如李小胖，它出生在數列的第一個位置上，是二叉樹的根結點，當其他結點進行初賽、復賽時，它就靜靜躺在根結點的位置等一場決賽。

? 當王大強和張壯壯，經歷了重重比拼來到了李小胖的左右子樹結點位置。他們三個人開始決賽。王大強和張壯壯是靠實打實的實力打上來的，他們已經確認過自己是小組最強。而李小胖之前一直躺在這里等決賽。如果李小胖贏了他們兩個，說明李小胖是所有小組里最強的，毋庸置疑，他可以繼續坐在冠軍寶座。

? 但李小胖如果輸給了其中任何一個人，比如輸給了王大強。王大強會和張壯壯對決，選出本次構建大頂堆的冠軍。但李小胖能夠坐享其成獲得第三名嗎？生活中或許會有這樣的黑幕，但程序不會欺騙我們。李小胖跌落神壇之后，就要從王大強的打拼路線回去，繼續向下比較，找到自己真正實力所在的真實位置。這就是 maxHeapify 中會繼續遞歸調用 maxHeapify 的原因。

? 當構建出大頂堆之后，就要把冠軍交換到數列最后，深藏功與名。來到冠軍寶座的新人又要和李小胖一樣，開始向下比較，找到自己的真實位置，使得剩下的 n - 1n?1 個數字構建成新的大頂堆。這就是 heapSort 方法的 for 循環中，調用 maxHeapify 的原因。

? 變量 heapSize 用來記錄還剩下多少個數字沒有排序完成，每當交換了一個堆頂的數字，heapSize 就會減 11。在 maxHeapify 方法中，使用 heapSize 來限制剩下的選手，不要和已經躺在數組最后，當過冠軍的人比較，免得被暴揍。

? 這就是堆排序的思想。學習時我們采用的是最簡單的代碼實現，在熟練掌握了之后我們就可以加一些小技巧以獲得更高的效率。比如我們知道計算機采用二進制來存儲數據，數字左移一位表示乘以 22，右移一位表示除以 22。所以堆排序代碼中的arr.length / 2 - 1 可以修改為 (arr.length >> 1) - 1，左子結點下標2 * i + 1可以修改為(i << 1) + 1。需要注意的是，位運算符的優先級比加減運算的優先級低，所以必須給位運算過程加上括號。

7.4 性能分析

時間復雜度：

? 堆排序分為兩個階段：初始化建堆（buildMaxHeap）和重建堆（maxHeapify，直譯為大頂堆化）。所以時間復雜度要從這兩個方面分析。

? 根據數學運算可以推導出初始化建堆的時間復雜度為 O(n)，重建堆的時間復雜度為 O(n\log n)O，所以堆排序總的時間復雜度為 O(n\log n)。推導過程較為復雜，故不再給出證明過程。

空間復雜度：

堆排序的空間復雜度為 O(1)，只需要常數級的臨時變量。堆排序是一個優秀的排序算法，但是在實際應用中，快速排序的性能一般會優于堆排序。

穩定性：

? 堆排序是不穩定的

? 比如：9 18 27 18

? 如果堆頂9先輸出，則第三層的18（最后一個18）跑到堆頂，然后堆穩定，繼續輸出堆頂，是剛才那個18，這樣說明后面的18先于第二個位置的18輸出，所以不穩定。

8.計數排序（Counting Sort）

計數排序是一個非基于比較的排序算法，它的優勢在于在對一定范圍內的整數排序時，它的復雜度為Ο(n+k)（其中k是整數的范圍），快于任何比較排序算法。當然這是一種犧牲空間換取時間的做法，而且當O(k)>O(nlog(n))的時候其效率反而不如基于比較的排序（基于比較的排序的時間復雜度在理論上的下限是O(n*log(n)), 如歸并排序，堆排序）

8.1算法描述

算法思想：

• 找出待排序的數組中最大和最小的元素；
• 統計數組中每個值為i的元素出現的次數，存入數組C的第i項；
• 對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）；
• 反向填充目標數組：將每個元素i放在新數組的第C(i)項，每放一個元素就將C(i)減去1。

8.2 圖解演示

8.3代碼實現

代碼實現如下：

//針對c數組的大小，優化過的計數排序
public class CountSort{publicstaticvoidmain(String[]args){//排序的數組int a[]={100,93,97,92,96,99,92,89,93,97,90,94,92,95};int b[]=countSort(a);for(inti:b){System.out.print(i+"");}System.out.println();}public static int[] countSort(int[]a){int b[] = new int[a.length];int max = a[0],min = a[0];for(int i:a){if(i>max){max=i;}if(i<min){min=i;}}//這里k的大小是要排序的數組中，元素大小的極值差+1int k=max-min+1;int c[]=new int[k];for(int i=0;i<a.length;++i){c[a[i]-min]+=1;//優化過的地方，減小了數組c的大小}for(int i=1;i<c.length;++i){c[i]=c[i]+c[i-1];}for(int i=a.length-1;i>=0;--i){b[--c[a[i]-min]]=a[i];//按存取的方式取出c的元素}return b;}
}

8.4 性能分析

時間復雜度：

? 原數組、count數組、累加數組、目標數組；先對原數組過濾一遍生成count數組，對count數組過濾一遍生成累加數組，最后再把原數組從后往前生成目標數組，原數組過濾兩遍，count數組過濾兩遍，原數組是長度是n，count數組長度是k，即2(n+k)；

? 從計數排序的實現代碼中，可以看到，每次遍歷都是進行 n 次或者 k 次，所以計數排序的時間復雜度為 O(n + k)，k 表示數據的范圍大小。用到的空間主要是長度為 k 的計數數組和長度為 n 的結果數組，所以空間復雜度也是 O(n + k)。

空間復雜度：

? 用了額外的數組長度為n和k，所以空間復雜度為O(n+k)。

穩定性：

? 經計數排序，輸出序列中值相同的元素之間的相對次序與他們在輸入序列中的相對次序相同，換句話說，計數排序算法是一個穩定的排序算法。

8.5 拓展

需要注意的是，一般我們分析時間復雜度和空間復雜度時，常數項都是忽略不計的。但計數排序的常數項可能非常大，以至于我們無法忽略。不知你是否注意到計數排序的一個非常大的隱患，比如我們想要對這個數組排序：

int[] arr = new int[]{1, Integer.MAX_VALUE};

盡管它只包含兩個元素，但數據范圍是 [1, 2^{31}]，我們知道java中int 占4個字節，一個長度為 2^{31}次方的 int 數組大約會占8G的空間。如果使用計數排序，僅僅排序這兩個元素，聲明計數數組就會占用超大的內存，甚至導致 OutOfMemory 異常。

使用于特定問題，對源數據有要求，適合量比較大，數值范圍比較小，例如企業員工年齡排序，快速查詢高考名次，如果需要排序的數字中存在一位小數，可以將所有數字乘以 10，再去計算最終的下標位置。當k不是很大并且序列比較集中時，計數排序是一個很有效的排序算法。

9.基數排序（Radix Sort）

基數排序有兩種實現方式。本例屬于「最高位優先法」，簡稱 MSD (Most significant digital)，思路是從最高位開始，依次對基數進行排序。與之對應的是「最低位優先法」，簡稱 LSD (Least significant digital)。思路是從最低位開始，依次對基數進行排序。使用 LSD 必須保證對基數進行排序的過程是穩定的。

通常來講，LSD 比 MSD 更常用。因為使用的是 MSD，例如在第二步比較兩個以 99 開頭的數字時，其他基數開頭的數字不得不放到一邊。體現在計算機中，這里會產生很多臨時變量。

但在采用 LSD 進行基數排序時，每一輪遍歷都可以將所有數字一視同仁，統一處理。所以 LSD 的基數排序更符合計算機的操作習慣。

9.1 算法描述

基數排序可以分為以下三個步驟：

• 找出數組中最大的數字的位數 maxDigitLength
• 獲取數組中每個數字的基數
• 遍歷 maxDigitLength 輪數組，每輪按照基數對其進行排序

9.2 圖解演示

9.3 代碼實現

9.3.1找出數組中最大的數字的位數

首先找到數組中的最大值：

public static void radixSort(int[] arr) {if (arr == null) return;int max = 0;for (int value : arr) {if (value > max) {max = value;}}// ...
}

通過遍歷一次數組，找到了數組中的最大值 max，然后我們計算這個最大值的位數：

int maxDigitLength = 0;
while (max != 0) {maxDigitLength++;max /= 10;
}

將 maxDigitLength 初始化為 00，然后不斷地除以 10，每除一次，maxDigitLength 就加一，直到 max 為 00。

如果 max 初始值就是 00 呢？嚴格來講，00 在數學上屬于 11 位數。但實際上，基數排序時我們無需考慮 max 為 00 的場景，因為 max 為 00 只有一種可能，那就是數組中所有的數字都為 00，此時數組已經有序，我們無需再進行后續的排序過程。

9.3.2獲取基數：

int dev = 1;
for (int i = 0; i < maxDigitLength; i++) {for (int value : arr) {int radix = value / dev % 10;// 對基數進行排序}dev *= 10;
}

9.3.3對基數進行排序：

因為每一個基數都在 [0, 9] 之間，并且計數排序是一種穩定的算法。

LSD 方式的基數排序代碼如下：

public class RadixSort {public static void radixSort(int[] arr) {if (arr == null) return;// 找出最大值int max = 0;for (int value : arr) {if (value > max) {max = value;}}// 計算最大數字的長度int maxDigitLength = 0;while (max != 0) {maxDigitLength++;max /= 10;}// 使用計數排序算法對基數進行排序int[] counting = new int[10];int[] result = new int[arr.length];int dev = 1;for (int i = 0; i < maxDigitLength; i++) {for (int value : arr) {int radix = value / dev % 10;counting[radix]++;}for (int j = 1; j < counting.length; j++) {counting[j] += counting[j - 1];}// 使用倒序遍歷的方式完成計數排序for (int j = arr.length - 1; j >= 0; j--) {int radix = arr[j] / dev % 10;result[--counting[radix]] = arr[j];}// 計數排序完成后，將結果拷貝回 arr 數組System.arraycopy(result, 0, arr, 0, arr.length);// 將計數數組重置為 0Arrays.fill(counting, 0);dev *= 10;}}
}

當每一輪對基數完成排序后，我們將 result 數組的值拷貝回 arr 數組，并且將 counting 數組中的元素都置為 00，以便在下一輪中復用。

9.4 對包含負數的數組進行基數排序

如果數組中包含負數，如何進行基數排序呢？

? 我們很容易想到一種思路：將數組中的每個元素都加上一個合適的正整數，使其全部變成非負整數，等到排序完成后，再減去之前加的這個數就可以了。

但這種方案有一個缺點：加法運算可能導致數字越界，所以必須單獨處理數字越界的情況。

? 事實上，有一種更好的方案解決負數的基數排序。那就是在對基數進行計數排序時，申請長度為19的計數數組，用來存儲 [-9, 9]這個區間內的所有整數。在把每一位基數計算出來后，加上99，就能對應上 counting 數組的下標了。也就是說，counting數組的下標[0, 18]對應基數 [-9, 9]。

代碼實現如下：

public class RadixSort {public static void radixSort(int[] arr) {if (arr == null) return;// 找出最長的數int max = 0;for (int value : arr) {if (Math.abs(value) > max) {max = Math.abs(value);}}// 計算最長數字的長度int maxDigitLength = 0;while (max != 0) {maxDigitLength++;max /= 10;}// 使用計數排序算法對基數進行排序，下標 [0, 18] 對應基數 [-9, 9]int[] counting = new int[19];int[] result = new int[arr.length];int dev = 1;for (int i = 0; i < maxDigitLength; i++) {for (int value : arr) {// 下標調整int radix = value / dev % 10 + 9;counting[radix]++;}for (int j = 1; j < counting.length; j++) {counting[j] += counting[j - 1];}// 使用倒序遍歷的方式完成計數排序for (int j = arr.length - 1; j >= 0; j--) {// 下標調整int radix = arr[j] / dev % 10 + 9;result[--counting[radix]] = arr[j];}// 計數排序完成后，將結果拷貝回 arr 數組System.arraycopy(result, 0, arr, 0, arr.length);// 將計數數組重置為 0Arrays.fill(counting, 0);dev *= 10;}}
}

代碼中主要做了兩處修改：

• 當數組中存在負數時，我們就不能簡單的計算數組的最大值了，而是要計算數組中絕對值最大的數，也就是數組中最長的數
• 在獲取基數的步驟，將計算出的基數加上9，使其與 counting 數組下標一一對應

9.5 LSD VS MSD

前文介紹的基數排序都屬于 LSD，接下來我們看一下基數排序的 MSD 實現：

public class RadixSort {public static void radixSort(int[] arr) {if (arr == null) return;// 找到最大值int max = 0;for (int value : arr) {if (Math.abs(value) > max) {max = Math.abs(value);}}// 計算最大長度int maxDigitLength = 0;while (max != 0) {maxDigitLength++;max /= 10;}radixSort(arr, 0, arr.length - 1, maxDigitLength);}// 對 arr 數組中的 [start, end] 區間進行基數排序private static void radixSort(int[] arr, int start, int end, int position) {if (start == end || position == 0) return;// 使用計數排序對基數進行排序int[] counting = new int[19];int[] result = new int[end - start + 1];int dev = (int) Math.pow(10, position - 1);for (int i = start; i <= end; i++) {// MSD, 從最高位開始int radix = arr[i] / dev % 10 + 9;counting[radix]++;}for (int j = 1; j < counting.length; j++) {counting[j] += counting[j - 1];}// 拷貝 counting，用于待會的遞歸int[] countingCopy = new int[counting.length];System.arraycopy(counting, 0, countingCopy, 0, counting.length);for (int i = end; i >= start; i--) {int radix = arr[i] / dev % 10 + 9;result[--counting[radix]] = arr[i];}// 計數排序完成后，將結果拷貝回 arr 數組System.arraycopy(result, 0, arr, start, result.length);// 對 [start, end] 區間內的每一位基數進行遞歸排序for (int i = 0; i < counting.length; i++) {radixSort(arr, i == 0 ? start : start + countingCopy[i - 1], start + countingCopy[i] - 1, position - 1);}}}

使用 MSD 時，下一輪排序只應該發生在當前輪次基數相等的數字之間，對每一位基數進行遞歸排序的過程中會產生許多臨時變量。

相比 LSD，MSD 的基數排序顯得較為復雜。因為我們每次對基數進行排序后，無法將所有的結果一視同仁地進行下一輪排序，否則下一輪排序會破壞本次排序的結果。

9.6 性能分析

時間復雜度：

? 無論 LSD 還是 MSD，基數排序時都需要經歷 maxDigitLength 輪遍歷，每輪遍歷的時間復雜度為 O(n + k) ，其中 k 表示每個基數可能的取值范圍大小。如果是對非負整數排序，則 k = 10，如果是對包含負數的數組排序，則 k = 19。所以基數排序的時間復雜度為 O(d(n + k)) (d 表示最長數字的位數，k 表示每個基數可能的取值范圍大小)。

? 每次都復制一遍，一遍的時間復雜度為O(n)，所以時間復雜度為O(n*k)。

空間復雜度：

? 使用的空間和計數排序是一樣的，空間復雜度為 O(n + k)（k 表示每個基數可能的取值范圍大小）。

穩定性：

? 在基數排序過程中，每一次裝桶都是將當前位數上相同數值的元素進行裝桶，并不需要交換位置；所以基數排序是穩定的算法。

如果負數可以使用正負數桶，負數的排負數，正數的排正數，然后就可以達到要求。

10.桶排序（Bucket Sort）

桶排序利用了函數的映射關系，高效與否的關鍵就在于這個映射函數的確定；桶排序 (Bucket sort)的工作的原理：假設輸入數據服從均勻分布，將數據分到有限數量的桶里，每個桶再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排）；桶排序的思想近乎徹底的分治思想；桶排序假設待排序的一組數均勻獨立的分布在一個范圍中，并將這一范圍劃分成幾個子范圍（桶）。

10.1 算法描述

• 設置一個定量的數組當作空桶；
• 遍歷輸入數據，并且把數據一個一個放到對應的桶里去；
• 對每個不是空的桶進行排序；
• 從不是空的桶里把排好序的數據拼接起來，得到結果。

10.2 圖解演示

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-vBv608ur-1620379072809)(C:\Users\86178\AppData\Roaming\Typora\typora-user-images\image-20210506215159979.png)]

10.3 代碼實現

代碼實現：

public static double[] bucketSort(double[] array){//得到數列的最大值和最小值，并計算出差值ddouble max=array[0];double min=array[0];for (int i=1;i<array.length;i++){if (array[i]>max){max=array[i];}if (array[i]<min){min=array[i];}}double d=max-min;//初始化桶int bucketNum=array.length;ArrayList<LinkedList<Double>> bucketList=new ArrayList<LinkedList<Double>>(bucketNum);for (int i=0;i<bucketNum;i++){bucketList.add(new LinkedList<Double>());}//遍歷原始數組將每個元素放入桶中for (int i=0;i<array.length;i++){int num=(int)((array[i]-min)*(bucketNum-1)/d);bucketList.get(num).add(array[i]);}//對每個桶內部進行排序for(int i=0;i<bucketList.size();i++){// 使用Collections.sort，其底層實現基于歸并排序或歸并排序的優化版本Collections.sort(bucketList.get(i));}//輸出全部元素double[] sortedArray=new double[array.length];int index=0;for (LinkedList<Double> list:bucketList) {for (double element:list){sortedArray[index]=element;index++;}}return sortedArray;}

10.4 性能分析

時間復雜度（這部分內容不太重要，增加學習負擔）：

? 桶排序利用函數的映射關系，減少了幾乎所有的比較工作。實際上，桶排序的f(k)值的計算，其作用就相當于快排中劃分，已經把大量數據分割成了基本有序的數據塊(桶)。然后只需要對桶中的少量數據做先進的比較排序即可。

? 對N個關鍵字進行桶排序的時間復雜度分為兩個部分：

• 循環計算每個關鍵字的桶映射函數，這個時間復雜度是O(n)。

• 利用先進的比較排序算法對每個桶內的所有數據進行排序，其時間復雜度為 ∑ O(Ni*logNi) 。其中Ni 為第i個桶的數據量。

  很顯然，第二部分是桶排序性能好壞的決定因素。盡量減少桶內數據的數量是提高效率的唯一辦法(因為基于比較排序的最好平均時間復雜度只能達到O(n*logn)了)。因此，我們需要盡量做到下面兩點：

• 映射函數f(k)能夠將n個數據平均的分配到m個桶中，這樣每個桶就有[n/m]個數據量。

• 在額外空間充足的情況下，盡量增大桶的數量，使用的映射函數能夠將輸入的 n個數據均勻的分配到 m個桶中。極限情況下每個桶只能得到一個數據，這樣就完全避開了桶內數據的“比較”排序操作。 當然，做到這一點很不容易，數據量巨大的情況下，f(k)函數會使得桶集合的數量巨大，空間浪費嚴重。這就是一個時間代價和空間代價的權衡問題了。

? 對于n個待排數據，m個桶，平均每個桶[n/m]個數據的桶排序平均時間復雜度為： O(n)+O(m(n/m)log(n/m))=O(n+n(logn-logm))=O(n+nlogn-nlogm)

• 當n=m時，即極限情況下每個桶只有一個數據時。桶排序的最好效率能夠達到O(n)。
• 最糟糕的情況下，即所有的數據都放入了一個桶內，桶內自排序算法為插入排序，那么其時間復雜度就為 O(n^2) 了。

空間復雜度：

? 當然桶排序的空間復雜度 為O(N+M)，如果輸入數據非常龐大，而桶的數量也非常多，則空間代價無疑是昂貴的。

穩定性：

? 桶排序是穩定的。

10.5 拓展

? 其次，我們可以發現，區間劃分的越細，即桶的數量越多，理論上分到每個桶中的元素就越少，桶內數據的排序就越簡單，其時間復雜度就越接近于線性。

? 極端情況下，就是區間小到只有1，即桶內只存放一種元素，桶內的元素不再需要排序，因為它們都是相同的元素，這時桶排序差不多就和計數排序一樣了。

? 總結： 桶排序的平均時間復雜度為線性的O(n+C)，其中C=n*(logn-logm)。如果相對于同樣的n，桶數量m越大，其效率越高，最好的時間復雜度達到O(n)。 桶排序的空間復雜度 為O(n+m)，如果輸入數據非常龐大，而桶的數量也非常多，則空間代價無疑是昂貴的。此外，桶排序是穩定的。

11.非比較類排序算法總結

這三種排序算法都利用了桶的概念，但對桶的使用方法上有明顯差異：

• 基數排序：根據鍵值的每位數字來分配桶；
• 計數排序：每個桶只存儲單一鍵值；
• 桶排序：每個桶存儲一定范圍的數值；

---

部分動圖參考：https://www.cnblogs.com/onepixel/articles/7674659.html
部分優化參考：https://leetcode-cn.com/leetbook/detail/sort-algorithms/

---