歸併排序——C語言
- 2019 年 10 月 3 日
- 筆記
歸併排序
歸併排序（MERGE-SORT）是建立在歸併操作上的一種有效的排序演算法,該演算法採用經典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然後遞歸求解，而治(conquer)的階段則將分的階段得到的各答案”修補”在一起，即分而治之)，將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序，若將兩個有序表合併成一個有序表，稱為二路歸併
1、歸併排序的基本思想
將待排序序列R[0…n-1]看成是n個長度為1的有序序列，將相鄰的有序表成對歸併，得到n/2個長度為2的有序表；將這些有序序列再次歸併，得到n/4個長度為4的有序序列；如此反覆進行下去，最後得到一個長度為n的有序序列
2、歸併排序的演算法描述
第一步：申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合併後的序列
第二步：設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
第三步：比較兩個指針所指向的元素，選擇相對小的元素放入到合併空間，並移動指針到下一位置
重複步驟3直到某一指針超出序列尾，將另一序列剩下的所有元素直接複製到合併序列尾
歸併排序其實要做兩件事：
（1）“分解”——將序列每次折半劃分（遞歸實現）
（2）“合併”——將劃分後的序列段兩兩合併後排序
如何合併？
在每次合併過程中，都是對兩個有序的序列段進行合併，然後排序。
這兩個有序序列段分別為 R[low, mid] 和 R[mid+1, high]。
先將他們合併到一個局部的暫存數組R2中，帶合併完成後再將R2複製回R中。
我們稱 R[low, mid] 第一段，R[mid+1, high] 為第二段。
每次從兩個段中取出一個記錄進行關鍵字的比較，將較小者放入R2中，最後將各段中餘下的部分直接複製到R2中。
經過這樣的過程，R2已經是一個有序的序列，再將其複製回R中，一次合併排序就完成了。
3、程式碼實現
1 /* 將序列對半拆分直到序列長度為1*/ 2 void MergeSort_UptoDown(int *num, int start, int end) 3 { 4 int mid = start + (end - start) / 2; 5 6 if (start >= end) 7 { 8 return; 9 } 10 11 MergeSort_UptoDown(num, start, mid); 12 MergeSort_UptoDown(num, mid + 1, end); 13 14 Merge(num, start, mid, end); 15 } 16 17 void Merge(int *num, int start, int mid, int end) 18 { 19 int *temp = (int *)malloc((end-start+1) * sizeof(int)); //申請空間來存放兩個有序區歸併後的臨時區域 20 int i = start; 21 int j = mid + 1; 22 int k = 0; 23 24 while (i <= mid && j <= end) 25 { 26 if (num[i] <= num[j]) 27 { 28 temp[k++] = num[i++]; 29 } 30 else 31 { 32 temp[k++] = num[j++]; 33 } 34 } 35 36 while (i <= mid) 37 { 38 temp[k++] = num[i++]; 39 } 40 while (j <= end) 41 { 42 temp[k++] = num[j++]; 43 } 44 45 //將臨時區域中排序後的元素，整合到原數組中 46 for (i = 0; i < k; i++) 47 { 48 num[start + i] = temp[i]; 49 } 50 51 free(temp); 52 }
4、拆分過程
（圖片來源：https://www.cnblogs.com/chengxiao/p/6194356.html）
完整程式碼：
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 void MergeSort_UptoDown(int *num, int start, int end); 5 void Merge(int *num, int start, int mid, int end); 6 7 int main() 8 { 9 /* 歸併排序（升序） */ 10 int num[10] = {5, 1, 8, 4, 7, 2, 3, 9, 0, 6}; 11 int length = sizeof(num) / sizeof(num[0]); 12 int i; 13 14 MergeSort_UptoDown(num, 0, length - 1); 15 16 for (i = 0; i < length; i++) 17 { 18 printf("%d ", num[i]); 19 } 20 21 return 0; 22 } 23 24 /* 將序列對半拆分直到序列長度為1*/ 25 void MergeSort_UptoDown(int *num, int start, int end) 26 { 27 int mid = start + (end - start) / 2; 28 29 if (start >= end) 30 { 31 return; 32 } 33 34 MergeSort_UptoDown(num, start, mid); 35 MergeSort_UptoDown(num, mid + 1, end); 36 37 Merge(num, start, mid, end); 38 } 39 40 void Merge(int *num, int start, int mid, int end) 41 { 42 int *temp = (int *)malloc((end-start+1) * sizeof(int)); //申請空間來存放兩個有序區歸併後的臨時區域 43 int i = start; 44 int j = mid + 1; 45 int k = 0; 46 47 while (i <= mid && j <= end) 48 { 49 if (num[i] <= num[j]) 50 { 51 temp[k++] = num[i++]; 52 } 53 else 54 { 55 temp[k++] = num[j++]; 56 } 57 } 58 59 while (i <= mid) 60 { 61 temp[k++] = num[i++]; 62 } 63 while (j <= end) 64 { 65 temp[k++] = num[j++]; 66 } 67 68 //將臨時區域中排序後的元素，整合到原數組中 69 for (i = 0; i < k; i++) 70 { 71 num[start + i] = temp[i]; 72 } 73 74 free(temp); 75 }
View Code
