【数据结构】归并排序

​​

👦个人主页：Weraphael
✍🏻作者简介：目前正在学习c++和算法
✈️专栏：数据结构
🐋 希望大家多多支持，咱一起进步！😁
如果文章有啥瑕疵
希望大佬指点一二
如果文章对你有帮助的话
欢迎 评论💬 点赞👍🏻 收藏 📂 加关注😍

---

一、基本思想（递归）

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。有点类似于二叉树的后序遍历。

归并排序前提是两个序列必须是有序，然后再从两个序列中选数到一个临时数组中。

以下是归并排序的核心步骤：

1. 确定分界点。目的是为了分为两个序列。mid = (left + right) >> 1
2. 递归处理分界点的左右两部分的区间。[left, mid] [mid + 1, right]
3. 【✨重点✨】归并。如上图所示，当递归至区间只有一个数后，开始将两个有序序列合并成一个有序序列

二、归并的方式（双指针算法）

1. 使用两个指针i和j， 分别指向分界点两端的数组头。
2. 创建一个临时数组tmp来暂存排完有序的数组，用k来遍历tmp。
3. 比较a[i]和a[j]直到其中一个序列中的元素全部遍历完。这就分为两种情况：若a[i] <= a[j]，则tmp[k++] = a[i++]（将小的元素放入tmp中）；同理，若a[i] > a[j]，则tmp[k++] = a[j++]
4. 可能会存在特殊情况：左、右两个区间可能会有多余元素没有比较完，则将多余元素原封不动放入数组tmp
5. 最后再将tmp数组中的元素复制回原数组a[]

三、递归代码实现

void RMergeSort(int a[], int l, int r, int* tmp)
{// 当区间只有一个数或者没有数，没必要排序了if (l >= r) return;// 1. 确定分界点下标int mid = (l + r) >> 1;// 2. 递归处理分界点左右两端区间RMergeSort(a, l, mid, tmp);RMergeSort(a, mid + 1, r, tmp);// 当递归结束来到此处，说明分界点左右两边已经是有序的了// 3. 归并int i = l, j = mid + 1;int k = 0;while (i <= mid && j <= r){if (a[i] <= a[j])tmp[k++] = a[i++];elsetmp[k++] = a[j++];}// 可能存在某个区间没有遍历完while (i <= mid)tmp[k++] = a[i++];while (j <= r)tmp[k++] = a[j++];// 将已排好序tmp还给原数组afor (int i = l, k = 0; i <= r; i++, k++)a[i] = tmp[k];
}// 归并排序(递归)
void MergeSort(int a[], int n)
{int* tmp = new int[n];// 如果在此函数递归，每次都要new大小为n的对象，消耗太大RMergeSort(a, 0, n - 1, tmp);delete[] tmp;
}

四、非递归版归并排序

4.1 思路

归并排序的非递归实现通常使用迭代和循环来模拟递归过程。下面是归并排序非递归实现的基本思路：

1. 分组： 首先，将原始数组视为若干个长度为1的有序子数组（因为长度为1的数组是有序的）。

2. 两两合并： 然后进行迭代，将相邻的两个有序子数组进行合并，并按照合并后的顺序形成新的有序子数组。这一步可以通过循环实现。

3. 增加子数组长度： 接着，将子数组长度翻倍，重复上述合并操作，直到整个数组成为一个有序的数组。

值得注意的是，归并排序的非递归实现需要考虑如何处理边界情况、子数组长度变化等细节，但整体思路和递归实现是类似的。

4. 2 代码实现

void mergeSort(int a[], int l, int r, int n)
{// 辅助数组int* tmp = (int*)malloc(sizeof(int) * n);int gap = 1;while (gap < n){for (int i = 0; i <= r; i = i + 2 * gap){int begin1 = i, end1 = i + gap - 1, mid = i + gap - 1;int begin2 = mid + 1, end2 = i + 2 * gap - 1;int j = i;if (begin2 > r) break;if (end2 > r) end2 = r;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]) tmp[j++] = a[begin1++];else tmp[j++] = a[begin2++];}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}for (int j = i; j <= end2; j++){a[j] = tmp[j];}}gap = 2 * gap;}
}