制作不易，三連支持一下吧！！！

---

前言

這篇博客我們將介紹歸并排序的原理和實現過程。

---

一、歸并排序遞歸方法實現

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

歸并排序核心步驟：

? ??????1.分解：?

將所給序列一分為二，直到區間中只有一個元素時停止。這個過程是遞歸進行的，通過傳遞區間參數來控制。

? ? 2.?合并：

相鄰兩個子數組有序之后，就遞歸合并這兩個子數組，將它們合并成一個新的有序子數組。

?動圖演示如下：

歸并時，我們是借助一個臨時數組tmp來合并兩個有序子數組。?

?代碼實現如下：

void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin >= end)return;int mid = (begin + end) / 2;_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid + 1, end, tmp);int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[i++] = a[begin1++];}else {tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(n * sizeof(int));_MergeSort(a, 0, n - 1, tmp);free(tmp);tmp = NULL;
}

二、歸并排序非遞歸方法實現

同快速排序一樣，如果遞歸深度過深，可能會導致棧溢出，這樣的情況下，我們就不能用遞歸法來實現歸并排序。

上篇博客提到：將遞歸改成非遞歸的一般方法有兩種

一種是直接改循環，如斐波那契數列。

另一種是借助棧或隊列，例如快速排序。

這里我們借助棧也無法完成歸并排序，因此我們只能選擇循環。

代碼實現如下：

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc:");return;}int gap = 1;while (gap < n){for (int j = 0; j < n; j +=2*gap){int begin1 = j, end1 = begin1 + gap - 1;int begin2 = end1 + 1, end2 = begin2 + gap - 1;int i = j;if (end1 >= n || begin2 >= n){break;}//處理數組越界的情況if (end2 >= n)end2 = n - 1;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[i++] = a[begin1++];}else {tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + j, tmp + j, sizeof(int) * (end2 - j + 1));}gap *= 2;}free(tmp);tmp = NULL;
}

---