06排序 + 查找（D1_排序（D1

學習預熱：基礎知識

一、什么是排序

二、為什么要排序

三、排序的穩定性

四、排序穩定性的意義

五、排序分類方式

方式一：內外分類

方式二：比較分類

六、排序算法性能評估

1. 算法的時間復雜度

2. 算法的空間復雜度

七、知識小結

1. 10種經典排序算法表格圖

2. 排序算法選擇

2.1. 穩定性比較

2.2. 平均時間復雜度

2.3. 排序算法的選擇

1> 數據規模較小（9W內）

2> 數據規模很大

3> 基數排序（穩定）

4> 希爾排序（不穩定）

------------------------------------

排序算法一：冒泡排序

一、簡介

二、示例代碼

三、變種

1. 雞尾酒排序

1.1. 簡介

1.2. 代碼

1.3. 復雜度

2. 短冒泡排序

2.1. 簡介

2.2. 代碼

3. 奇偶排序

3.1. 簡介

3.2. 題目

3.3. 代碼

3.3.1. 方法一：兩次遍歷

3.3.2. 方法二：雙指針 + 一次遍歷

3.3.3. 方法三：原地交換

四、應用場景

五、框架應用

1. 冒泡排序在spring 中的應用

六、算法分析

------------------------------------

排序算法二：選擇排序

一、基本介紹

二、示例代碼

方式一：原始版

方式二：遞歸版

方式三：優化版

方式四：優化遞歸版

三、變種

四、應用場景

五、框架應用

1. 選擇排序在spring 中的應用

六、算法分析

------------------------------------

排序算法三：插入排序

一、基本介紹

二、示例代碼

方法一：交換法

方法二：插入法

三、變種

1. 直接插入排序

1.1. 簡介

1.2. 代碼

1.3. 算法分析

2. 折半插入排序

2.1. 簡介

2.2. 代碼

2.3. 算法分析

3. 希爾排序（Donald.L.Shell）

3.1. 簡介

3.2. 代碼

四、應用場景

五、框架應用

六、算法分析

------------------------------------

第二個步驟，堆排序

三、完整代碼

四、應用場景

五、框架應用

六、算法分析

------------------------------------

排序算法六：快速排序

一、基本介紹

二、示例代碼

三、快排變種

1. 基于小于區的遞歸版本的快排

2. 荷蘭國旗問題的遞歸版本的快排

2.1. 什么是荷蘭國旗問題

2.2. 荷蘭國旗問題的抽象

2.3. 解決的思路

2.4. 代碼實現

3. 遞歸版本的隨機快排

4. 非遞歸版本的隨機快排

四、應用場景

五、框架應用

六、算法分析

------------------------------------

排序算法七：拓撲排序

參考文獻

------------------------------------

排序算法八：不基于比較的排序(3種)

前置知識

一、桶排序

1. 什么是桶排序

2. 算法思想

3. 案例分析

4. 代碼實現

5. 算法分析

二、計數排序

1. 什么是計數排序

2. 算法步驟

3. maven依賴

4. 流程解析

4.1. 計數流程圖

4.2. 計數數組變形

4.3. 排序過程

4.4. 代碼實現

三、基數排序

1. 什么是基數排序

2. 計數排序 vs 桶排序 vs 基數排序

3. 算法步驟

4. maven依賴

5. 流程解析

5.1. 個位數排序

5.2. 十位數排序

5.3. 百位數排序

6. 代碼實現

學習預熱：基礎知識

一、什么是排序

所謂排序，就是整理表中的數據元素，使之按元素的關鍵字遞增/遞減的順序排列。

二、為什么要排序

查找是計算機應用中必不可少并且使用頻率很高的一個操作。

在一個排序表中查找一個元素，要比在一個無序表中查找效率高得多。

所以為了提高查找效率，節省CPU時間，需要排序。

三、排序的穩定性

穩定性：穩定性指的是相同兩個數，排序后他們的相對順序不變。

什么時候需要穩定的排序方法？什么時候不需要呢？

待更新. . .

四、排序穩定性的意義

待更新. . .

五、排序分類方式

方式一：內外分類

我們根據待排序的數據元素是否全部在內存中，我們把排序方法，分為兩類：

內排序：整個排序元素都在內存中處理，不涉及內、外存的數據交換。

外排序：待排序元素有一部分不在內存（如：內存裝不下）

方式二：比較分類

比較類排序：通過比較來決定元素間的相對次序，由于其時間復雜度不能突破O(nlogn)，因此也稱為非線性時間比較類排序。
非比較類排序：不通過比較來決定元素間的相對次序，它可以突破基于比較排序的時間下界，以線性時間運行，因此也稱為線性時間非比較類排序。

待畫結構圖：非比較排序和比較排序!

六、排序算法性能評估

1. 算法的時間復雜度

評估一下算法運行時間

待更新. . .

2. 算法的空間復雜度

評估一下算法所用空間

七、知識小結

1. 10種經典排序算法表格圖

待更新：各排序算法的描述

2. 排序算法選擇

2.1. 穩定性比較

（1）穩定：冒泡排序、插入排序、二分插入排序、歸并排序和基數排序。

（2）不穩定：選擇排序、快速排序、希爾排序、堆排序。

2.2. 平均時間復雜度

（1）O(n^2)：直接插入排序，簡單選擇排序，冒泡排序、二分插入排序。

（2）O(nlogn)：快速排序，歸并排序，希爾排序，堆排序。快排是最好的，其次是歸并和希爾，

堆排序在數據量很大時效果明顯。

（3）在數據規模較小時（9W內）：直接插入排序，簡單選擇排序差不多。當數據較大時：冒泡排

序算法的時間代價最高。

性能為O(n^2)的算法基本上是相鄰元素進行比較，基本上都是穩定的。

2.3. 排序算法的選擇

1> 數據規模較小（9W內）

（1）直接插入排序、冒泡排序：待排序列基本有序的情況下，對穩定性有要求；

（2）直接選擇排序：待排序列無序，對穩定性不作要求；

2> 數據規模很大

（1）歸并排序：序列本身基本有序，對穩定性有要求，空間允許下。

（2）快速排序：序列本身無序。完全可以用內存空間，對穩定性沒有要求，此時要付出log(n)的額外空

間。

（3）堆排序：對穩定性沒有要求，所需的輔助空間少于快速排序，

3> 基數排序（穩定）

（1）在某個數字可能很大的時候，基數排序沒有任何性能上的優勢，還會浪費非常多的內存。

（2）一組數，這組數的最大值不是很大，更加準確的說，是要排序的對象的數目和排序對象的最大值之

間相差不多。比如，這組數 1 4 5 2 2，要排序對象的數目是 5 ，排序對象的最大值也是 5. 這樣的情況

很適合。

4> 希爾排序（不穩定）

（1）對于中等大小的數組它的運行時間是可以接受的。它的代碼量很小，且不需要使用額外的內

存空間。雖然有更加高效的算法，但除了對于很大的 N，它們可能只會比希爾排序快兩倍(可能還

達不到)，而且更復雜。如果你需要解決一個排序問題而又沒有系統排序函數可用，可以先用希爾

排序，然后再考慮是否值得將它替換為更加復雜的排序算法。

（2）希爾排序是對直接插入排序的一種優化，可以用于大型的數組，希爾排序比插入排序和選擇

排序要快的多，并且數組越大，優勢越大。

------------------------------------

排序算法一：冒泡排序

一、簡介

排序（Bubble Sort）是一種簡單的排序算法，它的基本思想是通過不斷交換相鄰兩個元素的位

置，使得較大的元素逐漸往后移動，直到最后一個元素為止。冒泡排序的時間復雜度為 O(n^2)，

空間復雜度為 O?

(1)，是一種穩定的排序算法。

其實現過程可以概括為以下幾個步驟：

從序列的第一個元素開始，對相鄰的兩個元素進行比較，如果它們的順序錯誤就交換它們的位置，即將較大的元素往后移動，直到遍歷到序列的最后一個元素。
對剩下的元素重復上述步驟，直到整個序列都已經有序。

二、示例代碼

