二分归并排序c++

本文主要是介绍二分归并排序c++，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1.问题
二分归并排序：对n个不同的数构成的数组A[1…n]进行排序，其中n=2^k
2.解析
把数组分为两部分，从中间隔开，把这两部分分别存入left，right数组中，对两个数组分别进行遍历，在遍历的同时比较两个数组中的值。这个步骤进行完后，数组中的元素不一定是按从小到大的顺序。只是其中一部分排好了序。这时候需要对数组进行递归，直到拆分的数组长度已经是1，就是只含有一个数。左右只含有一个元素，进行大小比较，依次再向上递归。可以得到排好序的数组了。
3.设计
//定义MergeSort函数,参数为数组a，左标记L，右标记R
void MergeSort(int a[],int L,int R){
//递归需要边界，当左标记L和右标记R相撞时，也就是说此时拆分的数组长度size已经是1
if(R==L){
return ;//返回空值
}
//合并用的M
int M=(L+R)/2;//向下取整，所以合并的时候需要计算left长度时需要M+1,右部分的开始也需要M+1;
MergeSort(a,L,M);//左部分依次向下拆分递归
MergeSort(a,M+1,R);//右部分依次向下拆分递归
//最后再依次向上归并
Merge(a,L,M,R);
}

4.分析
算法时间复杂度：O(n log n)
5.源码
https://github.com/Lily-blog/boostore

这篇关于二分归并排序c++的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！