服装厂网站模板,云主机 免费,WordPress知更鸟首页幻灯,欧洲做安网站 #x1f466;个人主页#xff1a;Weraphael ✍#x1f3fb;作者简介#xff1a;目前正在学习c和算法 ✈️专栏#xff1a;数据结构 #x1f40b; 希望大家多多支持#xff0c;咱一起进步#xff01;#x1f601; 如果文章有啥瑕疵 希望大佬指点一二 如果文章对你… 个人主页Weraphael ✍作者简介目前正在学习c和算法 ✈️专栏数据结构 希望大家多多支持咱一起进步 如果文章有啥瑕疵 希望大佬指点一二 如果文章对你有帮助的话 欢迎 评论 点赞 收藏 加关注 目录 一、基本思想递归二、归并的方式双指针算法三、递归代码实现四、非递归版归并排序4.1 思路4. 2 代码实现 一、基本思想递归 归并排序是建立在归并操作上的一种有效的排序算法该算法是采用分治法的一个非常典型的应用。有点类似于二叉树的后序遍历。
归并排序前提是两个序列必须是有序然后再从两个序列中选数到一个临时数组中。
以下是归并排序的核心步骤
确定分界点。目的是为了分为两个序列。mid (left right) 1递归处理分界点的左右两部分的区间。[left, mid] [mid 1, right]【✨重点✨】归并。如上图所示当递归至区间只有一个数后开始将两个有序序列合并成一个有序序列
二、归并的方式双指针算法 使用两个指针i和j 分别指向分界点两端的数组头。创建一个临时数组tmp来暂存排完有序的数组用k来遍历tmp。比较a[i]和a[j]直到其中一个序列中的元素全部遍历完。这就分为两种情况若a[i] a[j]则tmp[k] a[i]将小的元素放入tmp中同理若a[i] a[j]则tmp[k] a[j]可能会存在特殊情况左、右两个区间可能会有多余元素没有比较完则将多余元素原封不动放入数组tmp最后再将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的数组是有序的。 两两合并 然后进行迭代将相邻的两个有序子数组进行合并并按照合并后的顺序形成新的有序子数组。这一步可以通过循环实现。 增加子数组长度 接着将子数组长度翻倍重复上述合并操作直到整个数组成为一个有序的数组。 值得注意的是归并排序的非递归实现需要考虑如何处理边界情况、子数组长度变化等细节但整体思路和递归实现是类似的。
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;}
}
