思路：
依次交換相鄰兩個數， 使大的在後， 每趟在末尾確定一個最大值
外迴圈 n 趟依次確定最大值， 次大值， ....， 確定排序
學習交流,請少俠駐足:C/C++學習交流 8群 491994603
注意：
內迴圈的相鄰元素下標寫法和內迴圈下標起始
學習交流,請少俠駐足:C/C++學習交流 8群 491994603
計數排序思路：
找到陣列最大值 max 和最小值 min， 以差值(max-min)作為桶陣列的長度
遍歷陣列入桶計數
遍歷桶， 寫回原陣列
注意：
入桶時， 對應桶下標為
A[i]-min
寫回陣列時下標依次遞增，
A[i++] = j + min;
堆排序思路：
初始化成大根堆
將堆頂元素(即最大值)和末尾元素交換， 並下沉該換上來的末尾元素
將堆的長度減1， 重複第二步
注意：
下標從 1 開始較方便， 子節點下標就對應為
2*i
和
2*i+1
初始化時從一半位置依次遞減下標使用下沉操作
下沉操作挑子節點中較大值與父節點交換， 直至 滿足父節點大於兩個子節點
插入排序思路：
將陣列前一部作為一個“有序數組”，
每趟迴圈將當前元素依次和前一個元素比對， 插入到“有序數組”中的相應位置
注意：
注意下標起始， 外迴圈 n-1 次， 內迴圈下標遞減
插入效果可以使用兩兩相鄰交換來實現
學習交流,請少俠駐足:C/C++學習交流 8群 491994603
這裡使用非遞迴的 bottom-up 的實現方式
思路：
每次合併的單位長度為 size ， size 依次取 1， 2， ... ， 直到 size>=n
對於每個 size， 從前往後按照步長為 2*size 依次合併
歸併的內部邏輯是， 先從原陣列拷貝一份到輔助陣列， 再按序填回原陣列
注意：
需要分配一個輔助陣列用於合併
每次合併需要傳遞五個參數：原陣列， 輔助陣列以及合併的起止下標和中點下標
歸併的截止下標需要取小避免越界
Math.min(n, i + 2 * size);
內迴圈的終止條件是
i + size < n
， 步長是
2*size
學習交流,請少俠駐足:C/C++學習交流 8群 491994603
快速排序思路：
shuffle(可選):先把原陣列隨機打亂
partition:隨機選一個數作為參考值， 比其小的放左邊， 大的放右邊
遞迴地排序上述結果的左半部分和右半部分
注意：
一般參考值就取第一個元素， 對後面的元素進行劃分
劃分時注意迴圈終止條件， 大於小於帶不帶等號， 都要注意
學習交流,請少俠駐足:C/C++學習交流 8群 491994603
選擇排序思路：
每次遍歷一趟挑取最小元素， 將該元素與起始元素交換
起始元素下標依次為0， 1， ...， n-1
注意：
比較的是值， 記錄的是下標
學習交流,請少俠駐足:C/C++學習交流 8群 491994603
基數排序以元素小於等於 2000 為例，位數為 4
思路：
準備一個 10*n 的桶陣列(10 代表 0～9 的數位，n代表某個數位下最多容納的個數，這裡為原陣列大小 n)
由低位元到高位，將3，4步執行位數次迴圈
遍歷陣列，按照某一位元的數位將元素入桶
從大數位到小數位，依次將桶內元素從後往前寫回原陣列
注意：
需要兩個輔助陣列，一個用於存放元素，一個用於記錄每個數位桶的元素個數
入桶時一定要先低位元，再高位，這樣才能保證最高位影響最大
取桶內元素返到陣列時一定要倒著取，這樣才能保證之前排序的順序
希爾排序思路：
對陣列進行步長為1，4，13,...,（3*前一個步長+1）的插入排序，步長由大到小
注意：
最外層先計算好最大步長，每次除以三
插入排序的外層起始下標為 h，每次下標遞增 1
插入排序的內層遞減步長為 h
選擇關鍵字進行排序,學習交流,請少俠駐足:C/C++學習交流 8群 491994603
關鍵字 ----元素個數有關係
[6 2 4 1 5 9]
//通用分組 每次選取一半，直到 關鍵字 為1
關鍵字：6/2=3 每隔3個元素分為一組
分組怎麼分
[6,1] ： 1,6
[2,5] ： 2,5 //不動
[4,9] ： 4,9 //不動
關鍵字：3/2=1
[6 2 4 1 5 9]
//關鍵字為3排序後的結果
[1 2 4 6 5 9]
進行插入排序: 選出5 找到合適的位置進行插入
[1 2 4 5 6 9]
學習交流,請少俠駐足:C/C++學習交流 8群 491994603
學習交流,請少俠駐足:C/C++學習交流 8群 491994603
基數排序以元素小於等於 2000 為例，位數為 4
思路：
準備一個 10*n 的桶陣列(10 代表 0～9 的數位，n代表某個數位下最多容納的個數，這裡為原陣列大小 n)
由低位元到高位，將3，4步執行位數次迴圈
遍歷陣列，按照某一位元的數位將元素入桶
從大數位到小數位，依次將桶內元素從後往前寫回原陣列
注意：
需要兩個輔助陣列，一個用於存放元素，一個用於記錄每個數位桶的元素個數
入桶時一定要先低位元，再高位，這樣才能保證最高位影響最大
取桶內元素返到陣列時一定要倒著取，這樣才能保證之前排序的順序
希爾排序思路：
對陣列進行步長為1，4，13,...,（3*前一個步長+1）的插入排序，步長由大到小
注意：
最外層先計算好最大步長，每次除以三
插入排序的外層起始下標為 h，每次下標遞增 1
插入排序的內層遞減步長為 h
選擇關鍵字進行排序,學習交流,請少俠駐足:C/C++學習交流 8群 491994603
關鍵字 ----元素個數有關係
[6 2 4 1 5 9]
//通用分組 每次選取一半，直到 關鍵字 為1
關鍵字：6/2=3 每隔3個元素分為一組
分組怎麼分
[6,1] ： 1,6
[2,5] ： 2,5 //不動
[4,9] ： 4,9 //不動
關鍵字：3/2=1
[6 2 4 1 5 9]
//關鍵字為3排序後的結果
[1 2 4 6 5 9]
進行插入排序: 選出5 找到合適的位置進行插入
[1 2 4 5 6 9]
學習交流,請少俠駐足:C/C++學習交流 8群 491994603