数据结构之归并排序
什么是归并排序
归并排序是一种采用了分治法的高速排序算法，它通过不断递归自身，将要被排序的数列分成两部分进行排序。再将已排序的两部分数列合并起来即可。整个算法的关键在与合并两个数列的函数，它必须是一个时间复杂度为O(n1+n2)的函数。
归并排序由分割数列的函数和组合数列的函数组成，整体时间复杂度为O(nlogN)，这相比于前面的O(N²)的初等排序算法来说，提速是很明显的。
并且，归并排序是稳定排序算法。在合并数组的时候，只要保证前一个数列的优先级高于后一个数列，那么相同元素的顺序就不会颠倒。所以它是一个稳定排序。
算法实现
归并排序实质就是把一个数列分割成两个，再把每个子列再分割，直到无法再分为止，然后用一个函数来把排序好的子列组装起来。
这就是递归与分治问题的一种。
为了简化merge函数的实现，我们在前一个列和后一个列的末位添加一个很大很大的数，那么就能防止计数器越过n1、n2,并且能防止两个标记元素互相比较。
啊感觉有点复杂，还是赶紧上代码吧，这样或许能帮助理解。
问题
问题出自：
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_B
翻译过来就是根据归并排序的原理，编写一个归并排序的程序，并且输出排序后的结果以及排序过程中比较的次数。
代码实现
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
vector<unsigned int> vect;
unsigned int js=0;
void _Merge(vector<unsigned int> &a, int left, int mid, int right)
{
int n1 = mid-left;
int n2 = right - mid;
vector<unsigned int> L,R;
for(int i=0;i<n1;i++)
L.push_back(a[left+i]);
for(int i=0;i<n2;i++)
R.push_back(a[mid+i]);
L.push_back(1000000009);
R.push_back(1000000009);
int m=0,n=0;
for(int i=left;i<right;i++)
{
if(L[m]<=R[n])
{
a[i]=L[m];
m++;
}
else
{
a[i]=R[n];
n++;
}
}
js += m+n;
}
void mergeSort(vector<unsigned int> &a,int left, int right)
{
if(left+1<right)
{
int mid = (left+right)/2;
mergeSort(a,left,mid);
mergeSort(a,mid,right);
_Merge(a,left,mid, right);
}
}
int main()
{
int n;
cin>>n;
unsigned int tmp;
for(int i=0;i<n;i++)
{
cin>>tmp;
vect.push_back(tmp);
}
mergeSort(vect,0,n);
for(int i=0;i<n;i++)
{
cout<<vect[i];
if(i!=n-1) cout<<" ";
}
cout<<endl<<js<<endl;
}归并排序虽然高效且稳定，但是由于采用了递归的方式来实现，在运行的时候会占用更多的内存空间，当然，在题目限制范围之内，这个没啥问题的。毕竟，这个题限制的内存使用量是128MB，我这个程序才用了7.6MB的内存呢！所以内存的问题在这里是不用担心的。
转载请注明来源：https://www.longjin666.cn/?p=460
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021年12月27日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
