【數據結構初階】--排序(四)：歸并排序

🔥個人主頁：@草莓熊Lotso

🎬作者簡介：C++研發方向學習者

📖個人專欄：?《C語言》?《數據結構與算法》《C語言刷題集》《Leetcode刷題指南》

??人生格言：生活是默默的堅持，毅力是永久的享受。

前言：在前面的學習中，我們實現了直接插入排序，希爾排序，直接選擇排序，堆排序，冒泡排序，快速排序。我們常見的幾種排序算法也差不過都學完了。那么我們這篇博客就繼續接著上一篇博客實現完的排序往后寫，來講講歸并排序，還是和之前一樣，我們先分部分來講解，特別聲明一下，博客中的排序都是以升序為例的。??

一.遞歸實現歸并排序

具體過程：

代碼實現：?

時間復雜度：

二.非遞歸實現歸并排序?

具體過程：

?代碼實現：

?三.歸并排序的性能測試

代碼演示：?

一.遞歸實現歸并排序

?歸并排序（MERGE-SORT）是建立在歸并操作上的?種有效的排序算法,該算法是采用分治法（Divide and Conquer）的?個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成?個有序表，稱為二路歸并。

?--我們著重講一下分治的思想。合并操作需要注意的地方，大家看看后面代碼的重點提示就行了

將待排序的數組不斷分割成更小的子數組，直到每個子數組只包含一個元素。

具體過程：

找到數組的中間位置，一般是通過 mid = left + (right - left) / 2 來計算，left 和 right 分別表示當前數組范圍的起始和結束索引。
然后遞歸地對數組的左半部分（索引范圍從 left 到 mid）和右半部分（索引范圍從 mid + 1 到 right）進行同樣的分割操作，直到子數組的長度為 1。例如，對于數組 [5, 3, 8, 6, 2]，第一次分割得到 [5, 3] 和 [8, 6, 2]，然后繼續遞歸分割這兩個子數組，直到每個子數組都只有一個元素，即 [5]、[3]、[8]、[6]、[2] 。

代碼實現：?

void _MergeSort(int* arr, int left, int right, int* tmp)
{if (left >= right){return;}//分解//[left,mid][mid+1,right]int mid = left + (right-left) / 2;  _MergeSort(arr, left, mid, tmp);_MergeSort(arr, mid+1, right, tmp);//合并int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int index = left;//一定是left而不是0，不然會受到影響while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else {tmp[index++] = arr[begin2++];}}//有一個結束了，另外一個還沒結束while (begin1 <= end1){tmp[index++] = arr[begin1++];}while (begin2 <= end2){tmp[index++] = arr[begin2++];}//把數據拷貝回去for (int i = left; i <= right; i++){arr[i] = tmp[i];}
}//歸并排序--主函數里面不遞歸，所以可以先不傳left和right
void MergeSort(int* arr, int n)
{//開辟一個新數組int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail!");exit(1);}_MergeSort(arr, 0, n - 1, tmp);free(tmp);
}

重點提示：?

test.c:?

#include"Sort.h"void PrintArr(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}void test1()
{int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };int size = sizeof(a) / sizeof(a[0]);printf("排序前:");PrintArr(a, size);//歸并排序MergeSort(a, size);printf("排序后:");PrintArr(a, size);
}int main()
{test1();return 0;
}

--測試完成，升序排序沒有問題，退出碼為0

時間復雜度：

O(nlogn)

--時間復雜度 = 單次遞歸時間復雜度 * 遞歸次數?

二.非遞歸實現歸并排序?

非遞歸版本的歸并排序（迭代實現），核心思想是 “自底向上” 合并子數組，無需遞歸，直接通過循環控制分組大小（gap），逐步完成排序。

具體過程：

1. 分組合并：

gap 從 1 開始，每次翻倍（gap *= 2），表示當前合并的子數組長度。
例如：gap=1 時，合并相鄰的 1 個元素組成的子數組（實際是單個元素，視為有序）；gap=2 時，合并相鄰的 2 個元素組成的有序子數組，以此類推。

2. 邊界修正

計算 end1，end2 時，需判斷是否超出數組范圍（n-1 是最后一個元素的索引）。
若 begin2 >= n，說明第二個子數組不存在，直接跳過合并。

3. 合并操作

用雙指針法合并兩個有序子數組到 tmp，再通過 memcpy 寫回原數組。
保證合并后子數組有序，逐層向上歸并。

?代碼實現：

//非遞歸實現歸并排序
void MergeSortNore(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail!");exit(1);}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i,end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;if (begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}int index = i;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else {tmp[index++] = arr[begin2++];}}//有一個結束了，另外一個還沒結束while (begin1 <= end1){tmp[index++] = arr[begin1++];}while (begin2 <= end2){tmp[index++] = arr[begin2++];}//把數據拷貝回去memcpy(arr + i, tmp + i, (end2 - i + 1) * sizeof(int));}gap *= 2;}free(tmp);
}

test.c：

#include"Sort.h"void PrintArr(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}void test1()
{int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };int size = sizeof(a) / sizeof(a[0]);printf("排序前:");PrintArr(a, size);//非遞歸實現歸并排序MergeSortNore(a, size);printf("排序后:");PrintArr(a, size);
}int main()
{//TestOP();test1();return 0;
}

--測試完成，升序排序沒有問題，退出碼為0

?三.歸并排序的性能測試

--我們實現完了這么多種排序，我們還是通過測試函數看看它們的性能對比吧

代碼演示：?

include"Sort.h"void PrintArr(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}void test1()
{int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };int size = sizeof(a) / sizeof(a[0]);printf("排序前:");PrintArr(a, size);//直接插入排序//InsertSort(a, size);//希爾排序//ShellSort(a, size);//直接選擇排序//SelectSort(a, size);//堆排序//HeapSort(a, size);//冒泡排序//BubbleSort(a, size);//快速排序//QuickSort(a, 0, size - 1);//非遞歸快速排序//QuickSortNoare(a, 0, size - 1);//快速排序進階版//QuickSortMore(a, 0, size - 1);//歸并排序//MergeSort(a, size);//非遞歸實現歸并排序//MergeSortNore(a, size);//非比較排序--計數排序CountSort(a, size);printf("排序后:");PrintArr(a, size);
}// 測試排序的性能對比
void TestOP()
{srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);int* a6 = (int*)malloc(sizeof(int) * N);int* a7 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];a7[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3 = clock();SelectSort(a3, N);int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();int begin5 = clock();QuickSort(a5, 0, N - 1);int end5 = clock();int begin6 = clock();MergeSort(a6, N);int end6 = clock();int begin7 = clock();BubbleSort(a7, N);int end7 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("SelectSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("QuickSort:%d\n", end5 - begin5);printf("MergeSort:%d\n", end6 - begin6);printf("BubbleSort:%d\n", end7 - begin7);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
}int main()
{TestOP();//test1();return 0;
}

--我們可以通過下圖對比一下各個排序的效率