什么是归并排序
归并排序是一种采用了分治法的高速排序算法,它通过不断递归自身,将要被排序的数列分成两部分进行排序。再将已排序的两部分数列合并起来即可。整个算法的关键在与合并两个数列的函数,它必须是一个时间复杂度为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