復雜度

在介紹具體的排序分類之前，先引入時間空間復雜度的概念，這是各個排序算法的應用選擇條件

算法的復雜度是一個函數，一個語句的頻度是指該語句在算法中重復執行的次數時間復雜度是循環執行次數值，次數越多那執行越復雜需要運行時間或占用空間也就越多，所以也用它定量描述算法運行時間或空間的大小，理論上我們運行時間越短空間越小越好，也就是循序執行次數越少也好

常見的時間復雜度并且按照從小到大排序

如果一個數據集的規模是n
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)O(1):表示與元素數量無關，多了少了都一樣為1，這種時間復雜度是最低的
O(logn) :其實有個省略的底數，可以是2可以是10具體情況看待，如每次2分，那就是2，已2為底數的對數向上取整，比如n為10，2^4 > 10 里O(logn)這代表值就是4
O(n):表示與元素數量大小正相關，多少元素執行多少次
O(nlogn) ：算法的運行時間會以n乘以logn的速度增長nlogn的意思是 n * logn，O(nlogn)  = O(n) * O(logn) ，歸并排序就是這個復雜度
O(n^2)：復雜度值與輸入數據大小n的二次方成正比，比如雙重for循環：(n-1)+(n-2)+…+2+1 = n*(n-1)/2  
O(n^3)：復雜度值與輸入數據大小n的三次方成正比，三層for循環：0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6  
O(2^n)：復雜度隨著輸入數據規模 n 的增加呈指數增長

原地排序

原地排序就是指在排序過程中不申請多余的存儲空間，只利用原來存儲待排數據的存儲空間進行比較和交換的數據排序

int[] array = {5,4,3,2,1};
//臨時存儲元素4
int temp = array[1];
//將索引位置2的元素 更新替換掉索引位置1的元素
array[1] = array[2];//在將原索引位置1的元素更新替換掉索引位置2的元素
array[2] = temp;

這種方式 不申請多余的存儲空間，利用原數組的存儲空間進行交互數據，也是一種排序，至于先介紹它是因為后面介紹的排序都用到它

冒泡排序

通過重復地遍歷待排序的列表，比較相鄰的元素并交換它們的位置來實現排序。該算法的名稱來源于較小的元素會像"氣泡"一樣逐漸"浮"到列表的頂端

算法邏輯

它通過不斷交換相鄰的元素將最大（或最小）的元素逐漸“冒泡”到數組的末尾

	// 將數組元素大小按照從小到大排序public static void main(String[] args) {int[] array = {5,4,3,2,1};int count1 = 0;int count2 = 0;int n = array.length;for (int i = 0; i < n - 1; i++) {count1 = count1+1;System.out.println("外循環第"+(i+1)+"次");for (int j = 0; j < n - i - 1; j++) {if (array[j] > array[j + 1]) {count2 = count2+1;// Swap array[j+1] and array[j]int temp = array[j];array[j] = array[j + 1];array[j + 1] = temp;System.out.println("內循環第"+(j+1)+"次"+Arrays.toString(array));}}}System.out.println("外循環總次數:"+count1+"內循環總次數:"+count2+",最終排序數組"+Arrays.toString(array));}

打印輸出

它通過不斷交換相鄰的元素將最大（或最小）的元素逐漸“冒泡”到數組的末尾
外層循環一次就能固定一個元素外循環第1次  					
內循環第1次[4, 5, 3, 2, 1]
內循環第2次[4, 3, 5, 2, 1]
內循環第3次[4, 3, 2, 5, 1]
內循環第4次[4, 3, 2, 1, 5]        (n-1)	
外循環第2次
內循環第1次[3, 4, 2, 1, 5]
內循環第2次[3, 2, 4, 1, 5]
內循環第3次[3, 2, 1, 4, 5]        (n-2)
外循環第3次
內循環第1次[2, 3, 1, 4, 5]
內循環第2次[2, 1, 3, 4, 5]        (n-3)
外循環第4次
內循環第1次[1, 2, 3, 4, 5]        (n-4)
外循環總次數:4內循環總次數:10,最終排序數組[1, 2, 3, 4, 5]最壞情況下就是原數組元素大小順序是和我們需求相反的
需要進行(n-1)+(n-2)+…+2+1 = n*(n-1)/2次比較和交換操作，用時間復雜度表示 是O(n^2)最好的情況就是 int[] array = {1,2,3,4,5}; 原數組順序正好是我們需要的，這種
外循環總次數:4內循環總次數:0,最終排序數組[1, 2, 3, 4, 5] 時間復雜度是(0/n)

每外層循序一次通過相鄰元素兩兩比較并交換，最終確定一個最值的元素 放在末尾
第二次外循環 確定第二個最值元素放在倒數第二位
以此類推 到確定倒數第二個元素，那剩下的一個元素就自然是首位了

索引	0	1	2	3	4
外循環第1次	*	*	*	*	5
外循環第2次	*	*	*	4	5
外循環第3次	*	*	3	4	5
外循環第4次	1	2	3	4	5

冒泡排序的時間復雜度在(0/n) 到 O(n^2) 之間，但(0/n)是極端才有，默認的時間復雜度為O(n^2)
平均時間復雜度：O(n^2)
最壞時間復雜度：O(n^2)
最好時間復雜度：O(n)

時間復雜度：最好O(n)，最壞和平均O(n^2)

