每每遇到關于排序算法的問題總是不能很好的解決，對一些概念，思想以及具體實作的認識也是模棱兩可。歸根結底，還是掌握不夠熟練。以前隻是看别人寫，看了就忘。現在打算自己寫，寫些自己的東西，做個總結。本篇是這個總結的開始，是以我們先來闡述一下本次總結中會用到的一些概念。
排序是如何分類的？可以從不同的的角度對排序進行分類，這裡我是根據排序的政策對本次總結中涉及到的排序算法進行分類
前言
每每遇到關于排序算法的問題總是不能很好的解決，對一些概念，思想以及具體實作的認識也是模棱兩可。歸根結底，還是掌握不夠熟練。以前隻是看别人寫，看了就忘。現在打算自己寫，寫些自己的東西，做個總結。本篇是這個總結的開始，是以我們先來闡述一下本次總結中會用到的一些概念。
排序是如何分類的？可以從不同的的角度對排序進行分類，這裡我是根據排序的政策對本次總結中涉及到的排序算法進行分類：
| 交換排序 | 冒泡排序（Bubble Sort） |
| 快速排序（Quick Sort） | |
| 插入排序 | 簡單插入排序（Simple Insertion Sort）（也被稱為直接插入排序） |
| 希爾排序（Shell Sort） | |
| 選擇排序 | 簡單選擇排序（Simple Selection Sort）（也被稱為直接選擇排序） |
| 堆排序（Heap Sort） | |
| 歸并排序 | Merge Sort |
| 基數排序 | Radix Sort |
| 計數排序 | Count Sort |
其中每個算法都有其相應的時間複雜度和空間複雜度，這裡我也對它們做了一個彙總：
| 算法名稱 | 時間複雜度 | 空間複雜度 | 穩定性 | 複雜性 |
|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(1) | 穩定 | 簡單 |
| 快速排序 | O(nlog2n) | O(log2n) | 不穩定 | 較複雜 |
| 簡單插入排序 | O(n2) | O(1) | 穩定 | 簡單 |
| 希爾排序 | O(nlog2n)（參考值，與增量有關） | O(1) | 不穩定 | 較複雜 |
| 簡單選擇排序 | O(n2) | O(1) | 不穩定 | 簡單 |
| 堆排序 | O(nlog2n) | O(1) | 不穩定 | 較複雜 |
| 歸并排序 | O(nlog2n) | O(n) | 穩定 | 較複雜 |
| 基數排序 | O(d(n + r)) | O(n + r) | 穩定 | 較複雜 |
| 計數排序 | O(n + k) | O(n + k) | 穩定 | 簡單 |
說明
-
排序還會涉及到一個概念，叫排序的穩定性。那麼穩定性是什麼意思呢？
穩定性，就是有兩個相同的元素，排序後它們相對位置是否發生變化，若未變化則該稱該排序算法是穩定的。否則就是不穩定的。
- 本次總結所有的算法實作均是以從小到大為例進行排序的，後面不再特别指出。
- 文章後面将會提到的有序區，無序區。是指在待排序列中，已經排好順序的元素，就認為其是處于有序區中，還沒有被排序的元素就處于無序區中。
- 小提示，點選文章頁面右下角的“檢視目錄”可以檢視本文目錄哦
接下來，我們開始進入正文
交換排序
交換排序主要包括兩種排序算法，分别是冒泡排序和快速排序
冒泡排序
基本思想
從後往前，兩兩比較待排序列中的元素的大小，若比較結果不符合要求，則進行交換。這樣較小的元素會一直向前移動
通過無序區中相鄰元素的比較和交換，使最小的元素如氣泡一般逐漸往上漂浮至水面
複雜度與穩定性與優缺點
- 空間複雜度：O(1)
- 時間複雜度：O(n2)
- 最好情況：正序有序時，普通冒泡排序仍是O(n^2)，優化後的冒泡排序是O(n)
- 最壞情況：逆序有序時，O(n2)
- 穩定性：穩定
- 優點：簡單，穩定，空間複雜度低
- 缺點：時間複雜度高，效率不好，每次隻能移動相鄰兩個元素，比較次數多
算法實作
public void BubbleSort(int[] array){
for(int i = 0; i < array.Length - 1; i ++){
for(int j = array.Length - 1; j > i ; j --){
if(array[j] < array[j - 1]){
Swap(array, j, j - 1);
}
}
}
}
// 實作将指定下标的兩個元素在數組中交換位置
public void Swap(int[] array, int i, int j){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
【算法解讀】
算法的外層循環中的
i
可以了解為有序區的邊界，從0開始即表示初始時有序區是空的。當外層循環執行完一次後，會有一個無序區中最小的元素移動到有序區中，此時
i + 1 = 1
表示有序區邊界擴大了，
i
以内的元素都處在有序區中。當
i = array.Length - 1
時，即表示所有元素都處于有序區了，算法結束。
内層循環負責将無序區中的最小元素移動到有序區中，依次對無序區中相鄰元素進行比較，如果位置靠後的元素小于位置靠前的元素，則交換兩個元素。如此一來，無序區中最小的元素就會被一步步交換到有序區的末尾。
【舉個栗子】
對于待排序列4,1,3,2
首先依次比較無序區（初始時為所有元素）中的相鄰元素，比較3,2，位置靠後的元素小于位置靠前的元素，則交換。序列為4,1,2,3。繼續比較1,2，位置靠後的元素大于位置靠前的元素，不交換。繼續比較4,1，需要交換，此時無序區中的元素全部比較完畢，一趟冒泡排序結束，序列為1,4,2,3。可以看到最小元素1已經移動到序列首部，即處于有序區内，确定了一個元素的位置。無序區還剩下4,2,3。重複上述操作完成最終排序。
冒泡排序優化
當待排序列是正序有序時，冒泡排序的時間複雜度仍然是O(n2)，針對這點我們可以做一些優化
當内層循環執行完成一趟卻沒有發生交換時，說明此時的待排序列已經是正序有序的了，可以直接終止算法。
public void BubbleSortOptimize(int[] array){
for(int i = 0; i < array.Length - 1; i ++){
bool swapTag = false; // 标志位，判斷每完成一趟冒牌排序是否發生交換
for(int j = array.Length - 1; j > i; j --){
if(array[j] < array[j - 1]){
Swap(array, j, j -1);
swapTag = true;
}
}
if(!swapTag){
break;
}
}
}
快速排序
基本思想
快速排序又被稱為分區交換排序，是目前已知的平均速度最快的一種排序方法，它采用了一種分治的政策，是對冒泡排序的一種改進。
在待排序列中任取其中一個元素作為目标元素（稱其為樞軸或分界點），以該元素為分界點（pivot）進行分區，将待排序列分成兩個部分，所有比分界點小的元素都放置于分界點左邊，所有比分界點大的元素都放置于分界點的右邊，然後再分别将左右兩邊作為兩個待排序列，重複上述過程，直到每個分區隻剩下一個元素為止。顯然，每一趟快速排序後，分界點都找到了自己在有序序列中的位置
複雜度與穩定性與優缺點
- 空間複雜度：O(log2n)取決于遞歸深度，所占用的棧空間
- 時間複雜度：O(nlog2n)
- 最好情況：O(nlog2n)，當每次分區，分界點左，右兩邊的分組長度大緻相等時，快速排序算法的性能最好
- 最壞情況：O(n2)，當每次選擇的分界點都是目前分組的最大元素或最小元素時，快速排序算法退化為冒泡算法。
- 穩定性：不穩定，因為将元素移動到分界點兩邊時，會打亂原本相等元素的順序
- 優點：極快
- 缺點：不穩定
算法實作
public void QuickSort(int[] array){
QuickSortImpl(array, 0, array.Length - 1);
}
public void QuickSortImpl(int[] array, int left, int right){
if(left >= right) return;
int pivot = Partition(array, left, right);
QuickSortImpl(array, left, pivot - 1);
QuickSortImpl(array, pivot + 1, right);
}
// 分區函數，實作将所有元素依據大小移動到分界點的兩邊
public int Partition(int[] array, int left, int right){
int target = array[left];
while(left < right){
while(right > left && array[right] >= target){
right --;
}
if(right > left){
array[left] = array[right];
// 此時left位置的元素是被移動過來的元素，肯定比目标元素小
// 是以左指針掃描時就可以不用比較該元素，進行left++操作
left ++;
}
while(left < right && array[left] <= target){
left ++;
}
if(left < right){
array[right] = array[left];
right --;
}
}
array[left] = target;
return left;
}
【算法解讀】
算法首先選取待排序列的首元素作為分界點，調用
Partition
方法進行分區，将待排序列依據分界點分成兩個部分。每個子部分再作為待排序列進行遞歸調用。直到每部分隻剩一個元素（對應代碼：
if(left >= right) return;
）。
算法的關鍵在于
Partition
方法内部，通過左右指針不斷進行比較替換。首先準備移動右指針（因為當找到比分界點小的元素時，可以先将其移動到左指針指向的位置，而左指針所指向位置的元素已經被儲存到
target
中，不用擔心被覆寫），找到比分界點小的元素後将其移動到左指針指向的位置。右指針停止。準備移動左指針，找到比目标元素大的元素後，将其移動到右指針指向的位置（此時原來在右指針位置的元素也已經被移動走了，可以直接覆寫），左指針停止。再次開始移動右指針，重複上述操作。直到左指針和右指針重合，它們指向的位置就是分界點元素應該在的最終位置。
【舉個栗子】
對于待排序列3,1,4,2
先看圖：
首先選取首元素3作為目标元素，并将其儲存在臨時變量
target
中。起始
left
指向3，
right
指向2。開始移動右指針，發現2比目标元素3小，則将2移動到
left
指向的位置，注意此時
left
向右移動一位，指向1。右指針停止。開始移動左指針，1比3小符合要求，繼續移動，發現4比3大，不符合要求，将4移動到
right
位置（即原來2的位置，同理
right
也左移一位），
left
指針停止。
重新準備移動右指針，發現
right
與
left
重合則第一次分區結束。3找到了它的最終位置，即
left
，
right
重合的位置，将3移動到該位置。此時序列為2,1,3,4。
繼續遞歸重複上述操作。
快速排序優化政策
這裡簡單介紹一下快速排序可以做的一些優化
- 當待排序列是部分有序時，固定選取樞軸（即分界點）會使快排效率低下，要緩解這種情況，可以引入随機選取樞軸的方式
- 當待排序列長度分割到一定大小後，可以使用插入排序代替快速排序，因為對于很小和部分有序的序列，簡單插入排序的效率更好
- 針對遞歸的優化，算法中調用了兩次
QuickSortImpl
left = pivot + 1
插入排序
插入排序主要包括兩種排序算法，分别是簡單插入排序和和希爾排序
簡單插入排序
基本思想
每次将一個無序區的元素，按其大小找到其在有序區中的位置，并插入到該位置，直到全部元素插完為止。
插入排序不是通過交換位置而是通過比較找到合适的位置插入元素來達到排序的目的
複雜度與穩定性與優缺點
- 空間複雜度：O(1)
- 時間複雜度：O(n2)
- 最好情況：O(n)，正序有序時
- 最壞情況：O(n2)，逆序有序時
- 穩定性：穩定
- 優點：穩定，快，如果序列是基本有序的，使用直接插入排序效率就非常高
- 缺點：插入次數不一定，插入越多，插入點後的資料移動越多，特别是資料量龐大的時候，但用連結清單可以 解決這個問題。
算法實作
public void SimpleInsertionSort(int[] array){
for(int i = 1; i < array.Length; i ++){
int j = i;
int target = array[j];
while(j > 0 && target < array[j - 1]){
array[j] = array[j - 1];
j --;
}
array[j] = target;
}
}
【算法解讀】
算法預設待排序列的第一個元素是排好序的，處于有序區。從第二個元素開始，直到到末尾元素，依次作為目标元素（對應代碼：
for(int i = 1; i < array.Length; i ++)
)，向有序區中插入。那麼如何插入呢？将目标元素依次和有序區的元素進行比較，若目标元素小于該元素，則目标元素就應處于該元素的前面，則該元素後移一個位置(對應代碼：
array[j] = array[j - 1];
)。不斷比較直到找到不比目标元素小的元素，則目标元素就應在該元素的後面位置，将目标元素插入到該位置。繼續下一個目标元素，直到所有元素插入完畢。
在開始插入第i個元素時，前i-1個元素已經是排好序的。
【舉個栗子】
對于待排序列3,1,4,2
首先認為3是有序的，處于有序區。将1作為目标元素，依次和有序區中的元素進行比較，和3進行比較，1<3，則3後移，有序區中沒有待比較的資料了，是以将1插入到3原來的位置。此時序列：1,3,4,2。有序區内元素為1,3。繼續将4作為目标元素，先和3比較，4>3，則插入到4的後面位置。此時序列1,3,4,2。此時有序區内元素為1,3,4。繼續将2作為目标元素，和4比較，2<4，4後移，和3比較，2<3，3後移，和1比較，2>1，則插入到1的後面。此時序列1,2,3,4。所有元素插入完畢，即排序完成。
希爾排序
基本思想
希爾排序是插入排序的一種高效率的實作，又稱縮小增量式插入排序。它也是簡單插入排序算法的一種改進算法。
先標明一個數作為第一個增量，将整個待排序列分割成若幹個組，分組方式是将所有間隔為增量值的元素放在同一個組内。各組内部進行直接插入排序。然後縮小增量值，重複上述分組和排序操作，直到所取增量減少為1時，即所有元素放在同一個組中進行直接插入排序。
為什麼希爾排序的時間性能是優于簡單插入排序的呢？
開始時，增量較大，每組中的元素少，是以組内的直接插入排序較快，當增量減少時，分組内的元素增加，但此時分組内的元素基本有序，是以使得組内的直接插入排序也較快，是以，希爾排序在效率上較簡單插入排序有較大的改進
複雜度與穩定性與優缺點
- 空間複雜度：O(1)
- 時間複雜度：O(nlog2n)
- 最好情況：O(nlog2n)，因為希爾排序的執行時間依賴于增量序列，如何選擇增量序列使得希爾排序的元素比較次數和移動次數較少，這個問題目前還未能解決。但有實驗表明，當n較大時，比較和移動次數約在 n1.25~1.6n1.25。
- 最壞情況：O(nlog2n)
- 穩定性：不穩定，相同元素可能分在不同的組内，導緻順序可能發生改變
- 優點：快，資料移動少
- 缺點：不穩定，d的取值是多少，應該取多少個不同的值，都無法确切知道，隻能憑經驗來取
算法實作
public void ShellSort(int[] array){
int d = array.Length / 2;
while(d >= 1){
for(int i = d; i < array.Length; i ++){
int j = i;
int target = array[j];
while(j >= d && target < array[j -d]){
array[j] = array[j - d];
j -= d;
}
array[j] = target;
}
d /= 2;
}
}
【算法解讀】
希爾排序算法是對簡單插入排序的改進，是以如果對簡單插入排序還不夠了解的話，建議先去看一下上面的簡單插入排序算法。
算法首先取增量為待排序列長度的一半，通過增量進行分組，每個分組都進行簡單插入排序。然後，增量減半，重複上述操作直至增量減少為1（對應代碼：
while(d >= 1)
）。
算法的要點在于對每個分組進行簡單插入排序。首先從
i = d
位置上的元素開始，一直到待排序列的最後一個元素，依次作為目标元素，找到它們應該在自己分組中的位置并進行插入。當目标元素位置為
i
時，則目标元素所在分組的有序區内的元素位置分别為
i-d
，
i-d-d
，
i-d-d-d
...直到該位置大于0。目标元素隻需要和所在分組有序區内的元素進行比較，找到自己的最終位置即可。當增量減少為1時，則相當于隻有一個分組，此時就是對所有元素進行直接插入排序，完成最終的希爾排序。
【舉個栗子】
對于待排序列4,1,3,2
先看圖：
首先取增量為序列長度4的一半，即為2。此時的分組是（4,3），（1,2）。則從下标為2的元素3開始作為目标元素，下标2減去增量2，則找到目标元素3所在分組有序區内的元素4，和4進行比較，3<4，則4後移（這裡的後移都是相對于自己所在分組裡的元素），有序區内沒有其它元素，則目标元素3插入到元素4之前的位置。此時序列為3,1,4,2。繼續從下标為3的元素2開始作為目标元素，找到目标元素2所在分組有序區内的元素1，比較2>1，符合預期都不需要移動。一趟希爾排序完成，序列仍為3,1,4,2。增量再減半為1，此時就是對所有元素進行簡單插入排序，不再贅述。
希爾排序的關鍵點在于分組，我們再舉個栗子看是如何分組的：
對于序列25,36,48,59,13,21,74,32,60
第一次增量為序列長度9的一半，取下限是4，此時的分組情況是（25,13,60）（36,21）（48,74）（59,32），如下圖：
那麼到這裡，交換排序中的冒泡排序，快速排序和插入排序中的簡單插入排序，希爾排序，就總結完了。
後面我會繼續總結選擇排序中的簡單選擇排序算法，堆排序算法，以及歸并，基數，計數排序算法，敬請期待。
上面算法的源碼都放在了GitHub上，感興趣的同學可以點選這裡檢視
更多算法的總結與代碼實作（不僅僅是排序算法），歡迎大家檢視我的GitHub倉庫Algorithm