数据结构之归并排序

什么是归并排序

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

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~