public class BubbleSort {public static void bubbleSort(int[] arr) {int n = arr.length;for (int i = 0; i < n; i++) {// 每輪遍歷將最大的數移到末尾for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j+1]) {int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}}public static void main(String[] args) {int[] arr = {64, 34, 25, 12, 22, 11, 90};bubbleSort(arr);System.out.println(Arrays.toString(arr));  // [11, 12, 22, 25, 34, 64, 90]}
}

三、變種

冒泡排序有一些變種，其中比較常見的有以下幾種：

雞尾酒排序（Cocktail Sort）：又稱為雙向冒泡排序，它是一種改進的冒泡排序算法。
與普通冒泡排序不同的是，它是從左到右遍歷序列，然后從右到左遍歷序列，交替進行，直到序列有序為止。
這樣可以在一定程度上減少排序的時間。
短冒泡排序（Short Bubble Sort）：在冒泡排序的基礎上進行改進，當某一輪遍歷中沒有發生元素交換時，說明序列已經有序，可以提前結束排序。這樣可以在序列已經有序的情況下減少不必要的比較次數。
奇偶排序（Odd-Even Sort）：也稱為交替排序，它是一種并行排序算法，可以同時比較和交換序列中的奇數和偶數位置上的元素，直到序列有序為止。這樣可以在一定程度上減少排序的時間，但是它只適用于能夠并行處理的情況。

這些變種算法都是基于冒泡排序的基本思想，并對其進行了不同的優化和改進，使得排序效率更

高。

1. 雞尾酒排序

1.1. 簡介

雞尾酒排序是一種定向的冒泡排序（又叫快樂小時排序），排序是從低到高再從高到低的反復。

而冒泡排序是從低到高的排序。

先來看看冒泡排序

舉個栗子：8個數組成一個無序數列：3、2、4、5、6、7、1、8，希望從小到大排序

第一輪結果（ 3 和 2 交換，1 和 8 交換）

2、3、4、5、6、7、1、8

第二輪結果（ 7 和 1 交換）

、

第三輪結果（ 6 和 1 交換）

接下來（5和1交換，4和1交換，3和1交換，2和1交換）

最后結果為

總共進行了7次交換

下面用雞尾酒排序該無序數列

第一輪（ 3 和 2 交換，8 和 1 交換）

第二輪

此時開始不一樣了，我們要從右到左（即高到低）進行交換、比較

即在這里8已經在有序區域了，不考慮。讓1和7比較，1小于7，7和1交換

2、3、4、5、6、7、1、8

然后 6 和 1 交換，

2、3、4、5、1、6、7、8

5 和 1 交換，4 和 1 交換，3 和 1 交換， 2 和 1 交換

最終結果：

1、2、3、4、5、6、7、8

第三輪（結果已經有序了，但流程并沒有結束）

第三輪需要重新從左到右（從低到高）比較和交換

1和2比較，位置不變；2和3比較，位置不變， ...... ，6和7比較，位置不變

沒有元素位置交換，證明已經有序，排序結束

對于雙向雞尾酒排序，我們可以在每一輪排序的最后，記錄下最后一次元素交換的位置（ rightChange 和

leftChange ）,那個位置就是無序數列的邊界，再往后就是有序區了。

1.2. 代碼

下面給出雙向的雞尾酒排序的java代碼

public class CocktailSort {public static void main(String[] args) {int[] arr = {11, 95, 45, 15, 51, 12, 24};sort(arr);}public static void sort(int[] arr) {boolean sorted1 = true;boolean sorted2 = true;int len = arr.length;for (int j = 0; j < len / 2; j++) { //趟數sorted1 = true; //假定有序sorted2 = true;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;sorted1 = false; //假定失敗}}for (int i = len - 1 - j; i > j; i--) { //次數if (arr[i] < arr[i - 1]) {int temp = arr[i];arr[i] = arr[i + 1];arr[i + 1] = temp;sorted2 = false; //假定失敗}}System.out.println(Arrays.toString(arr));if (sorted1 && sorted2) { //減少趟數，已有序則結束break;}}}
}

1.3. 復雜度

雞尾酒排序最糟或是平均所花費的次數都是O(n2)，但如果序列在一開始已經大部分排序過的話，

會接近O(n)。

2. 短冒泡排序

2.1. 簡介

冒泡排序是一種基礎的排序算法，短冒泡排序是冒泡排序的一種改進，主要是為了解決冒泡排序在

數組初始狀態為逆序時效率低的問題。

在冒泡排序中，如果序列已經有序，則無需進行交換，但是在傳統的冒泡排序中，會進行n-1次全

排列，這就造成了不必要的計算。

短冒泡排序的思路是在每次遍歷的過程中，記錄下本次遍歷的最大位置i，

在下一次遍歷時，只需要遍歷到i位置，這就減少了全排列的次數。

2.2. 代碼

public class ShortBubbleSort {public static void sort(int[] array) {if (array == null || array.length <= 1) {return;}int len = array.length;for (int i = 0; i < len; i++) {// 記錄本次遍歷的最大位置int maxPos = i;for (int j = i + 1; j < len; j++) {if (array[j] > array[maxPos]) {maxPos = j;}}// 如果最大值不在最后的位置，交換最大值和當前位置的值if (maxPos != i) {int temp = array[i];array[i] = array[maxPos];array[maxPos] = temp;}}}
}

這段代碼首先判斷了數組是否為空或者只有一個元素，如果是的話，那么就沒有排序的必要。

然后開始進行短冒泡排序，外層循環遍歷數組，內層循環找出當前未排序部分的最大值，并記錄其

位置。

如果最大值不在當前位置，那么就交換這兩個位置的值。

這樣，每次外層循環結束后，最大的元素就會被放到正確的位置。重復這個過程，直到整個數組都

被排序。

3. 奇偶排序

3.1. 簡介

奇偶排序（Odd-Even Sort）：也稱為交替排序，它是一種并行排序算法，可以同時比較和交換序

列中的奇數和偶數位置上的元素，直到序列有序為止。這樣可以在一定程度上減少排序的時間，但

是它只適用于能夠并行處理的情況。

3.2. 題目

3.3. 代碼

3.3.1. 方法一：兩次遍歷

代碼：

class Solution {public int[] sortArrayByParity(int[] nums) {int n = nums.length, index = 0;int[] res = new int[n];for (int num : nums) {if (num % 2 == 0) {res[index++] = num;}}for (int num : nums) {if (num % 2 == 1) {res[index++] = num;}}return res;}
}

3.3.2. 方法二：雙指針 + 一次遍歷

代碼：

class Solution {public int[] sortArrayByParity(int[] nums) {int n = nums.length;int[] res = new int[n];int left = 0, right = n - 1;for (int num : nums) {if (num % 2 == 0) {res[left++] = num;} else {res[right--] = num;}}return res;}
}

3.3.3. 方法三：原地交換

代碼：

class Solution {public int[] sortArrayByParity(int[] nums) {int left = 0, right = nums.length - 1;while (left < right) {while (left < right && nums[left] % 2 == 0) {left++;}while (left < right && nums[right] % 2 == 1) {right--;}if (left < right) {int temp = nums[left];nums[left] = nums[right];nums[right] = temp;left++;right--;}}return nums;}
}

四、應用場景

冒泡排序雖然時間復雜度較高，但是它的實現簡單，容易理解，并且在某些特定場景下仍然有著廣

泛的應用。

以下是一些冒泡排序的應用場景：

數據量較小的排序：當待排序的數據量較小時，冒泡排序的效率并不比其他排序算法低，甚至在某些情況下可能更優。
數據基本有序的排序：當待排序的數據基本有序時，冒泡排序的效率比其他排序算法更高。
因為冒泡排序可以在一輪遍歷中將已經有序的元素排除在外，從而減少比較和交換的次數。
學習排序算法：冒泡排序是最基本的排序算法之一，它的實現簡單，容易理解，是學習排序算法的入門算法。

需要注意的是，如果待排序的數據量較大，或者數據分布比較隨機，冒泡排序的效率會比較低，不如其他排序

法。因此，在實際應用中，需要根據具體的情況選擇適合的排序算法。

五、框架應用

1. 冒泡排序在spring 中的應用

在 Spring 框架中，冒泡排序算法并沒有直接應用到核心模塊中，但是它可以作為一種排序算法被使用在 Spring

的某些模塊中，例如：

Spring Security 模塊中的權限排序：Spring Security 是一個基于 Spring 的安全框架，它提供了一套完整的安全解決方案，包括認證、授權、攻擊防護等功能。在 Spring Security 中，權限可以通過冒泡排序算法來進行排序，以便于在授權時按照順序進行匹配。
Spring Batch 模塊中的數據排序：Spring Batch 是一個基于 Spring 的批處理框架，它可以幫助用戶快速構建和執行大規模、復雜的批處理作業。在 Spring Batch 中，數據排序是一個常見的操作，可以使用冒泡排序算法來實現。

需要注意的是，冒泡排序算法雖然簡單，但是在實際應用中效率較低，因此在處理大規模數據時不

建議使用。

在 Spring 框架中，如果需要進行排序操作，建議使用更高效的排序算法，例如快速排序、歸并排

序等。

六、算法分析

冒泡排序的時間復雜度為 O(n^2) ，空間復雜度為 O (1)，是一種穩定的排序算法。

時間復雜度：冒泡排序的時間復雜度是 O(n^2)，其中 n 是待排序序列的長度。
冒泡排序的比較次數和交換次數都是 n(n-1)/2，因此時間復雜度為 O(n^2)。
空間復雜度：冒泡排序的空間復雜度是 O(1)，即只需要使用常數級別的額外空間來存儲臨時變量。
算法穩定性：冒泡排序是一種穩定的排序算法，即相等的元素在排序前后的相對位置不會發生改變。

------------------------------------

排序算法二：選擇排序

一、基本介紹

從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然后再從剩余的未排序元素中

尋找到最小（大）元素，繼續放在起始位置，直到未排序元素個數為0。

核心思想

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再從剩余未排序元素中繼續尋找最小（大）元素，然后放到未排序序列的起始位置。
重復第二步，直到所有元素均排序完畢。

二、示例代碼

方式一：原始版

