一、基數排序
“基於比較”可以有些讀者和認為排序不都是基於比較的嗎？但是，有個排序方法不用根據大小就能夠排序——基數排序。
基數排序它是根據每位數的大小來比較的。首先，建立9個大小相等的佇列。再根據每個數的個位數去比較大小。
例如：初始化：
根據個位數去比較大小：
從左到右依次出隊。
再根據十位數的大小去入隊：
最後依次出列則已經排好序。
二、直接插入排序
1。直接插入排序思路與程式碼
思路：直接插入排序它是從下標為1的數開始，將i下標的元素放入tmp中，若有元素比tmp中的數大，則放在j+1的位置，j再往後回退。
目的是將最小的數放在最後排序時的最終位置。
例如：
初始化：令i從下標1開始，j從i-1開始。
將i下標的元素放入tmp中，比較j下標的元素。若j下標的元素比tmp大，則有
arr［j+1］=arr［j］
。
此時j小於0，則遍歷i。i到2下標，重複相同的操作。但是若有
tmp>arr［j］
，直接跳出現在i下標處的迴圈，i到下一個位置。
最後如果退出這一趟的迴圈，則記得要將
arr［j+1］=tmp
，將tmp的值放入陣列當中。
程式碼：
public static void insertSort（int［］ array） {
for（int i = 1；i < array。length；i++） {//n-1
int tmp = array［i］；
int j = i-1；
for（； j >= 0；j——） {//n-1
if（array［j］ > tmp） {
array［j+1］ = array［j］；
}else{
break；
}
}
array［j+1］ = tmp；
}
}
2。直接插入排序特點、時間複雜度、空間複雜度、穩定性分析
特點：當一組資料資料量不大且趨近有序，此時用直接插入排序是比較快的，並且是陣列越有序越快。
時間複雜度：
若陣列基本上是有序的，則最好時間複雜度為O（N） 。
若陣列基本上是無序的，則最壞時間複雜度為O（N^2） 。
平均時間複雜度：O（N^2） 。
空間複雜度：O（1） 。
穩定性：穩定。
若要將直接插入排序的穩定性變為不穩定，則只需將array［j］ > tmp改為array［j］ >= tmp即可。例如一個數組由16*（星號當中標記），16，18組成，則i為16的位置，j為16 * 的位置，因為 16 * 大於等於16，則16* 移到16的位置，最後j- -，j小於0，則16移到了16*的位置。結果為：16，16 * ，18 。
3。折半插入排序（瞭解）
在有序區間選擇資料應該插入的位置時，因為區間的有序性，可以利用折半查詢的思想。
public static void bsInsertSort（int［］ array） {
for （int i = 1； i < array。length； i++） {
int v = array［i］；
int left = 0；
int right = i；
// ［left， right）
// 需要考慮穩定性
while （left < right） {
int m = （left + right） / 2；
if （v >= array［m］） {
left = m + 1；
} else {
right = m；
}
}
// 搬移
for （int j = i； j > left； j——） {
array［j］ = array［j - 1］；
}
array［left］ = v；
}
}
三、希爾排序
1。希爾排序思路與程式碼
希爾排序是基於直接插入排序的最佳化。
思想：假設10000個數據，若用直接插入排序則最壞情況下的時間複雜度為1000010000=1億，若採用分組的思想，10000個數據分為100組，每組100個，則每組的時間複雜度為100100=10000，因為有100則，則100組的時間複雜度為10000*100=100w。遠小於直接插入排序的時間複雜度。而希爾排序就是用的分組的思想。
例子：
我們先將一個數組分為5組。則跨度為5，有：
我們原理上可以是先將每組的數字排序。例如12，8，7排序後為7，8，12 。每一組都是相同的排序。
最後有：
但是我們求出來的只是每個組有序。此時我們可以將跨度改為3，即3組。有：
相同地，將每組的資料排序後，有：（雖然跨度越來越小，但是陣列本身越來越有序）
最後將跨度變為1，則每一個數據為一組，等同於直接插入排序。
理論上是以上的思想。但是程式碼上有所不同。
如果程式碼上直接實現每組排序是比較困難的。我們不妨先將i到每組的中間位置，j為每組的起始位置。
初始化：
因為8比12小，有：
**此時令i++，比較的是第二組中的中間位置與起始位置的數值。**發現5比33小，5回退5個單位，小於0，則再i++。
我們發現當i++一直加到最後一組的中間元素之後，比較的是第一組的最後一個元素與中間元素。
如：（j每次要比i小gap個單位）。
需要注意的是，最後一次的跨度一定要為1，否則無法保證有序。
public static void shellSort（int［］ array） {
//處理gap
int gap = array。length；
while （gap > 1） {
gap = gap / 3 + 1；//+1是為了保證最後一個序列是1，其實除幾都行
// gap /= 2；
shell（array，gap）；
}
}
public static void shell（int［］ array，int gap） {
for （int i = gap； i < array。length； i++） {
int tmp = array［i］；
int j = i-gap；
for （； j >= 0； j -= gap） {
if（array［j］ > tmp） {
array［j+gap］ = array［j］；
}else {
break；
}
}
array［j+gap］ = tmp；
}
}
2。希爾排序特點、時間複雜度、空間複雜度、穩定性分析
特點：到目前為止，還沒有人求得一種最好的增量序列（gap），陣列中不同個數的數值對應最好的增量序列也不同。
時間複雜度：
陣列趨近於有序：O（N） 。
陣列趨近於無序：O（N^2） ，比較難構造。
平均時間複雜度：O（N^1。3） 。
空間複雜度：O（1） 。
穩定性：不穩定。
四、選擇排序
1。選擇排序思路與程式碼
public static void selectSort（int［］ arr） {
for （int i = 0； i for （int j = i+1； j if（arr［i］>arr［j］） { int tmp = arr［i］； arr［i］=arr［j］； arr［j］=tmp； } } } } 2。選擇排序特點、時間複雜度、空間複雜度、穩定性分析 選擇排序特點：每一次從無序區間選出最大（或最小）的一個元素，存放在無序區 間的最後（或最前），直到全部待排序的資料元素排完 。 時間複雜度：O（N^2） 。 空間複雜度：O（1） 。 穩定性：不穩定。 五、氣泡排序 1。氣泡排序思路與程式碼 下面是最佳化的程式碼，設定了flg能夠直接判斷陣列是否是有序的，若在一個排序的情況下已知整個陣列是有序的，則直接退出迴圈，不用再繼續排序了。 思路：外層遍歷的是陣列需要排序的趟數，而j遍歷的是陣列當中的每個資料是否需要排序。 需要注意的是，i和j的範圍都是array。length-1，是因為調整到陣列的最後時，陣列的最後一個數的前面的數已經是調整過的了，並且最後一個數無需再調整。 public static void bubbleSort（int［］ array） { // boolean flg = false； for （int i = 0； i < array。length-1； i++） { boolean flg = false；//為什麼每一趟都要置為false for （int j = 0； j < array。length-1-i； j++） { if（array［j］ > array［j+1］） { int tmp = array［j］； array［j］ = array［j+1］； array［j+1］ = tmp； flg = true； } } if（flg == false） { break； } } } 2。氣泡排序特點、時間複雜度、空間複雜度、穩定性分析 特點：氣泡排序比較直觀，若前面一個數比後面一個數大，則直接交換。 時間複雜度：最好最壞都是O（n^2） ，但是：如果優化了，並且陣列有序的時候就是O（n），只要看情況。 空間複雜度：O（1） 。 穩定性：穩定。 六、堆排序 1。堆排序的思路與程式碼 原理：基本原理也是選擇排序，只是不在使用遍歷的方式查詢無序區間的最大的數，而是透過堆來選擇無序區間的最大的數。 注意： 排升序要建大堆；排降序要建小堆。 下面這篇部落格是作者早前詳細寫過有關堆排序以及它的應用的文章，有興趣的可以點入連結，此處不再說明。 堆排序及堆的應用 2。堆排序特點、時間複雜度、空間複雜度、穩定性分析 特點：堆排序能夠很快地找出堆當中前K大或前K小的資料。 時間複雜度：O（N*log2^N） 。 空間複雜度：O（1） 。 穩定性：不穩定。 七、快速排序 1。快速排序的思路與程式碼 原理：待排序的資料當中要找到一個基準（pivot）。 Partition： 遍歷整個待排序區間，將比基準值小的（可以包含相等的）放到基準值的左邊，將比基準值大的（可以包含相等的）放到基準值的右邊； 找基準也是一個排序的過程。 採用分治思想，對左右兩個小區間按照同樣的方式處理，直到小區間的長度==1，代表已經有序，或者小區間的長度 = = 0，代表沒有資料。 挖坑法程式碼思路（partition）： 以陣列0下標的元素作為基準，存入tmp中。設定low指向0下標，high指向陣列的最後的下標。 如果有arr［high］>=tmp，則high向左直到遇到有比tmp大的。如果high向左遍歷中有比tmp小的，則arr［low］=arr［high］。 此時向右遍歷low，判斷是否有資料比tmp大。若有，則arr［high］=arr［low］。 當然，如果low和high相遇了就不再遍歷low和high。此時將tmp的值放入arr［low］中即可， 此時返回low下標就是陣列的基準，它是將陣列劃分為左右兩邊，左邊的數都是比它小的，右邊的數都是比它大的。挖坑法首先將陣列0下標的數放入tmp中，此時一定要從右邊開始與tmp比較大小。 (1) 遞迴實現快速排序 圖解： 初始化： 挖坑法後的第一趟： 此時6已經是排好序的，只要以相同的挖坑法去執行pivot左右兩邊的資料即可達到排序。 三數取中找基準是有 arr［mid］<=arr［low］<=arr［high］ 是為了將基準最後按照挖坑法放到陣列的中間位置，更快地遞迴執行pivot兩邊的資料。 快速排序的遞迴： public static void insertSort（int［］ arr，int start，int end） { for （int i = start+1； i int tmp = arr［i］； int j = i-1； for （j = i-1； j >=start ； j——） { if（arr［j］>tmp） { arr［j+1］=arr［j］； }else { break； } } arr［j+1］=tmp； } } public static int partition（int［］ arr，int low，int high） { int tmp = arr［low］； while（low while（low high——； } arr［low］=arr［high］； while（low low++； } arr［high］=arr［low］； } arr［low］=tmp； return low； } public static void quickSort（int［］ arr，int low，int high） { if（low>=high） { return； } if（high-low+1<=100） { insertSort（arr，low，high）； } selectPivotMedianOfThree（arr，low，high）； int pivot = partition（arr，low，high）； quickSort（arr，0，pivot-1）； quickSort（arr，pivot+1，high）； } //快排中的三數取中找基準 public static void selectPivotMedianOfThree（int［］ arr，int low，int high） { //arr［mid］<=arr［low］<=arr［high］ int mid = （low+high）/2； if（arr［mid］>arr［low］） { int tmp = arr［mid］； arr［mid］=arr［low］； arr［low］=tmp； } if（arr［low］>arr［high］） { int tmp = arr［low］； arr［low］=arr［high］； arr［high］=tmp； } } public static void quick（int［］ arr） { quickSort（arr，0，arr。length-1）； } public static void main（String［］ args） { int［］ array = {12，5，9，34，6，8，33，56，89，0，7，4，22，55，77}； quick（array）； System。out。println（Arrays。toString（array））； } (2) 非遞迴實現快速排序 快速排序非遞迴要用到棧。 思路：首先找到陣列的基準。並且要判斷基準的兩邊是否足夠資料來找基準。若資料個數為1或0，則無需找基準；反之可以找基準。 再將左邊資料的左右邊界壓入棧中，再將右邊資料的左右邊界壓入棧中。此時棧如果不為空，則出棧中的兩個元素，即右邊資料的左右邊界，此時再去找它們的基準。若右邊的找基準的左右邊界不再入棧即右邊完成了排序。同樣地，左邊找基準也是如此。 程式碼： public static int partition（int［］ arr，int low，int high） { int tmp = arr［low］； while（low while（low high——； } arr［low］=arr［high］； while（low low++； } arr［high］=arr［low］； } arr［low］=tmp； return low； } public static void quickSort2（int［］ array） { Stack int start = 0 ； int end= array。length-1； int pivot = partition（array，start， end）； if（pivot>start+1） { stack。push（0）； stack。push（pivot-1）； } if（pivot stack。push（pivot+1）； stack。push（end）； } while（！stack。empty（）） { end =stack。pop（）； start =stack。pop（）； pivot = partition（array，start，end）； if（pivot>start+1） { stack。push（0）； stack。push（pivot-1）； } if（pivot stack。push（pivot+1）； stack。push（end）； } } } 注意：出棧的先後順序分別是end和start 。 思路： 1。先呼叫partition，找到pivot。 2。把當前的pivot的左邊區間和右邊區間的下標放入棧中。 3。判斷棧是否為空，不為空彈出兩個元素，要注意先後順序給的是誰。 4。再進行partition，若左右都排完序則棧為空。 2。快速排序特點、時間複雜度、空間複雜度、穩定性分析 特點：排序速度最快。 時間複雜度： 最好時間複雜度：O（n * log2^N） 。 基準將陣列均勻地分割。如同一顆二叉樹。 最壞時間複雜度：O（N^2） 。 陣列完全逆序。 如同單分支的二叉樹。 空間複雜度： 最好空間複雜度：O（log2^N） 。 最壞空間複雜度：O（N） 。 穩定性：不穩定。 表示最好時間複雜度。 八、歸併排序 1。歸併排序思路與程式碼 原理與思路：歸併排序（MERGE-SORT）是建立在歸併操作上的一種有效的排序演算法，該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，稱為二路歸併。 從上往下的歸併排序採用了遞迴的方式實現。它的原理非常簡單，如圖： 以上圖為例，很像一個二叉樹，將一個數組的每一個元素分為一組，這是“遞”。再將一個一個合併為每兩個一組、兩個兩個合併為四個一組等等，這是“歸”。**因此此處涉及到了合併兩個有序陣列的問題。**觀察下圖，可見當low和high相等時，則子資料不需要再進一步歸併排序了，此時只需要將它們合併並且排序。要注意的是需要設定一個數組tmp將資料都儲存起來。 (1) 遞迴實現歸併排序 因為看圖解，歸併排序的分解很像一顆二叉樹的先序遍歷。當low和high相等就是一個單位的資料，此時就要歸併。 public static void mergeSort1（int［］ array） { mergeSortInternal（array， 0，array。length-1）； } public static void mergeSortInternal（int［］ array，int low，int high） { if（low >= high） { return； } int mid = （low+high） / 2； mergeSortInternal（array，low，mid）； mergeSortInternal（array，mid+1，high）； //合併的過程 merge（array，low，mid，high）； } public static void merge（int［］ array，int low，int mid，int high） { int s1 = low； int e1 = mid； int s2 = mid+1； int e2 = high； int［］ tmp = new int［high-low+1］； int k = 0；//代表tmp陣列的下標 while （s1 <= e1 && s2 <= e2） { if（array［s1］ <= array［s2］） { tmp［k++］ = array［s1++］； }else { tmp［k++］ = array［s2++］； } } //有2種情況 while （s1 <= e1）{ //說明第2個歸併段沒有了資料 把第1個歸併段剩下的資料 全部複製過來 tmp［k++］ = array［s1++］； } while （s2 <= e2） { //說明第1個歸併段沒有了資料 把第2個歸併段剩下的資料 全部複製過來 tmp［k++］ = array［s2++］； } //tmp陣列當中 儲存的就是當前歸併好的資料 //這樣的程式碼是錯誤的 /*for （int i = 0； i < array。length； i++） { array［i］ = tmp［i］； }*/ for （int i = 0； i < tmp。length； i++） { array［i+low］ = tmp［i］； } } 注意： 1。tmp陣列的作用就是將分散的資料合併起來，因此有array［i+low］ = tmp［i］；**是因為陣列的後半段不能覆蓋掉陣列前面的資料，**若array［i］ = tmp［i］；就會覆蓋掉前面的資料。 如：後面的40 80與20 60歸併在一起時，不能覆蓋掉原陣列前面10 30 50 70 90的值。並且此時它們的low為5，array［i］ = tmp［i］；能夠避免。 2。遞迴實現的歸併排序首先每一個每一個合併為一組，此時一組為兩個，再每兩組每兩組合並，此時一組為四個，以此類推。 (2) 非遞迴實現歸併排序 非遞迴來實現歸併排序跟遞迴實現歸併排序的方法型別，也要**考慮到合併兩個有序的陣列問題。**但不同的是，非遞迴是直接將一整個陣列運用遞迴的歸併排序思想的基礎上在原陣列當中調整。因此tmp陣列的長度直接設定為原陣列的長度。 注意： 要考慮到右邊是否有歸併段，因此有while迴圈的判斷條件s2 < array。length。如果右邊沒有歸併段，則直接將左邊歸併段的資料拷入到tmp當中，tmp陣列的大小跟原陣列的大小相同。如果右邊有歸併段，則歸併完成後要調整s1，e1，s2，e2的值。 mergeSort方法內部是控制每幾個每幾個資料的合併。merge2方法內部是將兩個數組合並並排序。 e2的位置要注意不能陣列越界，如果超過陣列的長度，則讓它指向陣列最後的元素；若不超過，則按照常規邏輯有e2=s2+gap-1。 public static void mergeSort（int［］ array） { for （int i = 1； i < array。length； i*=2） { merge2（array，i）； } } public static void merge2（int［］ array，int gap） { int［］ tmp = new int［array。length］； int k = 0； int s1 = 0； int e1 = s1+gap-1； int s2 = e1+1； int e2 = s2+gap-1 < array。length ？ s2+gap-1 ： array。length-1； //保證有兩個歸併段 while （s2 < array。length） { while （s1 <= e1 && s2 <= e2） { if（array［s1］ <= array［s2］） { tmp［k++］ = array［s1++］； }else { tmp［k++］ = array［s2++］； } } while （s1 <= e1） { tmp［k++］ = array［s1++］； } while （s2 <= e2） { tmp［k++］ = array［s2++］； } //一組完了 確定新的區間的開始和結束 s1 = e2+1； e1 = s1+gap-1； s2 = e1+1； e2 = s2+gap-1 < array。length ？ s2+gap-1 ： array。length-1； } //e2 > array。length while （s1 <= array。length-1） { tmp［k++］ = array［s1++］； } for （int i = 0； i < tmp。length； i++） { array［i］ = tmp［i］； } } 2。歸併排序特點、時間複雜度、空間複雜度、穩定性分析 特點：歸併排序的排序速度相對來說比較快，但仍沒有快速排序快。並且它的空間複雜度較大。 時間複雜度： 最好最壞情況下：O（N * log2^N） 。 空間複雜度：O（N） 。 穩定性：穩定。 九、排序中時間複雜度、空間複雜度、穩定性的總結
