归并排序

我会带着你远行 2022-06-18 12:08 39阅读 0赞

> 归并排序  
> 时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte  
> 总提交 : 1600 测试通过 : 605  
> 比赛描述  
> 给定输入排序元素数目n和相应的n个元素，写出程序，利用内排序算法中归并排序算法进行排序，并输出排序最后结果的相应序列。
> 
> 输入
> 
> 共两行，第一行给出排序元素数目n，第二行给出n个元素，1≤n≤100000，每个元素值范围为 \[0，100000)  
> 输出  
> 一行，输出排序结果。  
> 样例输入  
> 7  
> 48 36 68 72 12 48 2
> 
> 样例输出  
> 2 12 36 48 48 68 72

> 归并排序：是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。  
> 归并过程为：比较a\[i\]和a\[j\]的大小，若a\[i\]≤a\[j\]，则将第一个有序表中的元素a\[i\]复制到r\[k\]中，并令i和k分别加上1；否则将第二个有序表中的元素a\[j\]复制到r\[k\]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间\[s,t\]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间\[s,t\]。

> 核心代码：

void arry_add(int a[],int l,int mid,int r,int tmp[])
    {
        if(l >= r)
            return;
        int i = l;
        int j = mid + 1;
        int k = 0;
        while(i <= mid && j <= r)
        {
            if(a[i] <= a[j])
                tmp[k++] = a[i++];
            else 
                tmp[k++] = a[j++];
        }
        while(i <= m)
            tmp[k++] = a[i++];
        while(j <= n)
            tmp[k++] = a[j++];
        for(int i=0;i<k;i++)
        {
            a[l + i] = tmp[i];
        }
    }
    void merge_sort(int a[],int l,int r)
    {
        if(l >= r)
            return;
        int mid = (l + r) >> 1;
        merge_sort(a,l,mid);
        merge_sort(a,mid+1,r);
        arry_add(a,l,mid,r);
    }

> AC代码：

#include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    typedef long long ll;
    ll a[100000];
    ll n;
    ll tmp[100000];
    void arry_add(ll a[],ll l,ll mid,ll r)
    {
        if(l >= r)
            return;
        ll i = l;
        ll j = mid + 1;
        ll k = 0;
        while(i <= mid && j <= r)
        {
            if(a[i] <= a[j])
                tmp[k++] = a[i++];
            else
                tmp[k++] = a[j++];
        }
        while(i <= mid)
            tmp[k++] = a[i++];
        while(j <= r)
            tmp[k++] = a[j++];
        for(int i=0;i<k;i++)
        {
            a[l + i] = tmp[i];
        }
    }
    void merge_sort(ll a[],ll l,ll r)
    {
        if(l >= r)
            return;
        int mid = (l + r) >> 1;
        merge_sort(a,l,mid);
        merge_sort(a,mid+1,r);
        arry_add(a,l,mid,r);
    }
    int main()
    {
        cin>>n;
        for(ll i=0;i<n;i++)
        {
            cin>>a[i];
        }
        merge_sort(a,0,n);
        for(ll i=1;i<=n;i++)
        {
            if(i!=n)
                cout<<a[i]<<" ";
            else cout<<a[i];
        }
        cout<<endl;
        return 0;
    }