書名：《圖說演算法-使用C#》
作者：吳燦銘、胡昭民
所讀版本：博碩文化
排序方式
直接移動：直接交換儲存數據的位置
邏輯移動：不移動存儲位置，僅改變指向目標數據的指標值
排序術語
穩定：兩個相同鍵值的記錄在排序後仍然保持相同的次序
不同情況下的時間複雜度
最好情況：原始資料已完成排序
最壞情況：資料中的每一個鍵值都要重新排序
平均情況：介乎最好與最壞，平常遇見最多的情況
空間複雜度：執行過程中所需付出的額外記憶體空間
排序算法
冒泡排序
由第一個元素開始，比較相鄰元素大小，若大小順序有誤，則對調後再進行下一個元素的比較
時間複雜度：
最壞/平均：O(n^2)
最佳：O(n)
穩定的排序
空間複雜度：O(1)
適用於數據量小/部分數據已排序的情況
通過記錄該次循環是否有進行過比較，沒有則直接中斷循環來減少多餘的比較。
我的冒泡排序實現
public static void Bubble(int[] arr)
{
int flag; //Optimize Code
for (int i = 0; i < arr.Length; i++)
{
flag = 0; //Optimize Code
for (int j = 0; j < arr.Length - 1; j++)
{
if(arr[j + 1] < arr[j])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag++;
}
}
if (flag == 0) { break; } //Optimize Code
}
}
選擇排序
反覆從未排序的數組中取出最小/最大的元素，加入到另一個數組中。
時間複雜度：
無論哪種情況都要找到最大/最小值，時間複雜度穩定為O(n^2)
不穩定的排序
空間複雜度：O(1)
適用於數據量小/部分數據已排序的情況
我的選擇排序實現
public static void Select(int[] arr)
{
for (int i = 0; i < arr.Length - 1; i++)
{
for (int j = i + 1; j < arr.Length; j++)
{
if (arr[j] < arr[i])
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
插入排序
將數組中的元素，逐一與已排序好的元素作比較，並插入到適當的位置中。
時間複雜度：
最壞/平均：O(n^2)
最好：O(n)
穩定的排序
空間複雜度：O(1)
適用於大部分數據已排序/在已排序的數據上新增數據進行排序
插入排序會造成數據的大量搬移，所以最好通過單向鏈表實現
我的單向鏈表插入排序實現
public class LinkedNode
{
public int val;
public LinkedNode next;
public LinkedNode(int val = 0, LinkedNode next = null)
{
this.val = val;
this.next = next;
}
}
public static LinkedNode Insert_LinkedList(int[] arr)
{
LinkedNode head = new LinkedNode(-99);
LinkedNode curr = head.next;
LinkedNode prev = head;
for (int i = 0; i < arr.Length; i++)
{
LinkedNode newNode = new LinkedNode(arr[i]);
curr = head.next;
prev = head;
while (curr != null && newNode.val > curr.val)
{
curr = curr.next;
prev = prev.next;
}
prev.next = newNode;
newNode.next = curr;
}
return head.next;
}
我的數組插入排序實現
public static void Insert_Loop(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
int compareIdx = i;
int compareTarget = arr[compareIdx];
while(compareIdx > 0 && compareTarget < arr[compareIdx - 1])
{
arr[compareIdx] = arr[compareIdx - 1];
compareIdx--;
}
arr[compareIdx] = compareTarget;
}
}
謝耳排序
插入排序的加速版
通過將數據區分成特定間隔的幾個小區塊，再使用插入排序排完區塊內的數據後再慢慢減少間隔的距離，從而減少插入排序法中數據搬移的次數，加速排序的進行。
將數據分成（數據總數 / 質數） = 劃分數份，比如(8/2)就把數據分成4份
每一份的兩個數據之間下標的差 = 劃分數
如數據：63, 92, 27, 36, 45, 71, 58, 7
劃分後分組為(63, 45), (92, 71), (27, 58), (36, 7)
它們的下標為:(0, 4), (1, 5), (2, 6), (3, 7)
對每一組進行插入排序，然後把間隔/2，重複執行直到間距 = 1，完成排序
時間複雜度：所有情況均為O(n^(2/3))
穩定的排序
空間複雜度：O(1)
適用於大部分數據已排序完成的情況
書中的謝耳排序實現
public static void Shell(int[] arr)
{
int j; //以j來定位比較的元素
int tmp; //資料暫存
int jmp; //間距位移量
jmp = arr.Length / 2;
while(jmp != 0)
{
for (int i = jmp; i < arr.Length; i++)
{
tmp = arr[i];
j = i - jmp;
while(j >= 0 && tmp < arr[j])
{
arr[j + jmp] = arr[j];
j = j - jmp;
}
arr[jmp + j] = tmp;
}
jmp = jmp / 2;
}
}
快速排序
先在數據中挑選一個「中間值」，並根據這個「中間值」，將所有打算排序的數據分為兩部分：
左邊：小於中間值
右邊：大於中間值
然後再兩邊的數據各自重複進行上述步驟，直到排序完成
時間複雜度：
最快/平均：O(nlog2n)
最壞：O(n^2)
不穩定的排序
空間複雜度：
最壞：O(n)
最好：O(nlog2n)
我的快速排序實現
public static void QuickSort(int[] arr, int left, int right)
{
if(left < right)
{
//初始值
int standard = arr[left]; //基準數，把小於等於它的數放在它的左邊，把大於它的數放在它的右邊
//用來做循環的標志位
int i = left;
int j = right;
//一直重複以下兩個循環，直到i == j（找到中間位置）。也就是基準數所在的位置
while (i < j)
{
//從後往前比較（從右向左比較）找一個比standard小 or 等於standard 的數字
//然後放在我們的坑裡面
//坑位於 i 的位置
while (i < j)
{
if (arr[j] <= standard) //從排序數據的尾部開始，找到了一個小於/等於基準數的數字，應該把他放在standard的左邊
{
arr[i] = arr[j];
break;
}
else
{
j--; //向左移動到下一個數字，然後做比較
}
}
//從前往後（從左向右）找一個比standard大的數字，放在坑裡面
//現在的坑位於j的位置
while (i < j)
{
if(arr[i] > standard)
{
arr[j] = arr[i];
break;
}
else
{
i++;
}
}
}
//現在i == j了，跳出循環，把基準值standard 賦值到中間位置（i）
arr[i] = standard;//left -- i -- right
QuickSort(arr, left, i - 1);
QuickSort(arr, j + 1, right);
}
}
歸并排序
針對已排序好的兩個或以上的數組，通過合併將它們經合成一個大的且已排序完成的數組
因此，如果是對一個未排序的數組進行歸并排序，首先要將數組重複對半分割直到數組不能再分割為止（數組長度==1）
然後再對兩個數組之間的元素進行比較，按據從小到大/從大到小的規則輸出到一個新的數組裡，然後再把這個合併後的數組往上提交。
提交上去的數組又會跟另一邊提交上去的數組之間進行比較和合併，最後回到頂端，合併成一個排序完成的數組
時間複雜度：所有情況均為O(nlogn)
空間複雜度為O(n)
穩定的排序
我的歸并排序實現
public static int[] MergeSort(int[] arr)
{
if (arr.Length <= 1) { return arr; }
//重複對半分割，直到無法分割
int mid = arr.Length / 2;
int[] left = MergeSort(arr.Take(mid).ToArray());
int[] right = MergeSort(arr.Skip(mid).Take(arr.Length - mid).ToArray());
//合併左右兩個數組
return Merger(left, right);
}
static int[] Merger(int[] leftPart, int[] rightPart)
{
int[] res = new int[leftPart.Length + rightPart.Length];
int leftIdx = 0;
int rightIdx = 0;
int resIdx = 0;
//左數組和右數組都有沒用完的元素
while(leftIdx < leftPart.Length && rightIdx < rightPart.Length)
{
if(leftPart[leftIdx] < rightPart[rightIdx])
{
res[resIdx] = leftPart[leftIdx];
leftIdx++;
}
else
{
res[resIdx] = rightPart[rightIdx];
rightIdx++;
}
resIdx++;
}
//其中一個數組遍歷到了末尾，把剩下的另外一個數組元素也加到結果裡
while(leftIdx < leftPart.Length)
{
res[resIdx] = leftPart[leftIdx];
resIdx++;
leftIdx++;
}
while(rightIdx < rightPart.Length)
{
res[resIdx] = rightPart[rightIdx];
resIdx++;
rightIdx++;
}
return res;
}
基數排序
基數排序是一種分配模式排序方式，不需要進行元素間的比較動作。
時間複雜度：所有情況均為O(nlogpk)，k = 原始數據的最大值
穩定的排序
空間複雜度：O(n * p)，p是數據字元數
若n（數據量）很大，p很小，基數排序將會很有效率
書中的基數排序實現
public static void Radix(int[] arr)
{
//0 -> 10 -> 100
for (int i = 1; i <= 100; i *= 10)
{
int[,] tmp = new int[10, 100]; //[0-9位數, 資料個數]
for (int j = 0; j < arr.Length; j++)
{
//m: i位數的值（arr[j] = 36; i = 10 -> (36/10) % 10 = 3）
int m = (arr[j] / i) % 10;
tmp[m, j] = arr[j];
}
//將tmp內的值放回原數組
int k = 0;
for (int j = 0; j < 10; j++)
{
for (int l = 0; l < arr.Length; l++)
{
if (tmp[j, l] != 0)
{
arr[k] = tmp[j, l];
k++;
}
}
}
}
}
堆排序
利用二叉樹的技巧，通過堆積樹完成排序
堆積樹特點
是一個完整二叉樹
所有節點都大於等於（最大堆積樹） or 小於等於（最小堆積樹）它左右子節點的值
樹根（首位下標的元素）是堆積樹中最大/最小的
時間複雜度：均為O(nlogn)
不穩定的排序
空間複雜度：O(1)
我的最小堆排序（輸出順序從大至小）
public static void HeapSort(int[] arr)
{
//arr.Length / 2 => 最後一個葉節點的父親節點 => 最後一個非葉節點
//節點編號從1開始
for (int i = arr.Length / 2; i > 0; i--)
{
//將每一個非葉節點構造成最小堆
HeapAdjust(i, arr, arr.Length);
}
//經過上面的循環，成功將完全二叉樹變成了小頂堆
foreach (var item in arr)
{
Console.Write(item + ", ");
}
//小頂堆只能保證根節點的元素是最小的，但不能保證後面的元素也是順序的
//因此還需要持續將根節點放到樹的末尾，然後把除末尾以外的節點進行最小堆的重構
//從而持續把最小元素推到根節點，再把之放在末尾，重複進行
//因此，最小堆可以得到一個從大至小排序的數組，而最大堆則可以得到一個從小到大排序的數組
//從最後一個數開始，與第一個數進行交換
for (int i = arr.Length; i > 1; i--)
{
//1 和 i 位置互換，交換之後，
//編號為1存儲的是最大值，編號為i存儲的是最小值
int temp = arr[0];
arr[0] = arr[i - 1];
arr[i - 1] = temp;
//持續把最小節點放到末尾，重構堆時將末尾的元素忽略
HeapAdjust(1, arr, i - 1);
}
Console.WriteLine();
foreach (var item in arr)
{
Console.Write(item + ", ");
}
}
static void HeapAdjust(int targetNumber, int[] arr, int numLimit)
{
//把編號1到(i - 1)構造成小頂堆
//把i節點的子樹變成小頂堆
int minNodeNumber = targetNumber;
int tmp = targetNumber;
while (true)
{
int leftSon = tmp * 2; //i的左子樹在array裡的下標
int rightSon = tmp * 2 + 1; //i的右子樹在array裡的下標
//左子節點存在（leftSon <= numLimit）
//且左子節點比當前節點的值小（arr[leftSon - 1] > arr[numLimit - 1]）
//需要-1是因為leftSon和numLimit都是編號（由1開始），而不是索引（由0開始）
//最後得到當前樹與兩個子樹中最小的節點
if(leftSon <= numLimit
&& arr[leftSon - 1] < arr[minNodeNumber - 1])
{
minNodeNumber = leftSon;
}
if(rightSon <= numLimit
&& arr[rightSon - 1] < arr[minNodeNumber - 1])
{
minNodeNumber = rightSon;
}
//經過上面的處理後
//minNodeNumber = 這個子樹裡最小節點的編號
//tmp依然等當前父節點（i）的編號
//發現了一個比i數據更小的子節點，將tmp和minNodeNumber編號裡的數據交換
if (minNodeNumber != tmp)
{
int cache = arr[tmp - 1];
arr[tmp - 1] = arr[minNodeNumber - 1];
arr[minNodeNumber - 1] = cache;
//交換之後，讓當前父節點編號往下移動，指向較小節點的原來編號
//然後再通過這個編號去檢查下面還有沒有子節點
tmp = minNodeNumber; //讓交換後的節點再跟他的子節點做比較
}
else
{
//當子節點編號 與 父節點編號 相等，那就代表沒有子節點，跳出循環
//子節點沒有比i節點更小的，已有小頂堆
break;
}
}
}