	public static void sort(int[] num){if(num.length < 2 || num == null) return;int index = 0;//標記最小值處int count = 0;//循環次數int count1 = 0;//交換次數for (int i = 0; i < num.length-1; i++) {index = i;for (int j = i; j < num.length ; j++) {count++;if(num[j] < num[index]) index = j;//發現更小值，獲取下標}if(i != index){//交換count1++;int c = num[i];num[i] = num[index];num[index] = c;System.out.print("交換了"+num[i]+"和"+num[index]+"結果：");}for (int m = 0; m < num.length; m++) {System.out.print(num[m]+",");}System.out.println();}System.out.println("循環次數"+count+"交換次數"+count1);}

方式二：遞歸版

	public static void sort1(int[] num,int m,int length,int count){if( length < 2 ) return;int index = m;//標記最小值for (int i = m; i < length+m; i++) {count++;if( num[i] < num[index] ) index = i;//發現更小值，獲取下標}if( index != 0 ){ //交換int c = num[m];num[m] = num[index];num[index] = c;System.out.print("交換了" + num[m] + "和" + num[index] + "結果：");}for (int n = 0; n < num.length; n++) {System.out.print(num[n]+",");}System.out.println("遞歸次數:" + m + "循環次數：" + count);sort1(num,m+1,--length,count);}

方式三：優化版

	public static void sort2(int[]num){if( num.length < 2 || num == null )return;int left,right;//標記左右int min,max;//標記最大和最小值left = 0;right = num.length - 1;int m = 0;while ( left < right ){min = left;max = right;for (int i = left; i < right+1 ; i++) {m++;if(num[i] <= num[min]) min = i;//掃描獲得最小值下標if(num[i] >= num[max]) max = i;//掃描獲得最大值下標}if( min != left ){int c = num[left];num[left] = num[min];num[min] = c;System.out.print("交換了"+num[left]+"和"+num[min]+"結果：");}if( max == left )min=max;if( max != right ){int c = num[right];num[right] = num[max];num[max] = c;System.out.print("交換了"+num[right]+"和"+num[max]+"結果：");}left++;right--;for (int n = 0; n < num.length; n++) {System.out.print(num[n]+",");}System.out.println("循環次數"+m);}}

方式四：優化遞歸版

	public static void sort3(int[] num,int m,int length){if( length < 2 )return;int index = m;//左標int index1 = num.length - m - 1;//右標for (int i = m; i < length; i++) {if( num[i] <= num[index] ) index=i;//掃描獲得最小值下標}if( index != m ){int c = num[m];num[m] = num[index];num[index] = c;System.out.print("交換了"+num[m]+"和"+num[index]+"結果：");}for (int i = m; i < length; i++) {if(num[i] >= num[index1]) index1 = i;//掃描獲得最大值下標}if( index1 != ( num.length - m - 1 ) ){int c = num[num.length-m-1];num[num.length-m-1] = num[index1];num[index1] = c;System.out.print("交換了"+num[num.length - m - 1]+"和"+num[index1]+"結果：");}for (int n = 0; n < num.length; n++) {System.out.print(num[n]+",");}System.out.println("遞歸次數"+m);if( m < ( num.length - m - 1) ) sort3(num,m+1,--length);}

三、變種

四、應用場景

選擇排序雖然時間復雜度較高，但是它的實現簡單，容易理解，并且在某些特定場景下仍然有著廣泛的應用。

以下是一些適合使用選擇排序的場景：

數據量較小：當待排序序列的數據量較小時，選擇排序的效率還是比較高的。在這種情況下，選擇排序比其他高級排序算法（如快速排序、歸并排序等）更容易實現和理解。
內存限制：選擇排序是一種原地排序算法，即不需要額外的內存空間來存儲臨時變量。因此，當內存空間有限時，選擇排序是一種比較合適的排序算法。
部分有序：當待排序序列已經有一部分有序時，選擇排序的效率會比其他排序算法高。這是因為選擇排序每次只選擇最小的元素進行交換，因此不會破壞已經有序的部分。

需要注意的是，選擇排序的時間復雜度較高，因此在處理大規模數據時，應該使用其他更高效的排序算法。

五、框架應用

1. 選擇排序在spring 中的應用

在 Spring 中，選擇排序并不是一個常用的算法，因此它并沒有被直接應用在 Spring 框架中。

然而，選擇排序的思想可以啟發我們在 Spring 中的一些實踐，例如：

Bean 的排序：在 Spring 中，我們可以通過實現 org.springframework.core.Ordered接口或者使用 @Order ?注解來控制 Bean的加載順序。這種方式類似于選擇排序中的選擇最小元素，即通過指定 Bean 的優先級來控制其加載順序。
AOP 切面的優先級：在 Spring AOP 中，我們可以通過 org.springframework.core.annotation.Order 注解來控制切面的優先級。這種方式也類似于選擇排序中的選擇最小元素，即通過指定切面的優先級來控制其執行順序。
Spring Security 中的 Filter 鏈：在 Spring Security 中，Filter 鏈是一種類似于責任鏈模式的機制，它由多個 Filter 組成，每個 Filter負責不同的安全檢查。這種方式也類似于選擇排序中的選擇最小元素，即通過指定 Filter 的執行順序來控制安全檢查的順序。

雖然選擇排序并不是 Spring 中的常用算法，但是它的思想可以啟發我們在 Spring 中的一些實踐，從而提高代碼

的可讀性和可維護性。

六、算法分析

時間復雜度
最好的情況全部元素已經有序，則交換次數為0；最差的情況，全部元素逆序，就要交換 n-1 次；
所以最優的時間復雜度和最差的時間復雜度和平均時間復雜度都為：O(n^2)
空間復雜度
最優的情況下（已經有順序）復雜度為：O(0) ；
最差的情況下（全部元素都要重新排序）復雜度為：O(n );
那么選擇排序算法平均的時間復雜度為：O(1)
算法穩定性
選擇排序是給每個位置選擇當前元素最小的，比如給第一個位置選擇最小的，在剩余元素里面給第二個元素選擇第二小的，依次類推，直到第n-1個元素，第n個元素不用選擇了，因為只剩下它一個最大的元素了。那么，在一趟選擇，如果一個元素比當前元素小，而該小的元素又出現在一個和當前元素相等的元素后面，那么交換后穩定性就被破壞了。所以選擇排序是不穩定的。

------------------------------------

排序算法三：插入排序

一、基本介紹

插入排序是一種簡單直觀的排序算法，它的工作原理是通過構建有序序列，對于未排序數據，在已

排序序列中從后向前掃描，找到相應位置并插入。

具體步驟如下：

從第一個元素開始，該元素可以認為已經被排序。
取出下一個元素，在已經排序的元素序列中從后向前掃描。
如果該元素（已排序）大于新元素，將該元素移到下一位置。
重復步驟3，直到找到已排序的元素小于或者等于新元素的位置。
將新元素插入到該位置后。
重復步驟2~5，直至所有元素都已排序完畢。1

在實際應用中，插入排序通常適用于較小規模的數據排序。

雖然其時間復雜度在最壞情況下為O(n^2)，但在部分已排序的序列中，其效率可能會高于其他排序

算法，如冒泡排序等。

此外，插入排序還具有穩定性，即相等的元素在排序后保持原有的順序不變。

二、示例代碼

方法一：交換法

    /*** 希爾排序*/@Testpublic void testShellSort() {int[] arr = new int[]{1, 4, 6, 3, 8, 9, 2,  23};exchangeShellSort(arr);
//        insertShellSort(arr);}/*** 希爾排序-交換法* @param arr*/public void exchangeShellSort(int arr[]) {int temp;// 臨時數據boolean flag = false;// 是否交換int count = 1;// 計數
//        分而治之，將數值分組排序,i為步長for (int i = arr.length / 2; i > 0; i /= 2) {
//            遍歷分治的每一個分組for (int j = i; j < arr.length; j++) {
//                遍歷分治的每一個分組的每一個值for (int k = j - i; k >= 0; k -= i) {if (arr[k + i] < arr[k]) {temp = arr[k + i];arr[k + i] = arr[k];arr[k] = temp;flag = true;}if (!flag) {break;} else {
//                        為了下次判斷flag = false;}}}System.out.println("希爾排序交換法第" + (count++) + "次排序后" + Arrays.toString(arr));}}

方法二：插入法

    /*** 希爾排序*/@Testpublic void testShellSort() {int[] arr = new int[]{1, 4, 6, 3, 8, 9, 2,  23};
//        exchangeShellSort(arr);insertShellSort(arr);}/*** 希爾排序-插入法* @param arr*/public void insertShellSort(int[] arr) {int count = 1;//計數
//        分而治之，循環為每次總數除二for (int i = arr.length / 2; i > 0; i /= 2) {
//            循環分治的每一個分組for (int j = i; j < arr.length; j++) {int index = j;int temp = arr[index];
//                比較每一組的值if (arr[index] < arr[index - i]) {
//                    如果比前面小就把前面的數值往后移，將合適的數值插入while (index - i > 0 && temp < arr[index - i]) {arr[index] = arr[index - i];index -= i;}arr[index] = temp;}}System.out.println("希爾排序插入法第" + (count++) + "次排序后" + Arrays.toString(arr));}}

三、變種

1. 直接插入排序

1.1. 簡介

直接插入排序（Insertion Sort）是一種基本的排序算法。

其思想是將數組分為已有部分和未排序部分，然后逐個比較并移動元素來達到排序目標。

一個簡單的例子：斗地主揭牌

我們從牌堆揭了一張A，現在要放到手牌中，一般來說都會插入到 2 與 J 之間

而直接插入排序就是這種思想

紅線左邊認為是有序的，紅線右邊是無序的

每一次從紅線右邊取一個值放到左邊進行排序

第一次可以省略掉，直接從第二個數據開始處理

例如，在斗地主揭牌，第一張牌我們不需要看，揭第二張牌，我才需要看一下這張牌是多少，是向左放還是向右

放

第二次，取出22這個數據，與已經排好的數據比較，22大于11，所以不需要挪動，直接插入即可

第三次取出 7 這個數，與已經排好的數據比較，7 比 22 小，向左繼續比較，7比11小，向左繼續比較，此時觸底，所以直接插入7.

小，向左繼續比較，此時觸底，所以直接插入5.

第五次取出17這個數，與已經排好的數據比較，17 比 22 小，向左繼續比較，17比11大，停止比較，插入17.

第六次的數據排好后，紅線右邊無數據，認為數組已經有序

用一句話描述調整過程：

將待插入的值和有序數組從右向左依次比較，找到小于等于自己的值，停下來，插入即可。

數據越有序，我們調用直接插入排序去比較挪動的次數越少，所以時間復雜度越低。

1.2. 代碼

public class InsertionSort {// 插入排序public static void insertionSort(int[] arr) {// 數組長度int n = arr.length;// 第一循環，從第二個元素開始for (int i = 1; i < n; ++i) {// 確定關鍵字int key = arr[i];// 從已經排好序的最右邊開始向左依次與key進行比較int j = i - 1;// while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];--j;}arr[j + 1] = key;}}public static void main(String[] args) {int[] array = {5, 2, 8, 3, 9};System.out.println("原始數組：");printArray(array);insertionSort(array);System.out.println("\n排序結果：");printArray(array);}private static void printArray(int[] arr) {for (int num : arr) {System.out.print(num + " ");}System.out.println();}
}

1.3. 算法分析

時間復雜度：O(N ^ 2)
空間復雜度：O(1)
穩定性：穩定
最好的情況：序列已經有序，只需要判斷是否滿足條件，不需要移動，時間復雜度為O(N)。
中間的情況：數據需要后移一部分，那時間復雜度就是O(N/2)即O(N)；
最壞的情況：序列是逆序插入，那么每插入一個數據都要和前面的比較、插入N個數據，此時時間復雜度就是O(N^2)；

2. 折半插入排序

2.1. 簡介

折半插入排序（binary insertion sort）是對插入排序算法的一種改進，由于排序算法過程中，就是

不斷的依次將元素插入前面已排好序的序列中。由于前半部分為已排好序的數列，這樣我們不用按

順序依次尋找插入點，可以采用折半查找的方法來加快尋找插入點的速度。

折半插入排序圖文說明

注：藍色代表已排序序列，白色代表未排序序列，紅色箭頭指向未排序序列的第一個元素位置。

如圖所示，現在有一個待排序序列[8 5 4 2 3]，首先默認初始狀態下，位置0的數字8作為已排序序

列[8]，位置1--位置4的[5 4 2 3 1] 為待排序序列，之后就逐一從[5 4 2 3 1]中取出數字向前進行比

較，插入到已排序序列的合適位置。尋找過程中將藍色的已排序區域不斷進行折半。

初始狀態下，已排序區只有一個數據元素8，low位置和high位置都指向了該位置，mid為中間位

置，此時很顯然也是0位（0+0）/ 2。

此時temp < mid，將high指向mid的前一位，這里也就是-1，這個時候high=-1，low=1，很顯然

high<low，每當這個時候，就到了移動元素的時候了，將(high+1)到(i-1)的元素都向后移一位，再

把(high+1)位置上插入要插入的元素。

2.2. 代碼

public class BinaryInsertionSort{public static void main(String[] args){// 待排序的數組        int[] array = { 1, 0, 2, 5, 3, 4, 9, 8, 10, 6, 7};// 折半插入排序開始binaryInsertSort(array);   // 顯示排序后的結果。        System.out.print("排序后： ");  for(int i = 0; i < array.length; i++){     // 打印數組元素System.out.print(array[i] + " ");   }  }   // Binary Insertion Sort method    private static void binaryInsertSort(int[] array){// 循環遍歷for(int i = 1; i < array.length; i++){// 臨時保存int temp = array[i];// 左邊界int low = 0;// 右邊界int high = i - 1;  // 循環遍歷，直到超出high邊界while(low <= high){                int mid = (low + high) / 2;if(temp < array[mid]){                    high = mid - 1;                }else{                    low = mid + 1;}       }for(int j = i; j >= low + 1; j--){array[j] = array[j - 1];}       array[low] = temp;}}
}

2.3. 算法分析

折半查找只是減少了比較次數，但是元素的移動次數不變。

時間復雜度：O(N^2)
空間復雜度：O(1)
穩定性：穩定

3. 希爾排序（Donald.L.Shell）

3.1. 簡介

希爾排序（Shell Sort）是一種基于插入排序的高效算法。

其主要思想是將數組分成多個子數組進行插入排序，然后逐漸合并這些子數組直到最終完全有序。

如圖示例：

（1）初始增量第一趟 gap = length / 2 = 4

（2）第二趟，增量縮小為 2

（3）第三趟，增量縮小為 1,得到最終排序結果

3.2. 代碼

public class ShellSort {public static void main(String[] args) {int[] arr = {9, 5, 2, 7, 1}; // 原始數組System.out.println("初始數組：");for (int num : arr) {System.out.print(num + " ");}shellSort(arr); // 調用希爾排序函數System.out.println("\n排序結果：");for (int num : arr) {System.out.print(num + " ");}}private static void shellSort(int[] arr) {int n = arr.length;for (int gap = n / 2; gap > 0; gap /= 2) {for (int i = gap; i < n; i++) {int temp = arr[i];int j = i - gap;while (j >= 0 && arr[j] > temp) {arr[j + gap] = arr[j];j -= gap;}arr[j + gap] = temp;}System.out.println();System.out.print("第" + (gap == n ? "" : "間距") + "次排序結果：");for (int num : arr) {System.out.print(num + " ");}}}
}

四、應用場景

適用于：數據量不大，并且對穩定性有要求并且數據局部或者整體有序的情況。

五、框架應用

六、算法分析

時間復雜度：最好（排序表本身有序）：O(n) / ?最壞（排序表逆序）O(n2)
空間復雜度：O(1)
算法穩定性：穩定

------------------------------------

	//堆排序public static int[] HeapSort(int[] arr){int len = arr.length;/*** 第一步，初始化堆，最大堆，從小到大* i從完全二叉樹的第一個非葉子節點開始，也就是len/2-1開始(數組下標從0開始)*/for(int i = len / 2 - 1;i >= 0;i--){HeapAdjust(arr,i,len);}//打印堆頂元素，應該為最大元素9System.out.println(arr[0]);return arr;}

上述代碼就是從完全二叉樹的第一個非葉子節點開始調換，還順便打印堆頂元素，此時應為9；

至此，第一個步驟，初始化堆完成，最后的結果應該為下圖：

第二個步驟，堆排序

堆排序的過程就是將堆頂元素（最大值或者最小值）與二叉堆的最末尾葉子節點進行調換，不停的調換，直到二

叉堆的順序變成從小到大

或者從大到小，也就實現了我們的目的。

我們這里以最大堆的堆頂元素（最大元素）為例，最后調換的結果就是從小到大排序的結果。

第一次交換，我們直接將元素9與元素0交換，此時堆頂元素為0，設當前節點index=0；

代碼：

/*** 第二步，交換堆頂（最大）元素和二叉堆的最后一個葉子節點元素。目的是交換元素* i從二叉堆的最后一個葉子節點元素開始，也就是len-1開始(數組下標從0開始)*/
for(int i = len - 1;i >= 0;i--){int temp = arr[i];arr[i] = arr[0];arr[0] = temp;//交換完之后需要重新調整二叉堆，從頭開始調整，此時Index=0HeapAdjust(arr,0,i);
}

注意：這里有個小細節問題，前面我們寫的初始化堆方法有三個參數，分別是數組arr，當前節點index以及數組長

度len，如下：

HeapAdjust(int[] arr,int index,int len)

那么，為何不直接傳入兩個參數即可，數組長度直接用arr.length表示不就行了嗎？

初始化堆的時候是可以，但是后面在交換堆頂元素和末尾的葉子節點時，在對剩下的元素進行排序時，

此時的數組長度可不是arr.length了，應該是變化的參數i，因為交換之后的元素

（比如9）就不計入堆中排序了，所以需要3個參數。

我們進行第二次交換，我們直接將元素8與元素2交換，此時堆頂元素為2，設當前節點index=2；

這時，我們需要將剩下的元素（排除元素9和8）進行堆排序，直到下面這個結果：

到這個時候，我們再重復上述步驟，不斷調換堆頂和最末尾的節點元素即可，再不斷地對剩下的元

素進行排序，最后就能得到從小到大排序好的堆了，如下圖所示，這就是我們想要的結果：

三、完整代碼

import java.util.Arrays;public class Head_Sort {public static void main(String[] args) {int[] arr = {4,2,8,0,5,7,1,3,9};System.out.println("排序前:"+Arrays.toString(arr));System.out.println("排序后:"+Arrays.toString(HeapSort(arr)));}//堆排序public static int[] HeapSort(int[] arr){int len = arr.length;/*** 第一步，初始化堆，最大堆，從小到大。目的是對元素排序* i從完全二叉樹的第一個非葉子節點開始，也就是len/2-1開始(數組下標從0開始)*/for(int i = len/2-1;i >=0;i--){HeapAdjust(arr,i,len);}/*** 第二步，交換堆頂（最大）元素和二叉堆的最后一個葉子節點元素。目的是交換元素* i從二叉堆的最后一個葉子節點元素開始，也就是len-1開始(數組下標從0開始)*/for(int i = len - 1;i >= 0;i--){int temp = arr[i];arr[i] = arr[0];arr[0] = temp;//交換完之后需要重新調整二叉堆，從頭開始調整，此時Index=0HeapAdjust(arr,0,i);}return arr;}/***初始化堆* @param arr 待調整的二叉樹(數組)* @param index 待調整的節點下標，二叉樹的第一個非葉子節點* @param len 待調整的數組長度*/public static void HeapAdjust(int[] arr,int index,int len){//先保存當前節點的下標int max = index;//保存左右孩子數組下標int lchild = index*2+1;int rchild = index*2+2;//開始調整，左右孩子下標必須小于len，也就是確保index必須是非葉子節點if(lchild <len && arr[lchild] > arr[max]){max = lchild;}if(rchild < len && arr[rchild] > arr[max]){max = rchild;}//若發生了交換，則max肯定不等于index了。此時max節點值需要與index節點值交換，上面交換索引值，這里交換節點值if(max != index){int temp = arr[index];arr[index] = arr[max];arr[max] = temp;//交換完之后需要再次對max進行調整，因為此時max有可能不滿足最大堆HeapAdjust(arr,max,len);}}
}

運行結果：

四、應用場景

大數據量排序：堆排序可以處理大數據量，特別是當數據以堆結構存儲時，它可以利用堆結構高效地進行排序。
優先隊列：堆結構本身就是一種優先隊列，因此堆排序可以用于實現優先隊列，如在操作系統中，根據進程的優先級進行排序。
最大/最小值查詢：堆排序可以通過堆結構實現最大/最小值查詢，如在電商網站中，根據商品價格進行排序。
求前K大/小元素：堆排序還可以通過堆結構實現求前K大/小元素，如在學生成績排序中，根據學生的成績進行排序1。

綜上所述，堆排序在大數據處理、優先隊列、最大/最小值查詢和前K大/小元素查詢等領域具有廣

泛的應用價值。

五、框架應用

六、算法分析

時間復雜度
建堆的時候初始化堆過程(HeapAdjust)是堆排序的關鍵，時間復雜度為O(log n)，下面看堆排序的兩個過程；
第一步，初始化堆，這一步時間復雜度是O(n)；
第二步，交換堆頂元素過程，需要用到n-1次循環，且每一次都要用到(HeapAdjust)，所以時間復雜度為((n-1)*log n)~O(nlog n)；
最終時間復雜度：O(n)+O(nlog n)，后者復雜度高于前者，所以堆排序的時間復雜度為O(nlogn)；
空間復雜度
空間復雜度是O(1)，因為沒有用到額外開辟的集合空間。
算法穩定性
堆排序是不穩定的，比方說二叉樹[6a，8，13，6b]，（這里的6a和6b數值上都是6，只不過為了區別6所以這樣）經過堆初始化后以及排序過后就變成[6b，6a，8，13]；可見堆排序是不穩定的。

------------------------------------

排序算法六：快速排序

一、基本介紹

快速排序（quicksort）是分治算法技術的一個實例，也稱為分區交換排序。

劃分：

數組A[low..high]被分成兩個非空子數組 A[low..q]和 A[q+1..high]，

使得A[low..q]中的每一個元素都小于或等于 A[q+1..high]中的元素。

在劃分過程中需要計算索引q的位置。

分而治之：

對兩個子數組A[low..q]和A[q+1..high]遞歸調用快速排序。

問題1

給定一個數組arr，和一個整數num。請把小于等于num的數放在數組的左邊，大于num的數放在數

組的右邊。

要求額外空間復雜度O(1)，時間復雜度O(N)

二、示例代碼

三、快排變種

1. 基于小于區的遞歸版本的快排

    public static void quickSort(int[] arr) {// 數組為空或者元素只有一個沒必要排序if (arr == null || arr.length < 2) {return;}// 不滿足以上條件進一步處理process(arr, 0, arr.length - 1);}public static void process(int[] arr, int L, int R) {// 遞歸終止條件if (L >= R) {return;}// 分值int M = partition(arr, L, R);// 左區域進一步處理process(arr, L, M - 1);// 右區域進一步處理process(arr, M + 1, R);}public static int partition(int[] arr, int L, int R) {// 左邊界不能小于右邊界if (L > R) {return -1;}// 左邊界等于右邊界，結束，說明區域分到只剩一個元素if (L == R) {return L;}// 小于等于區int lessEqual = L - 1;int index = L;// 迭代while (index < R) {if (arr[index] <= arr[R]) {// 小于等于區右移，交換swap(arr, index, ++lessEqual);}index++;}// 右邊界作為劃分值，最終需要交換到左區域最后一個位置swap(arr, ++lessEqual, R);return lessEqual;}public static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}

2. 荷蘭國旗問題的遞歸版本的快排

2.1. 什么是荷蘭國旗問題

荷蘭國旗是由紅白藍3種顏色的條紋拼接而成，如下圖所示：

假設這樣的條紋有多條，且各種顏色的數量不一，并且隨機組成了一個新的圖形，

新的圖形可能如下圖所示，但不僅僅只有這一種情況：

需求是：把這些條紋按照顏色排好，紅色的在上半部分，白色的在中間部分，藍色的在下半部分，

我們把這類問題稱作荷蘭國旗問題。

2.2. 荷蘭國旗問題的抽象

我們把荷蘭國旗問題抽象成數組的形式是下面這樣的：

給定一個整數數組和一個值M（存在于原數組中），

要求把數組中小于M的元素放到數組的左邊，等于M的元素放到數組的中間，大于M的元素放到數

組的右邊，最終返回一個整數數組，只有兩個值，0位置是等于M的數組部分的左下標值、1位置是

等于M的數組部分的右下標值。

進一步抽象為更加通用的形式是下面這樣的：

給定數組arr，將[l, r]范圍內的數（當然默認是 [ 0 - arr.length - 1 ]），

小于arr[r]（這里直接取數組最右邊的值進行比較）放到數組左邊，

等于arr[r]放到數組中間，

大于arr[r]放到數組右邊。

最后返回等于arr[r]的左, 右下標值。

2.3. 解決的思路

定義一個小于區，一個大于區；遍歷數組，挨個和arr[r]比較，

（1）小于arr[r]，與小于區的后一個位置交換，當前位置后移；

（2）等于arr[r]，當前位置直接后移；

（3）大于arr[r]，與大于區的前一個位置交換，當前位置不動（交換到此位置的數還沒比較過，所

以不動）。

遍歷完后，arr[r]和大于區的最左側位置交換。

最后返回，此時小于區的后一個位置，大于區的位置，即是最后的等于arr[r]的左, 右下標值。

2.4. 代碼實現

public class QuickSort2 {public static void quickSort(int[] arr) {// 數組為null或者元素只有一個沒必要排序if (arr == null || arr.length < 2) {return;}// 不只1個數，進一步處理process(arr, 0, arr.length - 1);}// arr[L...R] 排有序，快排2.0方式public static void process(int[] arr, int L, int R) {// 遞歸終止條件if (L >= R) {return;}// 等于區，荷蘭國旗問題后，返回的數組int[] equalArea = netherlandsFlag(arr, L, R);// 0位置是等于M的數組部分的左下標值process(arr, L, equalArea[0] - 1);// 1位置是等于M的數組部分的右下標值process(arr, equalArea[1] + 1, R);}// arr[L...R] 玩荷蘭國旗問題的劃分，以arr[R]做劃分值// <arr[R] ==arr[R] > arr[R]public static int[] netherlandsFlag(int[] arr, int L, int R) {// 左邊界大于右邊界，沒必要劃分了if (L > R) { // L...R L>Rreturn new int[] { -1, -1 };}// 左邊界等于右邊界，返回左右邊界位置if (L == R) {return new int[] { L, R };}// 以上不滿足，開始荷蘭國旗問題int less = L - 1; // < 區 右邊界int more = R; // > 區 左邊界int index = L;while (index < more) { // 當前位置，不能和 > 區的左邊界撞上if (arr[index] == arr[R]) {index++;} else if (arr[index] < arr[R]) {// 小于區右移一步再與當前位置交換，當前位置往后走一步swap(arr, index++, ++less);} else { // >// 都不滿足，就是大于，右邊區往左走一步再與當前位置交換swap(arr, index, --more);}}// 最終還有一個劃分值需要移動到中間位置，即右邊區與劃分值交換位置swap(arr, more, R); // <[R]   =[R]   >[R]// 完成劃分，返回一個只有兩個元素的數組return new int[] { less + 1, more };}public static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}// for testpublic static void main(String[] args) {TimesUtil.test("優化：基于荷蘭國旗問題遞歸版本的快速排序:", new TimesUtil.Task() {@Overridepublic void execute() {int[] orginNums = {1,2,6,8,2,4};System.out.println(Arrays.toString(orginNums));quickSort(orginNums);System.out.println(Arrays.toString(orginNums));}});}}

3. 遞歸版本的隨機快排

發現，每次都是固定你劃分值，接下來進行隨機分配劃分值

public class QuickSort3 {// 隨機快排public static void quickSort(int[] arr) {// 數組為null或者元素只有一個沒必要排序if (arr == null || arr.length < 2) {return;}// 不只1個數，進一步處理process(arr, 0, arr.length - 1);}public static void process(int[] arr, int L, int R) {// 遞歸終止條件if (L >= R) {return;}// 隨機選取1個位置上的數換到R位置上,就是隨機一個劃分值swap(arr, L + (int) (Math.random() * (R - L + 1)), R);// 等于區，荷蘭國旗問題后，返回的數組int[] equalArea = netherlandsFlag(arr, L, R);// 0位置是等于M的數組部分的左下標值process(arr, L, equalArea[0] - 1);// 1位置是等于M的數組部分的右下標值process(arr, equalArea[1] + 1, R);}// arr[L...R] 玩荷蘭國旗問題的劃分，以arr[R]做劃分值// <arr[R] ==arr[R] > arr[R]public static int[] netherlandsFlag(int[] arr, int L, int R) {// 左邊界大于右邊界，沒必要劃分了if (L > R) { // L...R L>Rreturn new int[] { -1, -1 };}// 左邊界等于右邊界，返回左右邊界位置if (L == R) {return new int[] { L, R };}// 以上不滿足，開始荷蘭國旗問題int less = L - 1; // < 區 右邊界int more = R; // > 區 左邊界int index = L;while (index < more) { // 當前位置，不能和 >區的左邊界撞上if (arr[index] == arr[R]) {index++;} else if (arr[index] < arr[R]) {// 小于區右移一步再與當前位置交換，當前位置往后走一步swap(arr, index++, ++less);} else { // >// 都不滿足，就是大于，右邊區往左走一步再與當前位置交換swap(arr, index, --more);}}// 最終還有一個劃分值需要移動到中間位置，即右邊區與劃分值交換位置swap(arr, more, R); // <[R]   =[R]   >[R]// 完成劃分，返回一個只有兩個元素的數組return new int[] { less + 1, more };}public static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}/*** 生成隨機數組* @param maxSize 隨機數組的封頂大小* @param maxValue 隨機數值的封頂值* @return*/public static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr = new int[(int) ((maxSize + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());}return arr;}// for testpublic static void main(String[] args) {TimesUtil.test("遞歸版本的隨機快排:", new TimesUtil.Task() {@Overridepublic void execute() {int[] orginArrays = generateRandomArray(10,10);System.out.println(Arrays.toString(orginArrays));quickSort(orginArrays);System.out.println(Arrays.toString(orginArrays));}});}}

4. 非遞歸版本的隨機快排

public class QuickSort4 {// 快排非遞歸版本需要的輔助類// 要處理的是什么范圍上的排序public static class Op {public int l;public int r;public Op(int left, int right) {l = left;r = right;}}// 快排3.0 非遞歸版本public static void quickSort(int[] arr) {// 數組為null或者元素只有一個沒必要排序if (arr == null || arr.length < 2) {return;}// 獲取數組長度int R = arr.length;// 隨機選取1個位置上的數換到R位置上,就是隨機一個劃分值swap(arr, (int) (Math.random() * R), R - 1);// 等于區，荷蘭國旗問題后，返回的數組int[] equalArea = netherlandsFlag(arr, 0, R - 1);// 獲取等于區的左邊數int el = equalArea[0];// 獲取等于區的右邊數int er = equalArea[1];Stack<Op> stack = new Stack<>();stack.push(new Op(0, el - 1));stack.push(new Op(er + 1, R - 1));while (!stack.isEmpty()) {Op op = stack.pop(); // op.l  ... op.rif (op.l < op.r) {swap(arr, op.l + (int) (Math.random() * (op.r - op.l + 1)), op.r);equalArea = netherlandsFlag(arr, op.l, op.r);el = equalArea[0];er = equalArea[1];stack.push(new Op(op.l, el - 1));stack.push(new Op(er + 1, op.r));}}}// arr[L...R] 玩荷蘭國旗問題的劃分，以arr[R]做劃分值// <arr[R] ==arr[R] > arr[R]public static int[] netherlandsFlag(int[] arr, int L, int R) {// 左邊界大于右邊界，沒必要劃分了if (L > R) { // L...R L>Rreturn new int[] { -1, -1 };}// 左邊界等于右邊界，返回左右邊界位置if (L == R) {return new int[] { L, R };}// 以上不滿足，開始荷蘭國旗問題int less = L - 1; // < 區 右邊界int more = R; // > 區 左邊界int index = L;while (index < more) { // 當前位置，不能和 >區的左邊界撞上if (arr[index] == arr[R]) {index++;} else if (arr[index] < arr[R]) {// 小于區右移一步再與當前位置交換，當前位置往后走一步swap(arr, index++, ++less);} else { // >// 都不滿足，就是大于，右邊區往左走一步再與當前位置交換swap(arr, index, --more);}}// 最終還有一個劃分值需要移動到中間位置，即右邊區與劃分值交換位置swap(arr, more, R); // <[R]   =[R]   >[R]// 完成劃分，返回一個只有兩個元素的數組return new int[] { less + 1, more };}// 兩兩交換算法public static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}// for testpublic static void main(String[] args) {TimesUtil.test("優化：基于荷蘭國旗問題的非遞歸版本隨機快速排序:", new TimesUtil.Task() {@Overridepublic void execute() {int[] orginNums = {1,2,6,8,2,4};System.out.println(Arrays.toString(orginNums));quickSort(orginNums);System.out.println(Arrays.toString(orginNums));}});}}

四、應用場景

五、框架應用

六、算法分析

------------------------------------

排序算法七：拓撲排序

待更新

參考文獻

Java手寫拓撲排序和拓撲排序應用拓展案例
拓撲排序與關鍵路徑

------------------------------------

排序算法八：不基于比較的排序(3種)

前置知識

桶排序思想下的排序：計數排序 & 基數排序

桶排序思想下的排序都是不基于比較的排序

時間復雜度O(N)，額外空間復雜度O(M)

應用范圍有限，需要樣本的數據狀況滿足桶的劃分

一、桶排序

1. 什么是桶排序

桶排序（Bucket Sort）又稱箱排序，是一種比較常用的排序算法。其算法原理是將數組分到有限

數量的桶里，再對每個桶分別排好序（可以是遞歸使用桶排序，也可以是使用其他排序算法將每個

桶分別排好序），最后一次將每個桶中排好序的數輸出。

2. 算法思想

桶排序的思想就是把待排序的數盡量均勻地放到各個桶中，再對各個桶進行局部的排序，最后再按序將各個桶中

的數輸出，即可得到排好序的數。

首先確定桶的個數。因為桶排序最好是將數據均勻地分散在各個桶中，那么桶的個數最好是應該根據數據的分散情況來確定。
首先找出所有數據中的最大值mx和最小值mn；
根據mx和mn確定每個桶所裝的數據的范圍 size，有size = (mx - mn) / n + 1，n為數據的個數，
需要保證至少有一個桶，故而需要加個1；
求得了size即知道了每個桶所裝數據的范圍，還需要計算出所需的桶的個數cnt，
有cnt = (mx - mn) / size + 1，需要保證每個桶至少要能裝1個數，故而需要加個1；
求得了size和cnt后，即可知第一個桶裝的數據范圍為 [mn, mn + size)，第二個桶為 [mn + size, mn + 2 * size)，…，以此類推
因此步驟2中需要再掃描一遍數組，將待排序的各個數放進對應的桶中。
對各個桶中的數據進行排序，可以使用其他的排序算法排序，例如快速排序；也可以遞歸使用桶排序進行排序；
將各個桶中排好序的數據依次輸出，最后得到的數據即為最終有序。

3. 案例分析

例如，待排序的數為：3, 6, 9, 1

1）求得 mx = 9，mn = 1，n = 4

size = （9 - 1) / n + 1 = 3

cnt = (mx - mn) / size + 1 = 3

2）由上面的步驟可知，共3個桶，每個桶能放3個數，第一個桶數的范圍為 [1, 4)，第二個[4, 7)，

第三個[7, 10)掃描一遍待排序的數，將各個數放到其對應的桶中，放完后如下圖所示：

4）依次輸出各個排好序的桶中的數據，即為：1, 3, 6, 9

可見，最終得到了有序的排列。

4. 代碼實現

import java.util.ArrayList;public class BucketSort {public void bucketSort(int[] nums) {int n = nums.length;int mn = nums[0], mx = nums[0];// 找出數組中的最大最小值for (int i = 1; i < n; i++) {mn = Math.min(mn, nums[i]);mx = Math.max(mx, nums[i]);}int size = (mx - mn) / n + 1; // 每個桶存儲數的范圍大小，使得數盡量均勻地分布在各個桶中，保證最少存儲一個int cnt = (mx - mn) / size + 1; // 桶的個數，保證桶的個數至少為1List<Integer>[] buckets = new List[cnt]; // 聲明cnt個桶for (int i = 0; i < cnt; i++) {buckets[i] = new ArrayList<>();}// 掃描一遍數組，將數放進桶里for (int i = 0; i < n; i++) {int idx = (nums[i] - mn) / size;buckets[idx].add(nums[i]);}// 對各個桶中的數進行排序，這里用庫函數快速排序for (int i = 0; i < cnt; i++) {buckets[i].sort(null); // 默認是按從小打到排序}// 依次將各個桶中的數據放入返回數組中int index = 0;for (int i = 0; i < cnt; i++) {for (int j = 0; j < buckets[i].size(); j++) {nums[index++] = buckets[i].get(j);}}}public static void main(String[] args) {int[] nums = {19, 27, 35, 43, 31, 22, 54, 66, 78};BucketSort bucketSort = new BucketSort();bucketSort.bucketSort(nums);for (int num: nums) {System.out.print(num + " ");}System.out.println();}
}

5. 算法分析

二、計數排序

1. 什么是計數排序

計數排序：核心在于將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。

作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。

2. 算法步驟

我們大概講一下算法的步驟。

找出待排序的數組中的最大元素max和最小元素min
統計數組中每個元素num出現的次數，存入數組countArray的countArray[num-min]項中
計數數組變形，對所有的計數累加（從第一項開始countArray[i] = countArray[i] + countArray[i - 1]）
反向填充目標數組arr：從后往前遍歷待排序的數列copyArray（拷貝份），
由數組元素num計算出對應的計數數組的索引countIndex為num - min，
從而推斷出num在arr的位置為index為countArray[num-min] - 1，
然后num填充到arr[index]，
最后記得計數數組的值減1，即countArray[countIndex]–

3. maven依賴

pom.xml

<dependencies><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter</artifactId><version>2.6.0</version></dependency><dependency><groupId>org.projectlombok</groupId><artifactId>lombok</artifactId><version>1.16.14</version></dependency>
</dependencies>

4. 流程解析

假設我們要排序的數據是：8, 10, 12, 9, 8, 12, 8

4.1. 計數流程圖

首先我們看看計數統計是什么一回事，計數統計就是把數組中每個元素出現的次數都記錄下來，并

且能夠通過元素找到對應的次數。

4.2. 計數數組變形

那么計數數組變形又是干啥呢？計數數組變形是從第一項開始，每一項都等于它本身和前一項的和，這樣做，得

到的值的意思是當前值前面還有多個數字，比如arr[1]=4,表示當前值前面有4-1=3個數字；arr[2]=5,表示當前值

前面有5-1=4個數字。

4.3. 排序過程

最后我們看下具體是怎么排序的，又我們的數組的值推導得到索引，然后從計數數組中找到應該要排的位置，最

后插入到對應的數組中，這種方式也是一種穩定的排序方式。

4.4. 代碼實現

具體的編碼實現如下，下面的實現方式也是穩定排序的方式。

/*** 計數排序** @param arr* @return*/
public static void countingSort(int[] arr) {if (arr.length == 0) {return;}// 原數組拷貝一份int[] copyArray = Arrays.copyOf(arr, arr.length);// 初始化最大最小值int max = Integer.MIN_VALUE;int min = Integer.MAX_VALUE;// 找出最小值和最大值for (int num : copyArray) {max = Math.max(max, num);min = Math.min(min, num);}// 新開辟一個數組用于統計每個元素的個數(范圍是：最大數-最小數+1)int[] countArray = new int[max - min + 1];// 增強for循環遍歷for (int num : copyArray) {// 加上最小偏差是為了讓最小值索引從0開始，同時可有節省空間，每出現一次數據就加1// 真實值+偏差=索引值countArray[num - min]++;}log.info("countArray的初始值：{}", countArray);// 獲取數組的長度int length = countArray.length;// 計數數組變形，新元素的值是前面元素累加之和的值for (int i = 1; i < length; i++) {countArray[i] = countArray[i] + countArray[i - 1];}log.info("countArray變形后的值：{}", countArray);// 遍歷拷貝數組中的元素，填充到原數組中去，從后往前遍歷for (int j = copyArray.length - 1; j >= 0; j--) {// 數據對應計數數組的索引int countIndex = copyArray[j] - min;// 數組的索引獲取（獲取到的計數數組的值n就是表示當前數據前有n-1個數據,數組從0開始，故當前元素的索引就是n-1）int index = countArray[countIndex] - 1;// 數組中的值直接賦值給原數組arr[index] = copyArray[j];// 計數數組中，對應的統計值減1countArray[countIndex]--;log.info("countArray操作后的值：{}", countArray);}log.info("排列結果的值：{}", arr);}public static void main(String[] args) {int[] arr = new int[]{8, 10, 12, 9, 8, 12, 8};log.info("要排序的初始化數據：{}", arr);//從小到大排序countingSort(arr);log.info("最后排序后的結果：{}", arr);
}

運行結果：

要排序的初始化數據：[8, 10, 12, 9, 8, 12, 8]
countArray的初始值：[3, 1, 1, 0, 2]
countArray變形后的值：[3, 4, 5, 5, 7]
countArray操作后的值：[2, 4, 5, 5, 7]
countArray操作后的值：[2, 4, 5, 5, 6]
countArray操作后的值：[1, 4, 5, 5, 6]
countArray操作后的值：[1, 3, 5, 5, 6]
countArray操作后的值：[1, 3, 5, 5, 5]
countArray操作后的值：[1, 3, 4, 5, 5]
countArray操作后的值：[0, 3, 4, 5, 5]
排列結果的值：[8, 8, 8, 9, 10, 12, 12]
最后排序后的結果：[8, 8, 8, 9, 10, 12, 12]

三、基數排序

1. 什么是基數排序

基數排序：（radix sort）屬于“分配式排序”（distribution sort），又稱“桶子法”（bucket sort）或

bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，從而達到排序

的作用，基數排序法是屬于穩定性的排序。

2. 計數排序 vs 桶排序 vs 基數排序

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

3. 算法步驟

找出待排序的數組中的最大元素max
根據指定的桶數創建桶，本文使用的桶是LinkedList結構
從個位數開始到最高位進行遍歷：num/ divider % 10 = 1，divider 取值為[1,10,100,100,…]
遍歷數組中每一個元素，先進行分類，然后進行收集，分類就是按位放到對應的桶中，比如個位、十位、百位等
（只看指定的位（個位、十位、百位等），如果此位沒有數據則以0填充，比如8，按十位分類，那么就是08，放0號桶）
收集就是把桶的數據取出來放到我們的數組中，完成排序

當然算法也可以對字母類排序，本文主要是對數字排序，大家比較好理解。

4. maven依賴

pom.xml

<dependencies><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter</artifactId><version>2.6.0</version></dependency><dependency><groupId>org.projectlombok</groupId><artifactId>lombok</artifactId><version>1.16.14</version></dependency>
</dependencies>

5. 流程解析

假設我們要排序的數據是：10, 19, 32, 200, 23, 22, 8, 12, 9, 108

5.1. 個位數排序

5.2. 十位數排序

5.3. 百位數排序

6. 代碼實現

/*** 基數排序*/
public static void radixSort(int[] arr) {// 初始化最大值int max = Integer.MIN_VALUE;// 找出最大值for (int num : arr) {max = Math.max(max, num);}// 我們這里是數字，所以初始化10個空間，采用LinkedListLinkedList<Integer>[] list = new LinkedList[10];for (int i = 0; i < 10; i++) {list[i] = new LinkedList<>();// 確定桶的格式為ArrayList}// 個位數：123 / 1 % 10 = 3// 十位數：123 / 10 % 10 = 2// 百位數: 123 / 100 % 10 = 1for (int divider = 1; divider <= max; divider *= 10) {// 分類過程(比如個位、十位、百位等)for (int num : arr) {int no = num / divider % 10;list[no].offer(num);}log.info("分類結果為：{}", Arrays.asList(list));int index = 0; // 遍歷arr原數組// 收集的過程for (LinkedList<Integer> linkedList : list) {while (!linkedList.isEmpty()) {arr[index++] = linkedList.poll();}}log.info("排序后結果為：{}", arr);log.info("---------------------------------");}
}public static void main(String[] args) {int[] arr = {10, 19, 32, 200, 23, 22, 8, 12, 9, 108};log.info("要排序的數據為：{}", arr);radixSort(arr);log.info("基數排序的結果為：{}", arr);
}

運行結果：

要排序的數據為：[10, 19, 32, 200, 23, 22, 8, 12, 9, 108]
分類結果為：[[10, 200], [], [32, 22, 12], [23], [], [], [], [], [8, 108], [19, 9]]
排序后結果為：[10, 200, 32, 22, 12, 23, 8, 108, 19, 9]
---------------------------------
分類結果為：[[200, 8, 108, 9], [10, 12, 19], [22, 23], [32], [], [], [], [], [], []]
排序后結果為：[200, 8, 108, 9, 10, 12, 19, 22, 23, 32]
---------------------------------
分類結果為：[[8, 9, 10, 12, 19, 22, 23, 32], [108], [200], [], [], [], [], [], [], []]
排序后結果為：[8, 9, 10, 12, 19, 22, 23, 32, 108, 200]
---------------------------------
基數排序的結果為：[8, 9, 10, 12, 19, 22, 23, 32, 108, 200]