整站下载器 做网站地图,seo技巧课程,上海市人才服务中心网首页,做黄金期货的网站目录
一#xff0c;归并排序#xff08;递归#xff09;
1#xff0c;基本思想 2#xff0c;思路实现
二#xff0c;归并排序#xff08;非递归#xff09;
1#xff0c;思路实现
2#xff0c;归并排序的特性总结#xff1a; 一#xff0c;归并排序#xff0…
目录
一归并排序递归
1基本思想 2思路实现
二归并排序非递归
1思路实现
2归并排序的特性总结 一归并排序递归
1基本思想 归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide and Conquer的一个非常典型的应用 将已有序的子序列合并得到完全有序的序列 即先使每个子序列有序再使子序列段间有序若将两个有序表合并成一个有序表称为二路归并 归并排序核心步骤 2思路实现
这个归并排序乍一看像一颗二叉树事实也是如此如上图所示我们需要不断的拆分直至拆成一个元素此时就是有序的然后再合并合并的时候不要选择原地合并原地合并时间复杂度很高需要开辟与数组同等大小的空间用来存放数据
主函数整体框架
//归并排序
void MergerSort(int* arr, int begin, int end)
{if (begin end){return;}//开辟同等大小数组int* tmp (int*)malloc((end - begin 1)*sizeof(int));//归并Merger(arr, tmp, begin, end);free(tmp);tmp NULL;
}
然后我们就要开始实现 Merger 函数是数据归并了
把数组拆分成一个数据后开始合并刚开始一 一合并然后二 二合并然后四 四合并直至全数组合并完
//归并
void Merger(int* arr, int* tmp,int begin,int end)
{int mid (begin end) / 2;if (begin end){return;}//排序【begin,mid】 【mid1,end】Merger(arr, tmp, begin,mid);Merger(arr, tmp, mid1, end);int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int i 0;while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2]){tmp[i] arr[begin1];}else{tmp[i] arr[begin2];}}while(begin1 end1){tmp[i] arr[begin1];}while (begin2 end2){tmp[i] arr[begin2];}//进行拷贝memcpy(arr begin, tmp, (end - begin1)*sizeof(int));
}
然后我们运行测试一下 可以看到是有序的选择排序就 OK 了 其实跟二叉树的前序遍历有异曲同工之处前后知识都是连贯起来的 二归并排序非递归
1思路实现
现在我们来拿捏一下非递归版的归并排序其实也还是换汤不换药 其实新思路是这个图的下半部分我们先让数据一 一合并然后再二 二合并然后再四 四合并程倍数增长有人问如果越界了怎么办没关系我们后面会做越界处理的
直接上代码
//归并排序(非递归)
void MergerSortNon(int* arr, int begin, int end)
{if (begin end){return;}//开辟同等大小数组int* tmp (int*)malloc((end - begin 1) * sizeof(int));int gap 1;int j 0;while (gap end){for (j 0; j end; j 2 * gap){int begin1 j, end1 begin1gap-1;int begin2 end11, end2 begin2gap-1;int i 0;//处理边界问题if (end1 end){break;}if (end2 end){end2 end;}while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2]){tmp[i] arr[begin1];}else{tmp[i] arr[begin2];}}while (begin1 end1){tmp[i] arr[begin1];}while (begin2 end2){tmp[i] arr[begin2];}//进行拷贝memcpy(arr j, tmp, (end2 - j 1) * sizeof(int));}gap * 2;}free(tmp);tmp NULL;
}
我们来运行测试一下 可以看到是有序的选择排序就 OK 了 2归并排序的特性总结
1 归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题
2 时间复杂度O(N*logN)
3 空间复杂度O(N)
4 稳定性稳定 第四阶段就到这里了带大家继续吃肉
后面博主会陆续更新
如有不足之处欢迎来补充交流
完结。。
