C#數據結構與演算法系列（二十三）：歸併排序演算法（MergeSort）
- 2020 年 7 月 17 日
- 筆記
- C#數據結構和演算法
1.介紹
歸併排序(MergeSort)是利用歸併的思想實現的排序方法，該演算法採用經典的分治策略(分治法將問題分(divide)成一些小的問題然後遞歸求解，
而治(conquer)的階段則將分的階段得到的各答案「修補」在一起，即分而治之)
2.示意圖
說明：可以看到這種結構很像一顆完全二叉樹，可以採用遞歸和循環迭代的方式去實現，分階段可以理解為就是遞歸拆分子序列的過程
合併相鄰有序子序列
再來看看治階段，我們需要將兩個已經有序的子序列合併成一個有序序列，比如上圖中的最後一次合併，
要將[4,5,7,8]和[1,2,3,6]兩個已經有序的子序列，合併為最終序列[1,2,3,4,5,6,7,8]，來看下實現步驟
3.實例
把數組[8,4,5,7,1,3,6,2]使用歸併排序完成排序
public class MergeSort { public static void Test() { int[] arr = { 8, 4, 5, 7, 1, 3, 6, 2 }; int[] temp = new int[arr.Length]; Sort(arr,0,arr.Length-1,temp); Console.WriteLine(string.Join(",",arr)); } /// <summary> /// 分+合方法 /// </summary> /// <param name="arr"></param> /// <param name="left"></param> /// <param name="right"></param> /// <param name="temp"></param> private static void Sort(int[] arr,int left,int right,int[] temp) { if (left<right) { //中間索引 int mid = (left + right) / 2; //向左遞歸進行分解 Sort(arr, left, mid, temp); //向右遞歸進行分解 Sort(arr, mid + 1, right, temp); //到合併 Merge(arr,left,mid,right,temp); } } /// <summary> /// 合併方法 /// </summary> /// <param name="arr">排序的原始數組</param> /// <param name="left">左邊有序序列的初始索引</param> /// <param name="mid">中間索引</param> /// <param name="right">右邊索引</param> /// <param name="temp">做中轉數組</param> private static void Merge(int[] arr, int left, int mid, int right, int[] temp) { int i = left; //初始化i,左邊有序序列的初始化索引 int j = mid + 1; //初始化j，右邊有序序列的初始化索引 int t = 0; //指向temp數組的當前索引 //(一) //先把左右兩邊（有序）的數據按照規則填充到temp數組 //直到左右兩邊的有序序列，有一邊處理完成為止 while (i <= mid && j <= right) { //如果左邊的有序序列的當前元素，小於或者等於右邊有序序列的當前元素 //即將左邊的當前元素，填充到temp數組 //然後t++,i++ if (arr[i] <= arr[j]) { temp[t] = arr[i]; t += 1; i += 1; } //反之，將右邊有序序列的當前元素，填充到temp數組 else { temp[t] = arr[j]; t++; j++; } } //(二) //把有剩餘數據的一邊的數據依次全部填充到temp while (i <= mid) { //左邊的有序序列還有剩餘的元素，就全部填充到temp temp[t] = arr[i]; t++; i++; } while (j <= right) { temp[t] = arr[j]; t++; j++; } //(三) //將temp數組的元素拷貝到arr,並不是每次都拷貝所有 t = 0; int tempLeft = left; while (tempLeft <= right) //第一次合併 tempLeft=0,right=1 第二次 tempLeft=2 right=3; { arr[tempLeft] = temp[t]; t++; tempLeft++; } } }
結果圖