什么情況下時間復雜度為(0/n)呢，數組元素順序正好是我們排序需要的順序，比如我們需要正序，數組正好是[1, 2, 3, 4, 5] 這樣正序的，而且還需要優化下排序算法，上面算法復雜度是O(n^2)

    public static void bubbleSort(int arr[]) {// 添加一個是否進行了交互元素的標識boolean didSwap;for(int i = 0, len = arr.length; i < len - 1; i++) {//初始還沒有交互元素 默認flasedidSwap = false;for(int j = 0; j < len - i - 1; j++) {//第一次內循環 n-1次,不斷相鄰位置比較if(arr[j + 1] < arr[j]) {//走到這里證明有需要相互交互的元素 執行了交換swap(arr, j, j + 1);//交換過元素 變更標識 證明了數組調整了 原數組不是正好排序的didSwap = true;}}// 如果標識為false,代表不需要交換元素，原數組正好排序的，那就直接退出if(didSwap == false)return; }}// 原地排序private static void swap(int[] arr, int j, int i) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}

如果int[] arr = {1,2,3,4,5};這樣正序的數組，那么再i=0,然后進行4次內循環之后，就會因didSwap == false觸發return,循環結束，時間復雜度：O(n)，這就是最好也是最極端的情況

冒泡排序:穩定性算法

穩定性是指在排序過程中保持相等元素的相對順序不變。簡單來說，如果一個排序算法能夠保證相等元素的順序相對位置不發生改變，那么它就是穩定的
比如：[5,4,3,3,2] 排序的過程中無論怎么調整
相等的兩個元素3相對位置順序不變；即第一個元素3始終在第二個元素3前面

冒泡排序：冒泡排序是穩定的，因為在比較相鄰元素并交換時，只有當前元素比相鄰元素大才會交換, 相等元素的順序不會發生交換的，這種穩定性在處理具有多個相同鍵值的記錄時十分有用

選擇排序

算法邏輯

先找到最小元素所在位置的索引，然后將該元素與第一位上的元素進行交換

        int[] array = {5,4,3,2,1};int count1 = 0;int count2 = 0;for (int i = 0; i < array.length-1; i++) {int swapIndex = i;//獲取剩余未排序元素最小值的索引值for (int j = i + 1; j < array.length; j++) {if (array[j] < array[swapIndex]) {// 如果在這一步 是兩個比較元素符合條件直接替換 就是冒泡排序了swapIndex = j;}}//獲取到最小元素的索引值不是 不是當前元素的 直接替換if(swapIndex != i){int swapValue = array[i];array[i] = array[swapIndex];array[swapIndex] = swapValue;}System.out.println("外循環第"+(i+1)+"次變更后"+Arrays.toString(array));}

打印輸出

外循環第1次變更后[1, 4, 3, 2, 5]第1次外循環:內循環4次得最小元素，并根據索引替換第一個元素
外循環第2次變更后[1, 2, 3, 4, 5]第2次外循環:內循環3次得剩余最小的元素，并根據索引替換第二個元素
外循環第3次變更后[1, 2, 3, 4, 5]第3次外循環:內循環2次得剩余最小的元素，并根據索引替換第三個元素
外循環第4次變更后[1, 2, 3, 4, 5]第4次外循環:內循環1次得剩余最小的元素，并根據索引替換第四個元素
外循環總次數:4 內循環總次數:10,最終排序數組[1, 2, 3, 4, 5]

處理邏輯是

索引	0	1	2	3	4
外循環第1次	確定
外循環第2次	確定	確定
外循環第3次	確定	確定	確定
外循環第4次	確定	確定	確定	確定

選擇排序：按照空間順序，每次從未排序的序列中 通過遍歷比較確定，選擇一個元素 替換到當前待確認的空間

和冒泡排序相似地方在于，每次外循環一次都能確定一個最值
區別就在于：
冒泡排序每次內循環符合條件的都有交換一次(可能需要多次交換元素)，最多替換值次數是O(n^2)
選擇排序內循環上只獲取最值的索引值，在外層循環里交換值(每次外循環交換一次)，最多替換值次數是n-1

這樣看其實選擇排序是冒泡排序的優化后的排序,雖然兩者時間復雜度看似一樣，但實際應用中選擇使用選擇排序的比較多，因為選擇排序的交換次數較少，通常比冒泡排序更快

時間復雜度：最好，最壞和平均都是O(n^2)

時間復雜度上
平均時間復雜度：O(n^2)
最壞時間復雜度：O(n^2)
最好時間復雜度：O(n^2)

正如這個邏輯圖所示，n為5

索引	0	1	2	3	4
元素	1	2	3	4	5
外循環第1次	確定1
外循環第2次	確定1	確定2
外循環第3次	確定1	確定2	確定3
外循環第4次	確定1	確定2	確定3	確定4	余下的5

第1次外循環，內循環n-1
第2次外循環，內循環n-2
第3次外循環，內循環n-3
第4次外循環，內循環n-4
需要進行(n-1)+(n-2)+…+2+1 = n*(n-1)/2次，用時間復雜度表示 是O(n^2)
最好情況下 數組順序正好是排序的，就是上面展示 的數組元素樣式，但依然需要 n*(n-1)/2次

選擇排序:不穩定性算法

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

選擇排序在交換過程中可能會改變相同元素間的原始順序
在一趟選擇，如果一個元素比當前元素小，而該小的元素又出現在一個和當前元素相等的元素后面，那么交換后穩定性就被破壞了

比如序列arr = [5 8 5 2 9]，第一遍選擇中第1個元素5會和2交換，
數組變成arr = [2 8 5 5 9]，兩個相對元素5相對先后順序變化了，所以選擇排序是非穩定的

插入排序

算法邏輯

通過構建有序序列，對于未排序的數據，在已排序序列中從后向前掃描，找到相應位置并插入，工作原理類似于整理撲克牌

        int[] array = {5,4,3,2,1};for (int i = 1; i < array.length; i++) {for (int j = i; j > 0; j--) {//不斷和有序列表元素比較大的放后面if (array[j - 1] > array[j]) {int tmp = array[j - 1];array[j - 1] = array[j];array[j] = tmp;}}}}

打印輸出

外循環第1次  					第2個元素和第1個元素比較，符合條件替換
內循環第1次[4, 5, 3, 2, 1]
外循環第2次						第3個元素和前2個元素比較，符合條件替換
內循環第1次[4, 3, 5, 2, 1]
內循環第2次[3, 4, 5, 2, 1]
外循環第3次						第4個元素和前3個元素比較，符合條件替換
內循環第1次[3, 4, 2, 5, 1]
內循環第2次[3, 2, 4, 5, 1]
內循環第3次[2, 3, 4, 5, 1]
外循環第4次						第5個元素和前4個元素比較，符合條件替換
內循環第1次[2, 3, 4, 1, 5]
內循環第2次[2, 3, 1, 4, 5]
內循環第3次[2, 1, 3, 4, 5]
內循環第4次[1, 2, 3, 4, 5]
外循環總次數:4內循環總次數:10,最終排序數組[1, 2, 3, 4, 5]外層循環標識并決定待比較的數值
內層循環為待比較數值確定其最終位置

和上面的排序的區別在于:
冒泡排序每次外循序將一個數歸位，將最值元素放入合適的對應位置
選擇排序每次外循環能確定一個索引位置 選擇了哪個元素

而直接插入排序每次外循環確定的是一個有序列表，這個有序列表每次外循序一次 增加一個元素到這個有序表

第一次外循環 比較索引1的值和首的值大小并決定是否交換，后面的元素內容不管的，著就相當于把原數組切割，相當于得到一個有序數組{4，5} 和 剩余待管理的數組{x,x,x}

索引	0	1	2	3	4
外循環第1次	4	5	*	*	*

第二次循環，從剩余待管理數組{x,x,x}按照順序取一個元素和有序數組{4，5}里面的元素比較并直接插入合適的位置，相當于得到一個有序數組{3，4，5} 和 剩余待管理的數組{x,x,x}，然后依次類推

索引	0	1	2	3	4
外循環第1次	3	4	5	*	*

該算法設計亮點之一在于利用了數組元素在存儲空間的聯系性，原數組切割后有序列表和未管理列表總空間大小還是原數組空間，未管理列表拿出以為元素相當于空間減少1 對于的有序列表空間加1

時間復雜度：最好O(n)，最壞和平均O(n^2)

上面的邏輯步驟里面 隨著有序列表越長，內循環次數越多,最壞的情況就是數組順序完全是相反的

原始數組 [5, 4, 3, 2, 1]外循環第1次:確定有序列表[4, 5, *, *, *] 內循環1一次:n-4
外循環第2次:確定有序列表[3, 4, 5, *, *] 內循環2一次:n-3
外循環第3次:確定有序列表[2, 3, 4, 5, *] 內循環3一次:n-2
外循環第4次:確定有序列表[1, 2, 3, 4, 5] 內循環4一次:n-1
需要進行(n-1)+(n-2)+…+2+1 = n*(n-1)/2次，用時間復雜度表示 是O(n^2)

上面的展示代碼就是最壞情況，時間復雜度就是O(n^2)

那最好的情況下數組順序正好是正序的，原始數組 [1, 2, 3, 4, 5]，但是需要調整一步算法邏輯：
調整的插入排序算法加強點在于:利用已知序列表的排序性,邏輯解讀:

原始數組 [1，3，5，4，6，8]按正序
第一次外循環
第一個元素和第二個元素比較并確定長度為2的有序列表
得到一個有序數組{1，3} 和 剩余待管理的數組{x,x,x,x}第二次外循環
第三個元素5和有序列表元素{1，3}比較
這里就利用已知序列表的排序性,有序列表已經排序了，最后元素也是最大的是3
拿元素5和元素3比較，如果比元素3大，那有序列表前面的元素一定都比該元素小的，就不用比了
得到一個有序數組{1,3,5} 和 剩余待管理的數組{x,x,x}第三次外循環
第四個元素4和有序列表元素{1，3，5}比較
拿元素4和元素5比，結果比元素5小，交換兩者位置
然后繼續往前比
拿元素4和元素3比，結果比元素3大，好，前面的都不用再比了循序上面步驟直到外層循序結束，那這里看下時間復雜度
外層循序總共次數n-1次，這個省不掉的外層循序對應的內層循環里，每次最理想的情況就是，待比較的元素比有序列表的最后元素大，
這樣外層循序里的比較次數就是1，那這種情況下的總的時間復雜度就是n-1就是O(n)

這種思路對應的代碼:

    public static void main(String[] args) {int[] array = {1,2,3,4,5};int i, j;int temp;//外層循序從未知排序列表開始for (i = 1; i < array.length; i++) {//未知排序列表第一個元素，準備往有序列表插入的元素temp = array[i];j = i - 1;/**待插入的元素 和有序列表從后往前順序開始比較大小*不滿足j>=0 && array[j] > array[i] 的兩種情況* 1.有序列表從后往前遍歷到頭了結束這次循環* 2.array[j] < array[i]找到合適插入的位置了*/for (;j>=0 && array[j] > array[i];j-=1){//插入的位置不符合要求，有序列表的元素往后移array[j + 1] = array[j];j--;}//待插入的元素插入到合適位置array[j + 1] = temp;}        

所以直接插入排序復雜度在(0/n) 到 O(n^2) 之間，但(0/n)也是極端下才有，這段展示代碼時間復雜度就是O(n) ，默認的平均時間復雜度為O(n^2)
平均時間復雜度：O(n^2)
最壞時間復雜度：O(n^2)
最好時間復雜度：O(n)：正好數組的順序就是我們需要的排序，而且優化算法

插入排序:穩定性算法

插入排序：插入排序是穩定的，因為插入時只有當前元素比前面的元素小才會插入，并且插入位置是有序區的最后一個位置

比如數組序列arr = [1,3,2,2]
第一次排序后變化 [1,2,3,2]
第二次排序后變化 [1,2,2,3]
相對元素2的相對順序沒有變化，原來在前面的元素2還是在前面

希爾排序

插入排序每次移動比較的是1位，希爾排序是插入排序的高效改進版本，通過引入“增量gap”分組來預處理數據，使得元素可以一次移動多位，從而減少總的移動次數和后續插入排序的工作量

邏輯步驟

1.選擇增量序列gap:
增量序列的選擇對希爾排序的性能至關重要。常見的增量序列有：

• 希爾原始序列：gap = n/2, n/4, ..., 1
• Hibbard序列：1, 3, 7, ..., 2^k-1
• Sedgewick序列：1, 5, 19, 41, ...（由9×4^k - 9×2^k +1或4^k - 3×2^k +1組成）

2.按增量分組對每個子序列 進行插入排序操作：
區別于直接插入排序，每次都是從未排序的數組排序選擇出最值插入到有序區間，這樣相當于每次增量都是1。希爾排序通過增量序列值，每次都是“跳著”選擇排序的空間，比如gap = n/2

初始數組: [8, 3, 5, 1, 4, 2, 7, 6]0  1  2  3  4  5  6  7
gap=4:增量分組 
Group1: [8, 4]    -> 排序后虛擬數組: [4, 8]
Group2: [3, 2]    -> 排序后虛擬數組: [2, 3]
Group3: [5, 7]    -> 排序后虛擬數組: [5, 7]
Group4: [1, 6]    -> 排序后虛擬數組: [1, 6]
這樣的好處在于
每個虛擬數組的首位都是最值，最終排序數組的首位的最值也從這些總序列數組產生
同樣第二個最值也從各自排序后子序列中的第二位產生，這樣豎著合并起來
第一次合并[4, 2, 5, 1, 8, 3, 7, 6]縮小增量繼續排序（gap = 2）分組:
當前數組[4, 2, 5, 1, 8, 3, 7, 6]
對應索引:0  1  2  3  4  5  6  7
Group1: [4, 5, 8, 7] -> 排序后: [4, 5, 7, 8]
Group2: [2, 1, 3, 6] -> 排序后: [1, 2, 3, 6]
第二次合并[4, 1, 5, 2, 7, 3, 8, 6]縮小增量繼續排序（gap = 1）：最終插入排序
執行標準插入排序:
[4, 1, 5, 2, 7, 3, 8, 6] 
第一次→ [1, 4, 5, 2, 7, 3, 8, 6]
第二次→ [1, 4, 5, 2, 7, 3, 8, 6]
第三次→ [1, 2, 4, 5,7, 3, 8, 6]
直到完成最終排序
→ [1, 2, 3, 4, 5, 6, 7, 8] (完成)

下面已希爾原始序列gap(每次減半)為例 代碼展示

    public static void shellSort(int[] arr) {int n = arr.length;//初始增量序列設為數組長度的一半，逐步縮小增量直到gap為1for (int gap = n/2; gap > 0; gap /= 2) {// 對每個子序列進行插入排序（從gap開始）subsequenceShort(array,n,gap);}}

進入每個子序列進行插入排序subsequenceShort方法

    private static void subsequenceShort(int[] array,int n, int gap) {//開始位置從每次增量分組索引位置開始for (int i = gap; i < n; i++) {// 當前待插入變量元素array[gap]int temp = array[i]; int j;// 對以gap為間隔的子序列進行插入排序,將比temp大的元素向前移動 交換for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {array[j] = array[j - gap];}// 插入到正確位置array[j] = temp;}}

這段代碼眼熟嗎，和上面插入排序優化時間復雜度算法里的一樣，只是插入排序每次移動單位是1，這里替換成了增量序列gap

時間復雜度

如果按照上面每次已一半為增量序列
gap = gap/2 初始gap= n/2
那么最外層的循環次數，就是底數為2的時間復雜度O(logn)

對于每個增量的內層循環，就是一個插入排序
平均時間復雜度：O(n^2)
最壞時間復雜度：O(n^2)
最好時間復雜度：O(n)：

所以總體時間復雜度
最好的情況就是O(n) * O(logn) = O(nlogn),

最壞的情況gao增量設置為1的定量，這時候的希爾排序就完全退化成了退化排序，那最壞的情況下的時間復雜度就完全取決于插入排序的最壞時間復雜度O(n^2)

所以希爾排序的時間復雜度的范圍空間在O(nlogn)~O(n^2)

主要取決于
1.增量系列的選擇，比如每次是一半 還是三分之一 還是4分之一
2.子序列的有序性：根據增量序列的子序列排序性狀況越好，對應的時間復雜度越低

不同增量序列的時間復雜度
{1, 2, 4, 8, …}：這種序列的時間復雜度在最壞情況下是O(n^2)。
{1, 3, 7, …, 2^k-1}： 這種序列的時間復雜度在最壞情況下是O(n^1.5)。
{1, 5, 19, 41, 109, …}：這種序列的時間復雜度在最壞情況下可以達到O(n^1.3)

雖然看著希爾排序的時間復雜度好像還不如插入排序，但是對應中等規模的數據處理上是比較快速的

希爾排序：不穩定算法

希爾排序不是穩定性的算法，雖然是插入排序的改進，原有就在于增量序列的跳這比對

初始數組: [1, 3, 3, 2]，初始增量gap = n/2
對應元素：a b c d 表示
gap=2:增量分組
Group1: [1, 3] -> 排序后虛擬數組: [1, 3] 這里的元素是[a, c]
Group2: [3, 2] -> 排序后虛擬數組: [2, 3]這里的元素是[d, b]
第一次合并[1, 2, 3, 3]對應元素是[a,d,c, b] 這里 bc兩個相等元素的相對順序變化了
所以希爾排序不是穩定算法

快速排序

快速排序：采用分區治理策略。基本思想是選一個元素作為基準（pivot），將數組分成兩部分，使得左邊部分的元素都小于等于基準，右邊部分的元素都大于等于基準，然后遞歸地對左右兩部分進行排序

步驟邏輯

快速排序步驟
1.選擇基準（pivot）:數組中隨機選一個元素,一般選首尾或者最中間位置的(這樣好比較，移動不亂)
2.分區（Partition）：將數組分成兩部分 左邊元素都小于基準元素值5 右邊元素都大于基準元素5

 public static void main(String[] args) {//定義一個亂序的數組int[] arr = {4,6,7,9,8,1,3,5};int head = 0;int tail = arr.length-1;// 進入自定義快速排序方法進行排序quickSort(arr,head,tail);System.out.println(Arrays.toString(arr));
}
// 進入到自定義的快速排序的方法
private static void quickSort(int[] arr, int head, int tail) {// 先判斷待排序的數組是否有效存在,比如就head = tail 就一個元素的不用排序了if (arr == null || arr.length == 0) return;if( head>= tail) return;//隨選基準值：這里選擇最后一個元素作為基準int pivot = arr[tail];  //定義一個小于基準的左子數組末尾索引值 int i = head - 1;       for (int j = head; j < tail; j++) {// 當前元素 <= 基準時，將其交換到左側if (arr[j] <= pivot) {i++;//當前索引位置j的元素和 左子數組末尾元素后一位置元素交互//即左子數組擴容新增一位，后面預留的右子數組少一位，總體空間不變if(i==j)continue;//如果相互交互的兩個元素是同一個元素 跳過swap(arr, i, j);}}//上面都交互完了，那么這時候將基準放到正確位置swap(arr, i + 1, tail);// 記錄下現在基準索引的值pivot =  i + 1;  }//指定索引位置的元素相互交互private static void swap(int[] arr, int i, int j) {if(i == j) return;int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}

代碼到這里就是分區的步驟邏輯，分區過程如下

原數組 [4, 6, 7, 9, 8, 1, 3, 5]，基準選擇末尾元素5，這個時候的分區數組其實相當于
左子數組 		右子數組
[還沒有元素		4, 6, 7, 9, 8, 1, 3, 5]  
理論上現在左子數組的末尾索引在元素4的前一位，
即左子數組 末尾索引 = 元素4索引 - 1 代碼表示就是int i = head-1開始移動分區元素
第一次循環：基準和第一個元素4比較 符合在左子數組條件 
將元素4和左子數組末尾索引后一位的元素進行交換 只是這里正好是同一個索引位置元素
左子數組 		右子數組
[4, 		     6, 7, 9, 8, 1, 3, 5]
現在左子數組里面有一個元素了，末尾索引值變為0了第二次循環：基準和第2個元素6比較 不符合在左子數組條件 跳過交互 開始下次循環
第三次循環：基準和第3個元素7比較 不符合在左子數組條件 跳過交互 開始下次循環
第四次循環：基準和第4個元素9比較 不符合在左子數組條件 跳過交互 開始下次循環
第五次循環：基準和第5個元素8比較 不符合在左子數組條件 跳過交互 開始下次循環第六次循環：基準和第6個元素1比較 符合在左子數組條件，現在左子數組末尾索引值為0
將元素1和 左子數組的末尾元素的后一位元素交換，即和索引位0+1=1位置的元素交互
左子數組 		右子數組
[4, 1,          7, 9, 8, 6, 3, 5]
現在左子數組里面有兩個元素了，末尾索引值變為1了第七次循環：基準和第7個元素3比較 符合在左子數組條件，現在左子數組末尾索引值為1
將元素3和 左子數組的末尾元素的后一位元素交換，即和索引位1+1=2位置的元素交互
左子數組 		右子數組
[4, 1, 3,         9, 8, 6, 7, 5]
現在左子數組里面有三個元素了，末尾索引值變為2了到這里循環就結束了，然后左右子數組都分好了，但基準還在右子數組里面，
把基準元素5 挪到左右子數組中間，現在左子數組末尾索引值為2
方法就是將基準元素5和 左子數組的末尾元素的后一位元素交換，即和索引位2+1=3位置的元素交互
左子數組 	 基準	右子數組
[4, 1, 3,    5,     8, 6, 7,9]
到這里第一次分區結束,保證已選擇的基準值為標準，左變都比基準值小，右邊都比基準值大

2.遞歸排序：對左右子數組遞歸執行相同操作
上面分區后得到是左子數組都比基準值小,右子數組都比基準大，但左右子數組還是亂序呢

左子數組 	 基準	右子數組
[4, 1, 3,    5,     8, 6, 7,9]

處理的方式就是把左右子數組各看成一個數組，只是右子數組的起始索引不是0而已，還和上面的分區操作一樣繼續操作左右子數組

		//上面我們代碼理我們保留的基準現在的索引位置pivot =  i + 1;  // 遞歸排序左子數組 從左子數組的首位為到末尾元素(基準值元素前一位) 進行分區遞歸quickSort(arr, head, pivot - 1);// 遞歸排序右子數組 從基準值元素后一位的右邊子數組 進行分區遞歸quickSort(arr, pivot + 1, tail);

處理邏輯步驟
Ⅰ.處理左子數組

左子數組 	 基準	右子數組
[4, 1, 3,    5,     8, 6, 7,9]左子數組[4, 1, 3] 索引值0，1 ，2 按照上面的分區步驟 得到一個分區數組
左子數組 	 二次基準值 	右子數組
[1,             3,                     4]
然后就分不動了 左子數組遞歸也就結束了,分區的左側區域也就治理好了
==================================================================左子數組  基準值		右子數組
已排序的區域:[1, 3, 4,   5,        
未排序的區域:					   8, 6, 7,9]

Ⅱ.處理右子數組

右子數組[ 8, 6, 7,9] 索引值4，5 ，6，7 按照上面的分區步驟 基準值用末尾元素9
第一次
左子數組 		右子數組
[ 8,             6, 7,9]第二次
左子數組 		右子數組
[ 8, 6,          7,9]第三次
左子數組 		右子數組
[ 8, 6, 7,       9]然后調整基準值位置
左子數組 		基準值      右子數組
[ 8, 6, 7,       9                ]
右子樹組第一次遞歸也就結束了，到這里
已排序的區域:[1, 3, 4,   5,       	 ,9]	
未排序的區域:					  8, 6, 7	
================================================================
然后繼續遞歸按照上面的步驟執行未排序區域 8, 6, 7 ]最終于排序完成

總結快速排序的步驟邏輯

這就是整個的分區治理的策略的概念，一分二，二分四，四分八 等，直到分不下去的時候，也就排好序列了
一分二 一個基準元素(相當于插眼一個點) 兩塊區域
二分四 又多了兩個基準元素(又查驗兩個點) 四塊區域
.....直到分不下去了
這些基準值的點占據的位置就正好是整個數組的全部空間(點連成線)，此時排序完成

時間復雜度：最好：O(nlog2n)，平均：O(nlog2n)，最壞：O(n^2)

快速排序的時間復雜度
每次分區域成2份 就相當于除以2，雖然得到的不一定是大小相同的區域(不是平均切割的哦)，那這里的時間復雜度理論上應該就是能除以2多少次，即 O(logn)：已2為底數的對數

切割后的區域里面有循環進行比較然后決定是否交互，這里的時間復雜度應該是O(n)

所以理論上的時間復雜度是：O(logn) * O(n) = O(nlogn)，當然極端情況下時間復雜度會多點，比如最壞情況下，每次選擇的基準元素都是當前子數組中的最小或最大元素，這樣每次分區都相于沒分，其中一個子數組和原數組一樣，遞歸調用就變成了類似for循序的作用，在加上分區比較的for循序，就是雙層for循環了，這樣的快速排序實際上退化成了冒泡排序或選擇排序，時間復雜度變為O(n^2)

快速排序的性能很大程度上取決于選擇的基準元素（pivot），基于基準元素的每次分區能越均衡，整體時間復雜度越小，這里不進行介紹更優化的分區方法，只是了解快速排序的邏輯步驟
平均時間復雜度：O(nlog2n)
最壞時間復雜度：O(n^2)
最好時間復雜度：O(nlog2n)

當然Java數組快速排序最簡單是是可以使用Java內置的Arrays.sort()方法

    int[] array = {5,4,3,2,1};//調用排序方法Arrays.sort(arr1);

Arrays.sort()方法默認使用的是快速排序算法，但在某些情況下可能會退化為歸并排序

快速排序：不穩定算法

快速排序：分區時可能改變相等元素順序

先說一下快速排序的幾種分區方式
1.單方向掃描分區:Lomuto洛穆托 分區方法就是，常用方式以最后一個元素為基準的選擇
2.雙向掃描分區:Hoare霍爾 分區方法也是原始分區方式，左右兩邊同時開始
3.三指針掃描分區：和基準的元素相同的元素劃出成一個區間，左區間小于基準，右邊區間大于基準

先看Lomuto分區方式的穩定性，選第一個元素為基準，從左向右遍歷
情況Ⅰ:和基準值相同的元素的順序

示例數組[3a, 2, 4, 3b, 1]其中有兩個相等的元素3（用3a和3b區分，3a表示第一個3，3b表示第二個3）
基準值(pivot) = 3a (第一個元素)，交換移動條件是arr[j] <= pivot 就將其移動到左邊
[3a, 2, 4, 3b, 1]0   1  2  3   4
從索引位置j = 1開始 從左到右遍歷到最后一個元素 
j=1 元素2（<3a）-> 真，交換arr[1]和arr[1] 后數組：[3a, 2, 4, 3b, 1]
j=2：元素4（<=3a）-> 否，不交換，數組不變。繼續。
j=3：元素3b（<=3a)-> 真 交換arr[2]和arr[3] 后數組：[3a, 2, 3b, 4, 1]
j=3：元素1（<=3a)-> 真 交換arr[3]和arr[4] 后數組：[3a, 2, 3b, 1, 4]
此時遍歷結束，分區 左右序列2, 3b, 1 和 4注意最后一步，將基準值（索引0）與左側序列末尾元素1（索引3）對調
得到：[1, 2, 3b, 3a, 4] 原數組是3a在前3b在后，現在相對順序改變了，
所以得出非穩定性，這個舉例出現非穩定性的情況是因為：
選擇第一個元素為基準值，如果后面元素有和基準值相同的元素在移動到左序列時候，在最后一步替換基準值位置到左序列末尾，這樣一定會出現相等元素相對順序改變的情況解決方案：
1.如果選擇的是第一個元素作基準值，在Lomuto分區中，一般將相等元素放在右側，不放在左側
j=3：元素3b（<=3a)-> 真 這步條件里 <=改成 < 條件2.更簡單，按照Lomuto分區選擇末尾元素，還使用<=這個條件，這樣如果有和基準相等的元素放在左序列，最后基準值調換到左序列末尾，一定在還在原來相等元素的后面

情況Ⅰ:在排序后的左序列末尾元素有相等元素

示例數組[3, 2a, 1, 2b]這里基準值選第一個元素3，從索引位置j = 1開始 從左到右遍歷
j=1 元素2a <3 -> 真，交換arr[1]和arr[1] 后數組不變：[3, 2a, 1, 2b]
j=2：元素1 <3 -> 真，交換arr[2]和arr[2] 后數組不變：[3, 2a, 1, 2b]
j=3：元素2a <3-> 真，交換arr[3]和arr[3] 后數組不變：[3, 2a, 1, 2b]
遍歷結束，將基準值（索引0）與左側序列末尾元素2b（索引3）對調,嗚呼
[2b, 2a, 1, 3] 元素2a 和 2b的先后順序改變了,不穩定性體現了這兩個例子都能看出，在最后一步替換基準值和左序列末尾時候，相同元素相對順序變化的不可控
這就是不穩定的表現

再看Hoare霍爾分區方式的穩定性
Hoare分區的邏輯及特性
1.已雙向指針left和right 分別從兩端開始指針掃描
2.區別單向掃描的分區最后已基準值作樞軸，雙向掃描最后已左右指針做區分左右序列，遞歸調用時候選擇右指針做分區索引

數組[3, 7, 8, 5, 2, 1, 9, 4]為例，選擇第一個元素 3 作為基準值 (pivot = 3)
索引 0  1  2  3  4  5  6  7左邊指針left	 已首位 索引位置0開始，從左到右順序遍歷，不符合指針移動條件時 指針移動"停"
右邊指針right 已末尾 索引位置7開始，從右到做順序遍歷，不符合指針移動條件時 指針移動"停"
注意:內層循環 指針移動條件 使用嚴格比較 (左循環使用< 和 右循環>)，不能使用<= 和>= 
主要是為了遍歷時遇到和基準元素相同的元素時停止移動。這對于正確分區和避免死鎖至關重要
不使用嚴格比較可能會出現越界異常，無法正確異常 比如[4,3,2,1] left直接越界了
死鎖(無限循環)主要會由于遞歸引起 這兩點下面講第一次掃描交換
此時left = 0 (值 3), right = 7 (值 4)
內左循環：arr[0] (3) < pivot (3)->否 不符合移動條件 -> 停。此時left=0(值 3)
內右循環:arr[7] (4) > pivot (3)->真 符合移動條件 ->往前移動指針 right-1 =6(值 9) arr[6] (9) > pivot (3)->真 符合移動條件 ->往前移動指針 right-1 =5(值 1) arr[5] (1) > pivot (3)->否 不符合移動條件 -> 停。此時right=5(值 1)
左指針停下的位置表明該元素不符合在左序標準，應該呆在右序
右指針停下的位置表明該元素不符合在右序標準，應該呆在左序先進行左右指針交叉或相遇判斷 if left >= right-->不成立
好的 兩者進行元素交換 -> 交換 arr[0] (3) 和 arr[5] (1) -->交換元素后左右指針各移1位
-> 數組變為 [1, 7, 8, 5, 2, 3, 9, 4]
此時左右指針	L			   R
移動左右指針	   L		R
左半部分也就是左指針左側： 所有元素 小于或等于 基準
右半部分也就是右指針右側： 所有元素 大于或等于 基準
==============================================================================
第二次掃描，繼續縮小范圍
此時left = 1 (值 7), right = 4 (值 2)
內左循環：arr[1] (7) < 3 ->否 不符合移動條件 -> 停。此時left=1(值 7)
內右循環：arr[4] (2) > 3 ->否 不符合移動條件 -> 停。此時right=4(值 2)
左右指針交叉或相遇判斷 if left >= right-->不成立
兩者進行元素交換 -> 交換 arr[1] (7) 和 arr[4] (2) 
-> 數組變為 [1, 2, 8, 5, 7, 3, 9, 4]
此時左右指針	   L		R
此時左右指針	      L	 R
==============================================================================
第三次掃描
此時left = 2 (值 8), right = 3 (值 5)
內左循環：arr[2] (8) < 3 -> 否 不符合移動條件 -> 停。此時left=2(值 8)
內右循環：arr[3] (5) > 3 -> 真 符合移動條件 ->往前移動指針 right-1 =2(值 8) arr[2] (8) > 3 -> 真 符合移動條件 ->往前移動指針 right-1 =1(值 2) arr[1] (2) > 3 -> 否 不符合移動條件 -> 停。此時right=1(值 2)
然后左右指針 left >= right-->成立--> 返回right =1(值 2) 值 跳出循環，此時左指針left = 2分區結果：[1, 2, 8, 5, 7, 3, 9, 4] left =2 right = 1
左分區 (索引 0 到 2): [1,2,8] -> 1 2都小于基準(樞軸)3 但8好像不符合
右分區 (索引 1 到 7): [2,8,5,7,3,9,4] -> 基準(樞軸)3 為什么放在右邊序列里面了這里揭示了 Hoare 分區的一個重要特性：
它不保證分區點左邊的元素都嚴格 <= 樞軸，或者右邊的都嚴格 >= 樞軸。它的保證是：在分區完成時
left 指針左邊的所有元素（不包括 left 本身）都 <= 樞軸()。
right 指針右邊的所有元素（不包括 right 本身）都 >= 樞軸。分區點 right 是劃分兩個區域的邊界索引之一（另一個是 left)

看完邏輯步驟三個問題
1.為什么內層循環指針移動條件使用嚴格比較 (左循環使用< 和 右循環>)？
2.為什么在分區結果左序列中會存在元素比基準值大的？
3.為什么基準值會放在序列中，而不是替換位置放在左右分區中間？

延申的有點多了，但是不把這些疑問解釋清除是不好理解霍爾分區的特性，上代碼

    public static void main(String[] args) {int[] arr = {3, 7, 8, 5, 2, 1, 9, 4};//進入快速分區方法quickSort(arr, 0, arr.length - 1);}public static void quickSort(int[] arr, int low, int high) {//判斷待分區的序列是否為有效數組空間if (low < high) {//返回上次分區的右指針作為分區索引int pi = partition(arr, low, high);//遞歸左序分區空間(low 到 pi)quickSort(arr, low, pi);//遞歸右序分區空間(pi+1 到 high)quickSort(arr, pi + 1, high);}}//霍爾分區方法private static int partition(int[] arr, int low, int high) {int pivot = arr[low];  // 選擇第一個元素作為樞軸int left = low;        // 初始化左指針 (實際會立即右移)int right = high;      // 初始化右指針while (true){// 無限循環，內部檢查退出條件// 移動左指針，找到 >= pivot 的元素while (arr[left] < pivot){// 注意：嚴格小于才移動left = left + 1;}// 移動右指針，找到 <= pivot 的元素while (arr[right] > pivot){// 注意：嚴格大于才移動right = right - 1;}// 檢查指針是否相遇或交叉if (left >= right) return right;// 返回分區點// 交換左右指針指向的元素swap(arr[left], arr[right]);// 移動指針繼續掃描 (避免死鎖，尤其是元素等于pivot時)left = left + 1;right = right - 1;}}

這段代碼是一個霍爾分區的遞歸調用，解釋一下上面的問題
1.為什么在分區結果左序列中會存在元素比基準值大的？
這是因為左右指針是作為 分區邊界線 用的 比如

分區結果：[1, 2, 8, 5, 7, 3, 9, 4]  right = 1
左分區 (索引 0 到 2): [1,2,8] -> 1 2都小于基準(樞軸)3 但8好像不符合
右分區 (索引 1 到 7): [2,8,5,7,3,9,4] -> 元素2不符合，而且基準(樞軸)3 為什么放在右邊序列里面了這里是內層循環 指針移動條件 使用嚴格比較 (左循環使用< 和 右循環>)的好處之一
任何一個不等于基準元素的值 是不可能同時滿足 < 和 >嚴格條件
它必然會讓左右指針雙方一方移動，一方停下
這樣符合left >right條件的情況就是left = right+1，左右序列交互的元素個數最多是2個
而且這兩個元素必然按照順序排序好的如果是left = right 滿足，那代表左右指針指向同一個元素，而且這個元素必然是和基準元素相同的元素
此時左右序列交互的元素數量是一個以上這兩種情況表示存在交互數據，那么在遞歸調用之后，交互范圍的元素不可能同時給兩邊處理
只能歸屬一方，要么歸左邊 要么歸右邊，不然數據就重復了這里的處理方式就是講交互范圍的元素 
已右指針作為分區索引切割劃分
[1, 2, 8, 5, 7, 3, 9, 4]  R
位置小于等于R的 屬于真正意義上的左半部分
位置大于R 屬于真正意義上的右半部分：那么此時R指針數據是不算真正的右半部分
==============================================================
如果已左指針作為分區索引切割劃分
[1, 2, 8, 5, 7, 3, 9, 4]  L
位置小于L的 屬于真正意義上的左半部分
位置大于等于L 屬于真正意義上的右半部分常見方式是已右指針作為分區索引方式
==============================================================
這里也就是Hoare 分區的一個重要特性在重申一下：
它不保證分區點左邊的元素都嚴格 <= 樞軸，或者右邊的都嚴格 >= 樞軸。它的保證是：在分區完成時
left 指針左邊的所有元素（不包括 left 本身）都 <= 樞軸()。
right 指針右邊的所有元素（不包括 right 本身）都 >= 樞軸。分區點 right 是劃分兩個區域的邊界索引之一（另一個是 left)

2.為什么在分區結果左序列中會存在元素比基準值大的？
個人認為的幾點原因
a.穩定性，在上面單向掃描最后替換基準值的不可控制相對順序，從而破壞穩定性

b.簡化算法，單向掃描最后替換基準值是選擇基準值是一個分區標準，最后分區后使用指針作為分區索引，就不用特意在替換基準值并作為分區索引了，使用基準值分區索引意義沒必要了
c.算法的平衡，基準值放在左邊序列那一定是當前序列最大值，基準值放在右邊序列一定是右邊序列的最小值
在快速排序的邏輯步驟講解里，每次分區左右序列越均衡越好,這和隨機選則的基準值有很大關系，應使用"三數取中"法取基準值的(隨機三個元素 排序取中間值那個元素作基準值)，如果分區后左右一側元素為空極度失衡不好，這里基準值放在子序列中有點配重意思，基準值停留在子序列中為了均衡下次分區

作用體現:遞歸子序列分區，如上面例子[8,5,7,3,9,4]，無論基準值選哪個，左邊序列一定有元素3，這樣能保證左邊序列不為空，保證該分區算法不會失衡

3.為什么內層循環指針移動條件使用嚴格比較 (左使用< 和 右循環>)
a.保證正確分區：[18,5,7,3,9,4]，選擇第一個18作為基準，恰巧是最大值，如果使用<=

            while (arr[left] <= pivot){//在比對元素4之后 再后移動,arr[6]越界報錯了left = left + 1;}//發生越界異常，程序都報錯終止了 還談什么能正常分區

b.放在死鎖(無線循環):發生再遞歸調用中

			//為了放在報錯 我們加上邊界限制while (left<=arr.length-1 && arr[left] <= pivot){left = left + 1;}while (right>=0 &&arr[right] >= pivot){right = right - 1;}if (left >= right) return right;

會再遞歸調用出現無限循環

比如數組[3,3,3] 
執行分區
quickSort(arr, 0, 2); 
這樣左邊指針會一直指完整個數組，最后left = arr.length
右指針這樣也會一直指完整個數組，最后right = -1[3,3,3] 
左序列 			L
右序列 	R 0 1 2
也就是整個數組既然成左序列 又成右序列然后遞歸，左版本分L>arr.length 不執行分區方法了，
但右半部分符合，開始分區執行，輸入參數
quickSort(arr, pi + 1, high); == quickSort(arr, 0, 2); 就這樣遞歸循環下去吧，直到堆棧溢出報error

以上就是霍爾分區的邏輯步驟以及注意特性，現在對其穩定性解析

1.基準值被放在子序列中，防止了像單向掃描最后替換基準值時相對順序不可控的情況，提高穩定性

2.不一定是相鄰兩個元素順序交換，所以相同元素的先后順序不可控制
比如[5,1a,3,1b]基準值選擇3，第一次左右指針停留，左指針停留在5，右指針停留在1，然后交換變更數組[1b,1a,3,5], 兩個1的先后順序變更

3.對于和基準值相同的元素穩定性完全破壞穩定性，比如[3a,1,3b]，第一次交換就是[3b,1,3a],相同元素3的先后順序變更

總結：相同元素+霍爾分區，不穩定算法分區

歸并排序

歸并排序（Merge Sort）是一種分治算法，其核心思想是將數組分成兩半，分別排序，然后合并兩個有序數組。歸并排序是穩定的排序算法，時間復雜度為 O(n log n)，但需要額外的空間。

邏輯步驟

算法步驟
1.分解（Divide）：將數組遞歸地分成兩個子數組，直到每個子數組只有一個元素
2.解決（Conquer）：對每個子數組進行排序（單個元素自然有序）
3.合并（Combine）：將已排序的子數組合并成一個完整的有序數組

public static void main(String[] args) {int[] arr = {38, 27, 43, 3, 9, 82, 10};// 復制一個臨時存儲數組，并作為參數傳入，這樣只new一次 能復用節省空間int[] temp = new int[arr.length];//進入歸并排序方法mergeSort(array, 0, array.length - 1, temp);
}

進入歸并排序的mergeSort方法
步驟1：分解

private static void mergeSort(int[] arr, int left, int right, int[] temp) {if (left < right) {//步驟1:分解    這里每次都是對半分,防止整數溢出不能平分的就元素給左邊int mid = left + (right - left) / 2; // 排序左半部分leftmergeSort(arr, left, mid,temp);// 排序右半部分right   mergeSort(arr, mid + 1, right,temp);//步驟2：解決 將拆分后的子數組進行排序 并 合并有序數組merge(arr, left, mid, right, temp,temp);}
}

先圖解看步驟1分解 到步驟2解決之間的邏輯

以數組 arr數組 [38, 27, 43, 3, 9, 82, 10] 為例
1. 分解：[38, 27, 43, 3] 和 [9, 82, 10]繼續分解：[38, 27] [43, 3]    [9, 82] [10]繼續分解：[38] [27] [43] [3]   [9] [82] [10]注意:這里的拆分并不是將原數組分解成n個數組，
只是將對應的索引值標記出來傳遞進入治理合并的方法里去
merge(arr, left, mid, right, temp);

步驟2：治理解決排序問題

    // 解決并合并兩個有序數組，參數mid是左右區域分開的中間索引值(偏左指向)private static void merge(int[] arr, int left, int mid, int right, int[] temp) {int i = left;    // 左序列子數組初始位置索引指針int j = mid + 1; // 右序列子數組初始位置索引指針int t = 0;       // 臨時存儲數組的指針
原數組arr 	[38, 27, 43, 3, 9, 82, 10]已分解為 [38] [27] [43] [3] [9] [82] [10]
臨時數組temp [0, 0, 0, 0, 0, 0,0]
第一次進入該方法比較執行的這樣序列是[38] [27] 左序列索引為0 右序列索引為1 
(0和1之間沒有，兩個中間索引值總不能0.5吧，所以參數mid偏左指向)就下面這樣式的
left|mid  righti	   j[38] 	  [27]第一次進入該方法的參數 letf:0  mid:0 right:1 i:0 j:1

步驟1：比較左右子數組元素，按序放入臨時數組

         //自旋條件是不能超出"兩塊數組"的空間范圍while (i <= mid && j <= right) {if (arr[i] <= arr[j]) {temp[t++] = arr[i++];} else {temp[t++] = arr[j++];}}
(i <= mid && j <= right)  索引指針范圍 符合條件
[38] [27] 比較得出最小元素是 27 放入臨時存儲數組temp
arr 	[38, 27, 43, 3, 9, 82, 10]
temp    [27, 0, 0, 0, 0, 0,0]注意一下符合條件的元素放入temp后 其索引指針進行了后置+1，
如果僅僅是填充temp元素temp[t++] = arr[i];或者temp[t++] = arr[j];就可以了
為什么還要后置+1呢，因為還要把它作為判斷標識:biao如i<= mid成立表明左序指針還在左數組范圍內，左序還存在未填充進temp的剩余元素,剛填充的元素是右側的
left|mid  righti	   		 j	[38] 	  [27]//這時候就將左邊剩余元素按空間順序陸續填充進tempwhile (i <= mid) {temp[t++] = arr[i++];}如j<=right成立表明右序指針還在右數組范圍內，右序還存在未填充進temp的剩余元素,剛填充的元素是左序的
left|mid  righti|j[38] 	  [27]//這時候就將右邊剩余元素按空間順序陸續填充進tempwhile (j <= right) {temp[t++] = arr[j++];}
填充后的數組
arr 	[38, 27, 43, 3, 9, 82, 10]
temp    [27, 38, 0, 0, 0, 0,0]

步驟2：將temp中的元素全部拷貝回原數組

		//重置臨時數組索引指針從首位元素開始t = 0;// 將temp中的元素全部拷貝回原數組while (left <= right) { //表明拷貝的范圍只在這次排序的左右序列范圍內arr[left++] = temp[t++];}
拷貝后
arr 	[27, 38, 43, 3, 9, 82, 10]
temp    [27, 38, 0, 0, 0, 0,0]
原來分解的數組[38] [27] 就歸并成了 [27, 28]

步驟4：遞歸調用
再來看第二次參數進入執行

第二次要解決的是[43] [3]
參數
arr 	[27, 38, 43, 3, 9, 82, 10]
temp    [27, 38, 0, 0, 0, 0,0]
left|mid  righti	   j[43] 	  [3]
letf:2 mid:2 right:3 i:2 j:3然后執行到比較大小 小的元素放入臨時數組temp,這里元素3小于元素43,放入元素3
temp    [3, 38, 0, 0, 0, 0,0]
left|mid  righti	   		j[43] 	  [3]然后執行填充剩余元素,i沒超過左序指針范圍，那就是左側還有未填充元素進入temp,填充進去
temp    [3, 43, 0, 0, 0, 0,0]此時數組arr和臨時數組元素
arr 	[27, 38, 43, 3, 9, 82, 10]
temp    [3, 43, 0, 0, 0, 0,0]開始按arr[left++] = temp[t++];合并變成
arr 	[27, 38, 3, 43, 9, 82, 10]
原來分解的數組[43] [3]就歸并成了 [3, 34]

再來看第三次參數進入指向情況

第三次傳入的參數letf:0 mid:1 right:3 
arr 	[27, 38, 3, 43, 9, 82, 10] 
temp    [3, 43, 0, 0, 0, 0,0]
這次處理的是上面歸并的兩個數組[27, 38] [3, 43] (自上而下分解，然后自下而上歸并)left|mid  righti	   	   j
[27, 38]  [3, 34] 
letf:0 mid:1 right:3 i:0 j:2然后執行比較arr[i] <= arr[j]while (i <= mid && j <= right) {if (arr[i] <= arr[j]) {temp[t++] = arr[i++];} else {temp[t++] = arr[j++];}}
第一次:arr[0]<= arr[2] 否 temp填充arr[2]=3 變成[3, 43, 0, 0, 0, 0,0] j++
第二次:arr[0]<= arr[3] 是 temp填充arr[0]=27 變成[3, 27, 0, 0, 0, 0,0] i++
第二次:arr[1]<= arr[3] 是 temp填充arr[1]=27 變成[3, 27, 28, 0, 0, 0,0] i++
循環結束，變成這樣式的了
left|mid   righti   j
[27, 38]  [3, 34] 
這里i超出左側數組指針范圍，表明元素填充完了，右側沒有超還有待填充進temp的元素
temp [3, 27, 28, 34, 0, 0,0]然后開始拷貝
temp [3, 27, 28, 43, 0, 0,0]
arr  [3, 27, 28, 43, 9, 82, 10] 

到這里原數組第一次分解的左序 可就歸并好了，右邊同樣如此，總結一下步驟

原數組[38, 27, 43, 3, 9, 82, 10] 分解[38, 27, 43, 3] 和 [9, 82, 10]繼續分解：[38, 27] [43, 3] [9, 82] [10]繼續分解：[38] [27] [43] [3] [9] [82] [10]第一次歸并 [38] [27] 成 [27, 38]
第二次歸并 [43] [3] 成[3, 43]
第二次歸并 [27, 38]  [3, 43] 成 [3, 27, 28, 43]
-----------
最后歸并[3, 27, 28, 43][9, 10, 82] 得到最終排序的數組

時間復雜度：最好 平均 最壞都是O(nlog2n)

至于時間復雜度，每次對半分，這樣時間復雜度是O(log2n)
循環比較并交互元素復雜度是O(n)
兩者相乘O(nlog2n) = O(n) * O(log2n)
由于每次都是對半分，不像快速排序每次分可能兩邊極度不平衡導致退化成冒泡排序或選擇排序，所以歸并排序是穩定的排序方式，而快速排序就屬于非穩定排序了

歸并排序
平均時間復雜度：O(nlog2n)
最壞時間復雜度：O(nlog2n)
最好時間復雜度：O(nlog2n)

歸并排序:穩定性算法

歸并排序在合并過程中，如果遇到相等的元素，會先保留原來順序，因此它是穩定的排序算法

它只是將數組從上往下不停拆分，直到拆不動了，然后開始比較排序，在這個排序的過程中，不斷的是有序的左右子數組 比較元素然后合并，這個過程是中相等元素的順序是不變的

堆排序

區別于以上的基于數組結構的排序算法，堆排序（Heap Sort）雖然實際操作的還是數組，但是 ，是一種基于二叉堆（Binary Heap）這種數據結構所設計的一種排序算法，堆是一個近似完全二叉樹。并同時滿足堆的性質：即父節點的值總是大于或等于（最大堆）或小于或等于（最小堆）子節點的值

基于數組 隱式指針方式構建二叉堆

    static class TaskTreeNode {int priority;TaskTreeNode (int x) {priority = x;}}TaskTreeNode buildCompleteTaskTree() {int[] arr = {38, 27, 43, 3, 9, 82, 10};// 構建初始數組TreeNode[]，這里是一維靜態數組TaskTreeNode[] nodes = new TaskTreeNode [arr.length];// 按照先后順序給所有節點創建節點TreeNode,并且加到數組nodes for (int i = 0; i < arr.length; i++) {nodes[i] = new TaskTreeNode (arr[i]);}//返回一個根節點就是一個符合的完全二叉樹return nodes[0];}

父子節點之間的索引值的數學規律 得到的隱式指針，可以看這里關于完全二叉樹的詳細介紹

父節點索引i
其存在的左邊子節點索引值為：2*i + 1
其存在的右邊子節點索引值為：2*i + 2

基于數組的隱式指針構建二叉堆的方式又免除了 替換操作節點時候變更顯示指針的麻煩，所以二叉堆的實現大都是基于數組實現的

隱式指針的完全二叉樹實際上就是數組，這種設計的好處：
1.可以利用二叉樹的數據結構優勢和數學規律
2.可以利用數組優勢：數組連續的存儲空間可以根據索引值快速定位
3.操作數據時候不用再處理二叉樹中的節點指針指向關系
4.完全二叉樹的數據結構特征就決定了：一維數組的數據集是一定符合完全二叉樹的，即父子節點索引值的規律是一定適用的

堆排序的算法步驟過程叫 堆化過程，而堆類型分最大堆MaxHeap(大頂堆)和最小堆MinHeap(小頂堆)兩種

最大堆MaxHeap

最大堆MaxHeap(大頂堆)
①首先它必須滿足完全二叉樹的定義
②其次堆樹中任一節點的值總是不小于其子節點的值
③最大的值是根節點，堆樹中每個節點的子樹都是堆樹，注意沒有要求左右節點的大小關系

如下圖所示

堆排序

以數組 [4, 10, 3, 5, 1,12] 為例，展示堆排序過程：

初始數組: [4, 10, 3, 5,1,12]，對應的二叉堆結構4/      \10         3/ \	      / 5   1	12
根節點為4 索引值為0
左子節點10 索引值為1	隱藏指針鏈接關系為 leftIndex = 2*rootIndex +1
右子節點3  索引值為2， 隱藏指針鏈接關系為rightIndex = 2*rootIndex +2
節點3是該二叉堆最后一個非葉子節點 索引值為(N-1)/2
.......這些規律介紹可以點擊上面關于完全二叉樹的詳情介紹鏈接...........

二叉堆排序調整數據序列：將待排序的序列構造成一個大頂堆(最大堆)

    public static void main(String[] args) {int[] array = {4, 10, 3, 5, 1,12};int n = array.length;// 步驟1: 構建最大堆（從最后一個非葉子節點開始 也就是倒數第二層最后一個節點開始）for (int i = n / 2 - 1; i >= 0; i--) {heapSort(array, n, i);}}//堆排序(下沉對比)private static void heapSort(int[] array, int heapSize, int rootIndex) {int maxValueIndex = rootIndex;  // 先初始定義最大值的元素是根節點int left = 2 * rootIndex + 1;  // 左子節點索引int right = 2 * rootIndex + 2; // 右子節點索引// 如果左子節點比根節點大if (left < heapSize && array[left] > array[rootIndex]) {maxValueIndex = left;}// 如果右子節點比當前最大值大if (right < heapSize && array[right] > array[rootIndex]) {maxValueIndex = right;}// 如果最大值不是根節點，需要交換值if (maxValueIndex != rootIndex) {swap(array, rootIndex, maxValueIndex);}}//原地排序 交互對應索引的值private static void swap(int[] array, int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;}

打印輸出

第1次循環后：[4, 10, 12, 5, 1, 3]
第2次循環后：[4, 10, 12, 5, 1, 3]
第3次循環后：[12, 10, 4, 5, 1, 3]

來看具體步驟

二叉堆數據結構4/      \10         3/ \	      / \5   1	12   NIL(空節點)
==================================================================
第一次排序
選擇最后一個非葉子節點，也就是倒數第二層的最后一個節點(最后一個子樹)
比較的范圍是3			和左子節點比較  rootValue<leftValue/ \			---------------->  更新最大值索引值給MaxIndex
12   NIL(空節點)  
swap交互值 數組變更為[4, 10, 12, 5, 1, 3]
此時二叉堆數據結構 未排序 的范圍4/      \10         12/ \	      5   1	
==================================================================
第二次排序 遞減推選擇節點 10
比較的范圍是10			和左子節點比較 rootValue>leftValue   和右子節點比較/ \			---------------->  不更新maxIndex---------------->  不更新maxIndex
5    1 
這次數組元素順序不需要變更
此時二叉堆數據結構 未排序 的范圍4/      \10         12
==================================================================
第三次排序 和上面一樣步驟
比較的范圍是4			   和右子節點比較/ \			
10    12 
和左子節點比較 MaxValue<leftValue---> 更新maxIndex 此時maxIndex 對應value = 10
和右子節點比較 MaxValue<leftValue---> 更新maxIndex 此時maxIndex 對應value = 12
swap交互值 數組變更為[12, 10, 4, 5, 1, 3] 這樣排序完成
最終二叉樹數據結構調整未12/      \10         4/ \	      / \5   1	3   NIL(空節點)

總結一下
1.歸并排序，遞歸排序，原地排序

歸并排序：每次一個子樹，從最后的開始往上遞推排序，最終將最值 給“堆”到頂上去
遞歸排序：for循環控制的每次子樹范圍的比較，根據子樹個數循環次數
原地排序：每次有需要交互元素的時候根據索引值進行交互，不需要申請額外的空間

2.看下堆排序的復雜度
外層循環或者說遞歸次數是0到n/2 - 1 接近n/2，每次循環里面子樹root和left right比較，最多進行兩次比較和互換操作 所以復雜度就是(n/2 ) 乘以2 = n，所以堆排序的時間復雜度是O(n)，網上很多都說堆排序的時間復雜度都是O(nlogn)，這個說法是不太準確的，正確的說法應該是構建最大堆未或者最小堆的時間復雜度O(nlogn)：包括堆排序的O(n)和堆調整O(logn)

構建堆:

1.堆排序：
對一個非排序的完全二叉樹進行排序，時間復雜度O(n)

2.堆調整：進行堆調整的前提是 當前堆已經是最大堆或者最小堆了
a.當向一個堆中新增節點，上浮調整排序每次只需要和其對應的父節點比較，時間復雜度O(log n)
b.當從堆中取出一個節點后，剩余的堆中節點下沉調整已維持最大堆或最小堆特性時間復雜度O(logn)

堆調整

區別于我們上面從一個已經存在元素的堆再進行排序，堆調整示例從數據元素最初添加進去就按照最大堆的數據結構添加
第一步:創建一個堆的內部表示

public class MaxHeap {private final int[] heap;//用來存放元素的數組private int size;		//當前堆的大小也就是節點N的數量private final int capacity;	//堆的最大容量public MaxHeap(String mame,int capacity) {this.capacity = capacity;this.size = 0;			this.heap = new int[capacity];//初始化堆數組}

二叉堆的構造函數給一個初始容量值相當于：

	MaxHeap maxHeap = new MaxHeap(10);
先初始一個容量為10的數組Heap,初始元素默認值都為0
0 0 0 0 0 0 0 0 0 0 	

第二步:實現添加元素的操作insert

    // 插入元素public void insert(int value) {if (size == capacity) throw new IllegalStateException("Heap is full");heap[size] = value;//將新的元素放在堆的末尾heapifyUp(size);//上浮新的元素已來維持最大堆或者最小堆的性質size++;	//增加堆的大小}// 核心方法：上浮調整private void heapifyUp(int index) {int parent = (index - 1) / 2; //計算新插入節點對應的父節點的索引while(index >0 ){if(heap[index] > heap[parent]){//和父節點比較swap(index, parent);//原地排序:交互位置index = parent;//更新當前索引為父節點的位置 然后繼續往上比}else{break;}}}// 輔助方法：交換元素private void swap(int i, int j) {int temp = heap[i];heap[i] = heap[j];heap[j] = temp;}

測試代碼

    public static void main(String[] args) {//表明容量大小為10，如果是任務優先級隊列表明最大同時9個任務,也就是二叉堆節點最多9個MaxHeap maxHeap = new MaxHeap(10);maxHeap.insert(10);maxHeap.insert(15);maxHeap.insert(20);maxHeap.insert(19);maxHeap.insert(22);maxHeap.insert(13);maxHeap.insert(6);//...如添加元素的數量超過了數組容量,報錯拋出 }

打印輸出

第1次插入節點后：[10, 0, 0, 0, 0, 0, 0, 0, 0, 0]
第2次插入節點后：[15, 10, 0, 0, 0, 0, 0, 0, 0, 0]
第3次插入節點后：[20, 10, 15, 0, 0, 0, 0, 0, 0, 0]
第4次插入節點后：[20, 19, 15, 10, 0, 0, 0, 0, 0, 0]
第5次插入節點后：[22, 20, 15, 10, 19, 0, 0, 0, 0, 0]
第6次插入節點后：[22, 20, 15, 10, 19, 13, 0, 0, 0, 0]
第7次插入節點后：[22, 20, 15, 10, 19, 13, 6, 0, 0, 0]二叉堆數據結構隨著添加進的數據進行`上浮調整`節點位置，插入數據前提是該二叉堆已經是最大堆所以每次比較都只需要和父節點比較就行(不用和旁邊節點比較了，因為旁邊節點肯定沒有父節點大)只是如果比父節點大交互位置后，還需要再往上一層比較，直到能確定值不在比父節點的值大
新增節點-->父節點-->爺爺節點-->太爺爺節點-->....-->根節點那最好的情況下:新增節點就是最小的，到父節點比較來位置都不需要交互 時間復雜度O(1)
那最壞的情況下：新增節點 要比較到 根節點才能知道最大值是哪個并確定最值位置
那這種情況下 上面這條線上有多少個節點就需要多少次，就是對應的時間復雜度還是畫圖為例吧,已4層二叉堆為例A/      \B         C/ \        / \D   E      F    G/ \  / \    / \   / \
H   I J  K   M L  O   NEW最壞情況下需要比較次數:NEW-->G-->C-->A 
往上推導父節點索引 parent = (N- 1) / 2,如果滿足上面比較次數那就是需要比較到A
那此時parent = (N- 1) / 2 = 0，也就是共需要多少次(N- 1) / 2為0，就個次數是對應的時間復雜度
對應的表示就是O(log2 n)

第三步:查看最大元素的操作peek

    public int peek() {if (size == 0) throw new IllegalStateException("Heap is empty");return heap[0];//返回根節點元素也就是最大元素

第四步:取出最大元素的操作poll

    // 刪除最大值，每次移除都是根元素 就不用索引值了public int poll() {//檢查堆是不是空了if (size == 0) throw new IllegalStateException("Heap is empty");int max = heap[0];//保持一下最大元素值heap[0] = heap[size - 1];//將最后一個元素賦值到根節點先保持下二叉堆的完整size--;//減少堆的大小heapifyDown(0);//向下調整return max;//返回最大元素}// 核心方法：下沉調整private void heapifyDown(int index) {int maxIndex = index;//先假設最大值是當前節點int left = 2 * index + 1;//左子節點索引int right = 2 * index + 2;//右子節點索引if (left < size && heap[left] > heap[maxIndex]) //和左子節點比較元素大小maxIndex = left;//更新最大元的索引if (right < size && heap[right] > heap[maxIndex])maxIndex = right;//更新最大元的索引if (index != maxIndex) {swap(index, maxIndex);//原地排序：交互當前位置與最大的位置heapifyDown(maxIndex);//往下遞歸調整}}

這個方法實現的根基在于：移除元素操作的二叉堆是最大堆或者最小堆，在移除節點操作時候通過下沉調整堆中節點元素位置已維持最大堆或最小堆的特征

[20, 15, 11, 10, 12, 9, 6, 0, 0, 0]20/     \15      11/ \	     / \	10   12  9   6
此時最大堆的最大值為根節點，第二大的值就在左右子樹的頂點中產生，即15 或者 11第一步：先賦值heap[0] = heap[size - 1];//將最后一個元素賦值到根節點先保持下二叉堆的完整
此時的數組數據為[6, 15, 11, 10, 12, 9, 6, 0, 0, 0]
對應對二叉樹結構為6/     \15      11/ \	     / 10   12  9    會發現和數組比少了一個老6
因為size,堆大小表示值size在取出最大元素進行了size--,雖然當前數組元素是7個但有效節點就6個了第二步驟 開始遞歸判斷6/     \		--根節點和左右節點兩次比較得出最大值并替換6和15的位置15      11
此時樹結構為15/     \		6      11  / \	     / 	10   12  9   此時新的根節點已經確定了，再往下進行的是調整節點已維持最大堆的性質第二次遞歸判斷比較6/     \10      12 --根節點和左右節點兩次比較得出最大值并替換6和12的位置
二叉堆的數據結構變成15/     \12      11/ \	     / 	10   6  9    最新的需要比較的節點是6在索引4，是葉子節點了循序也就結束了
最新數組為 [15, 12, 11, 10, 6, 9, 6, 0, 0, 0]其中在insert方法
if (size == capacity) throw new IllegalStateException("Heap is full");
每添加一次size++; 如果capacity為10 那么添加到第10次就會觸發報錯
所以這個容量為10的數組，最多能同時容納9個有效元素

再來看時間賦值度

第一次根節點和左右子節點比較 替換并決定下次比較是左樹還是右樹
第二次節點和其左右子節點比較 替換并決定下次比較是其左樹還是右樹 
-------------------這樣相當于每次都除以2 時間復雜度O(log2n)---------------

測試一下

    public static void main(String[] args) {MaxHeap maxHeap = new MaxHeap(10);maxHeap.insert(10);maxHeap.insert(15);maxHeap.insert(20);maxHeap.insert(9);System.out.println("此時堆中有效節點數："+maxHeap.size);System.out.println("最大值："+maxHeap.peek());System.out.println("移除的最大值："+maxHeap.poll());System.out.println("最新最大值："+maxHeap.peek());}

最小堆和這個邏輯思路類似，總體來說時間復雜度：
1.構建堆：O(n)
2.每次堆調整：O(log n)
總時間復雜度：O(n log n)（最優、最差和平均情況相同）

使用堆（Heap）來實現優先級隊列管理

堆排序講的比較多，順便這里在提一下為什么選擇使用二叉堆來進行優先級任務隊列的管理

首先明確優先級隊列的操作需求：插入任務（帶優先級）和取出最高優先級的任務（即出隊），這就要求 最快找出最小（或最大）元素，為了刪除最小（或最大）

滿足該需求的數據結構符合條件
1.最快找出最小（或最大）元素，這點上大頂堆取根節點值arr[0]就可以，復雜度為O(1)，但是首位為最大值的平常數組 或者 首位為最大值的鏈表這點也符合為什么不用他們來管理呢
2.數據結構調整上復雜度：為了上述條件1，新增或刪除后的數據結構首位保持是最值元素，那么新增或者刪除元素后的數據結構調整是必要的，選擇數據結構調整上復雜度最低的

①.先看沒有采用二叉堆數據結構設計思路的完全排序的數組

 int[] arr = new int[10];
先初始一個容量為10的數組,初始元素默認值都為0
0 0 0 0 0 0 0 0 0 0 設計思路上1：將最大值放在首位,后續位置不管排序上：
第一次來添加優先級值9 放入索引0
9 0 0 0 0 0 0 0 0 0 
第二次添加優先級元素值7 和首位比較 然后決定索引位置放入數組
9 7 0 0 0 0 0 0 0 0 
第二次添加優先級元素值10 和首位比較 然后決定索引位置放入數組
10 7 9 0 0 0 0 0 0 0 
時間復雜度只需要取[0] 比較插入值 是O(1)
調整上:
取出首位最大值元素[0]，剩下的元素哪個是最大的呢，冒泡排序或者選擇排序給它重新排序
時間復雜度瞬間就上來了設計思路上2：完全按照從大到小順序排放，這就已經是冒泡排序或者選擇排序了
排序上：
第一次來添加優先級值9 放入索引0
9 0 0 0 0 0 0 0 0 0 
第二次添加優先級元素值7 和前面的比較 然后決定索引位置放入數組
9 7 0 0 0 0 0 0 0 0 
第二次添加優先級元素值10 和前面的比較 然后決定索引位置放入數組
10 9 7 0 0 0 0 0 0 0 
再看調整上
取出首位最大值元素[0]，剩下的元素最大的[1]
但是注意是取出，也就是[0]對應的元素不在數組了，原來[1]變成[0]
9 7 0 0 0 0 0 0 0 0 
每個元素都往前平移一位，時間復雜度和空間復雜度又上一層

②再來看鏈表再進行優先級節點調整上的時間復雜度

使用單鏈表的方式進行管理優先級隊列的方式：按照大小順序排放，最大的放在隊首

// 繼承一個比較接口，這樣可以方便比較節點里面的優先級值大小
public class PriorityQueueTest <T extends Comparable<T>> {//定義一個隊首private Node<T> head;//記錄任務節點數private int size;private static class Node<T> {T data;Node<T> next;Node(T data) {this.data = data;this.next = null;}}//新增元素public void insert(T data) {//根據插入優先級值 生成新的節點Node<T> newNode = new Node<>(data);//和最大值頭子比較，如果比隊列首位大就把新節點放在首位if (head == null || data.compareTo(head.data) < 0) {newNode.next = head;head = newNode;} else { //否則就往下遍歷查找合適插入的位置Node<T> current = head;// 已值大小作為判斷條件不斷往下遍歷查找位置while (current.next != null && data.compareTo(current.next.data) >= 0) {current = current.next;}//直到找到合適插入的位置,最壞情況可能需要到隊尾 時間復雜度 O(n)newNode.next = current.next;current.next = newNode;}size++;}//移除最大元素簡單 拿掉隊首的和第二位的指針指向關系就行 時間復雜度 O(1)public T poll() {if (head == null) {throw new NoSuchElementException("Priority queue is empty");}T data = head.data;head = head.next;size--;return data;}// 查看隊頭元素 查看最大值元素時間復雜度也是O(1)public T peek() {if (head == null) {throw new NoSuchElementException("Priority queue is empty");}return head.data;}// 檢查隊列是否為空public boolean isEmpty() {return head == null;}//獲取隊列大小（size）public int size() {return size;}
}

時間復雜度

插入操作（insert）：在最壞情況下插入操作需要遍歷整個鏈表以找到合適的位置。因此 時間復雜度為O(n)，其中 n 是鏈表的長度。
刪除最小元素操作（deleteMin）：刪除操作總是從鏈表的頭部進行，因此時間復雜度為 O(1)。
獲取最小元素操作（peek）：獲取最小元素操作也是從鏈表的頭部進行，因此時間復雜度為 O(1)。
判斷隊列是否為空（isEmpty）：這個只要檢查鏈表的頭部是否為 null，因此時間復雜度為 O(1)。
獲取隊列大小（size）：這個操作只需要返回一個整數值，因此時間復雜度為 O(1)。

總結
1.二叉堆的堆調整的時間復雜度是O(log2n),隨著n越大 二叉堆管理優先級隊列的性能越好
2.使用鏈表實現的優先級隊列在插入操作上時間復雜度較高為 O(n)，但在刪除最小元素和獲取最小元素等操作上時間復雜度較低為 O(1)。這種實現方式適用于需要頻繁刪除最小元素但插入操作較少的場景

堆排序：不穩定算法

堆排序：堆排序不是穩定的，因為堆化過程中會交換不相鄰的元素

在堆數據調整過程不是相鄰的元素調整的，調整的元素一般是隔著2i+1或者2i+2個空間調整的，所以這種相對元素先后順序的穩定性是完全不可控滴，堆排序不穩定舉例

[8, 2, 5a, 5b,3],其中5a和5b都是元素5，一個未排序的二叉堆進行堆排序8/     \2       5a/ \5b   3
排序最大堆結果(排序邏輯在上面堆排序里面)8/     \5b       5a/ \2  3
5b 跑到5a前面去了，相對順序變了，所以堆排序非穩定的算法