网站开发公司巨推,青岛新公司网站建设推广,视频直播网站建设费用,排行榜123网本文旨在讲解归并排序的实现#xff08;递归及非递归#xff09;搬好小板凳#xff0c;干货来了#xff01; 前序#xff1a;
在介绍归并排序之前#xff0c;需要给大家介绍的是什么是归并#xff0c;归并操作#xff0c;也叫归并算法#xff0c;指的是将两个顺序序列…本文旨在讲解归并排序的实现递归及非递归搬好小板凳干货来了 前序
在介绍归并排序之前需要给大家介绍的是什么是归并归并操作也叫归并算法指的是将两个顺序序列合并成一个顺序序列的方法相信不少小伙伴之前都做过合并两个有序链表或者两个有序数组的例题归并就是将两个数组或链表合并成一个链表或数组还得保证与其原来的顺序相同那么归并排序就是用到了归并这个思想将一组元素完成排序的算法 归并排序的介绍
归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序的时间复杂度和空间复杂度
时间复杂度ON*logN因为其是一种二叉树结构其高度为logN,每层需要排序的个数都是N个所以其时间复杂度为ON*logN。
空间复杂度因为创建了一个新的数组所以其空间复杂度为ON 归并排序的思想与思路
归并排序就是本质上是分治的方法来实现的是将一组数据分割成若干组有序数组然后对这若干个有序数组两两进行归并即可得到我们想要的排序 归并排序的思路图 归并排序的动态图展示 归并排序的大致实现思路
归并排序其实现的思路其实很简单就是将一组数据分割分割到若干组有序数组然后两两进行归并那么如何保证分割的数组为有序数组呢这其实很简单当分割到数组中只有一个元素的时候那么该数组就是有序的数组了然后进行归并拷贝到原数组上即可 归并排序的代码实现
C版本递归
void _MergeSort(int* a, int left, int right, int* tem)
{//当再次需要调用的区间不存在时返回即可if (left right) //很显然left不会大于right保险起见加上大于条件没有影响{return;}//每次取出中间坐标用于下次的左半边的递归右半边递归同理int mid (left right) / 2;_MergeSort(a, left, mid, tem);_MergeSort(a, mid 1, right, tem);//到此分割区间已经结束每组区间都能保证时有序的了下一步就开始进行归并int begin1 left, end1 mid;int begin2 mid 1, end2 right;int i left; //i用于对tem数组的下标进行表示//下面开始归并两个有序数组当两个有序数组其中一个遍历完成就退出循环while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tem[i] a[begin1];}else{tem[i] a[begin2];}}while (begin1 end1){tem[i] a[begin1];}while (begin2 end2){tem[i] a[begin2];}//归并结束后将tem数组中的数据拷贝到元素组中相应的位置即可memcpy(a left, tem left, sizeof(int)*(right - left 1));//个数为右边界减去左边加1因为为闭区间//至此归并结束拷贝结束!
}
void MergeSort(int* a, int n)
{//在堆上申请开辟一个tem数组用来最后拷贝到原数组中int* tem (int *)malloc(sizeof(int) * n);//因为存在递归的调用所以再创建一个函数若仍在此函数上重复调用时则会重复开辟新的空间可能导致空间不足_MergeSort(a, 0, n - 1, tem);//用完之后释放到tem数组free(tem);
}
需要注意的是当进行递归归并排序的时候需要注意返回的条件当区间不存在或者区间内部只有一个元素的时候就可以返回了还需要注意的是因为要进行拷贝不能在原数组上直接拷贝所以需要创建一个新的数组用来存储归并后的元素的位置最后归并结束重新拷贝到原数组中即可 C版本非递归
分段拷贝
// 归并排序非递归实现//思路如下要想实现归并排序的非递归那么需要注意分组从每组一个元素开始因为当只有一个元素的时候默认是有序的然后
//进行归并拷贝即可每组一个元素遍历结束之后进行每组两个依次进行每组2倍个元素进行归并当每组的元素为所有元素的一半或大于一半
//即可完成排序需要特别注意的是进行非递归归并排序的时候需要注意区间的取值在此有两个拷贝方式一种是整体拷贝一组是归并一段拷贝一段//进行非递归实现归并的时候也需要创建一个新的数组不能在原数组上进行对数据的改变因为可能会造成数据的覆盖导致数据不能完成排序
//创建一个新数组然后让每组元素为一个依次递增二倍进行归并拷贝直至每组的元素个数大于数组个数结束归并即可完成排序//下面先来进行分段拷贝
//void MergeSortNonR(int* a,int n)
//{
// //注意gap代表的是每组归并时的元素的个数
// int gap 1;
// int* tem (int*)malloc(sizeof(int) * n);
// while (gap n) //当gap大于n时结束循环即可完成
// {
// int j 0;
// //每组为一个的进行遍历
// for (int i 0; i n ; i2*gap)
// {
//
// //每组个数为1的进行归并排序
// //区间范围如下!
// int begin1 i, end1 i gap - 1;
// int begin2 i gap, end2 i 2 * gap - 1;
//
// //当end1n,begin2n时不需要进行归并
// if (end1 n||begin2n)
// {
// break;
// }
//
// //对end2边界进行修改
// if (end2 n)
// {
// end2 n-1;
// }
//
// //开始进行归并拷贝
// while (begin1 end1 begin2 end2)
// {
// if (a[begin1] a[begin2])
// {
// tem[j] a[begin1];
// }
// else
// {
// tem[j] a[begin2];
// }
// }
// while (begin1 end1)
// {
// tem[j] a[begin1];
// }
// while (begin2 end2)
// {
// tem[j] a[begin2];
// }
//
// //注意需要注意的是当求元素的个数时应该用end2-i,不能减去begin1因为begin1每次都会改变记录的不再是数组开始拷贝的地方
// memcpy(a i, tem i, sizeof(int) * (end2 - i 1));
// }
// gap * 2;
// }
// free(tem);
//}
整体拷贝
//整段拷贝
void MergeSortNonR(int* a, int n)
{//注意gap代表的是每组归并时的元素的个数int gap 1;int* tem (int*)malloc(sizeof(int) * n);while (gap n) //当gap大于n时结束循环即可完成{//j的声明必须写在for循环的外面因为若写到for循环内部时在每组循环都会将原来归并好的数据放到前面的那些位置//导致以及归并好的又被覆盖导致排序失败每组的归并都放在前两组内部导致不能将全部归并结束int j 0;//每组为一个的进行遍历for (int i 0; i n; i 2 * gap){//每组个数为1的进行归并排序//区间范围如下!int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;//当end1n,begin2n时不需要进行归并if (end1 n){end1 n - 1;//将第二块区间设置为不存在的区间如果设置为n-1那么会造成对最后一个数据的重复使用拷贝导致排序错误begin2 n;end2 n - 1;}else if (begin2 n){begin2 n;end2 n - 1;}else if(end2n){end2 n - 1;}//开始进行归并拷贝while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tem[j] a[begin1];}else{tem[j] a[begin2];}}while (begin1 end1){tem[j] a[begin1];}while (begin2 end2){tem[j] a[begin2];}//注意需要注意的是进行整段拷贝的时候不需要再从abegin1的位置开始拷贝啦直接将所有tem中的元素拷贝到原数组即可}memcpy(a, tem, sizeof(int) * n);gap * 2;}free(tem);
}
需要注意的是非递归的归并排序整体拷贝和分段拷贝大致思路是一样的只是最后进行memcpy的起始位置和个数有所不同相关细节与思路都在源代码上加有注释标明需要注意的是当进行整体拷贝的时候用于标记tem数组的j的坐标的定义一定要在for循环外部定义赋值若在内部赋值定义则每进行一次都会覆盖原来已经归并好的数据上面导致归并排序不能正确进行 今日的归并排序分享到此结束欢迎大家积极评论支持。若有不足及补充及时提出必将改正
