c++实现二路归并排序的示例代码
二路归并排序
基本思想
二路归并排序就是将两个有序子表归并成一个有序表。首先我们得有一个算法用于归并：两个有序表放在同一数组的相邻位置上，arr[left]到arr[center-1]为第一个有序表，arr[center]到arr[right]是第二个有序表。每次从两端中取出一个进行比较，小的先放在一个temp数组，最后将比较剩下的直接放到temp中去，最后将temp又复制回arr。这是“治”。
所谓“分”，就是递归地将前半部分和后半部分的数据各自归并排序即可。
算法分析
每一趟归并的时间复杂度为O(n)，共需要进行⌈log2n⌉趟。对应的算法的时间复杂度为O(nlog2n)。归并排序的空间复杂度O(n)。另外，归并排序中归并的算法并不会将相同关键字的元素改变相对次序，所以归并排序是稳定的。
二路归并排序的前提是两个序列本身有序。
voidMerger(int*arr,intlen,intwidth)
{
int*temp=(int*)malloc(sizeof(int)*(len));
//首先对两路下标分别进行初始化
intl1=0;
inth1=l1+width-1;
intl2=h1+1;
inth2=l2+width-1
PS:二路合并排序算法
#include
usingnamespacestd;
classSortableList
{
public:
SortableList(intmSize)
{
maxSize=mSize;
l=newint[maxSize];
n=0;
}
~SortableList()
{
delete[]l;
}
voidMerge(int,int,int);
voidMergeSort(int,int);
voidInput();
voidOutput();
private:
int*l;
intmaxSize;
intn;
};
voidSortableList::Input()
{
cout<<"请输入要排序的数：";
for(inti=0;i<=maxSize-1;i++)
cin>>l[i];
}
voidSortableList::Output()
{
cout<<"排序后的数是：";
for(inti=0;i<=maxSize-1;i++)
cout<>m;
SortableLista1(m);
a1.Input();
a1.MergeSort(0,m-1);
a1.Output();
}
到此这篇关于c++实现二路归并排序的示例代码的文章就介绍到这了,更多相关c++二路归并排序内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票！