简介

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

1、分

对集合不断进行拆分，直至集合中只剩一个元素为止。

void Mergesort(int left,int right)
{
if(left<right)
{
int mid=(left+right)/2;
Mergesort(left,mid);
Mergesort(mid+1,right);
Merge(left,right);
}
}

2、治(合并相邻有序子序列)

调用合并排序算法，将每一个子集合的元素进行排序，并将排序后的结果保存在临时数组中，再将临时数组赋值给初始数组即可

void Merge(int left,int right)
{
int mid=(left+right)/2;
int i=left;
int j=mid+1;
int t=0;
while(i<=mid&&j<=right)
{
if(a[i]<=a[j])temp[t++]=a[i++];
else temp[t++]=a[j++];
}
while(i<=mid)temp[t++]=a[i++];//将左边剩余元素填充进temp中
while(j<=right)temp[t++]=a[j++];//将右序列剩余元素填充进temp中
    t=0;
// cout<<"xwhdewjdb"<<endl;
//将temp中的元素全部拷贝到原数组中
while(left<=right)
{
// cout<<a[left]<<"  ";
        a[left++]=temp[t++];
}
// cout<<"加速度快的---------------"<<endl;
}

完整代码：

#include<bits/stdc++.h> 
using namespace std; 
int temp[1005],a[1005];//临时数组
void Merge(int left,int right)
{
    int mid=(left+right)/2;
    int i=left;
    int j=mid+1;
    int t=0;
    while(i<=mid&&j<=right)
    {
        if(a[i]<=a[j])temp[t++]=a[i++];
        else temp[t++]=a[j++];
    }
    while(i<=mid)temp[t++]=a[i++];//将左边剩余元素填充进temp中
    while(j<=right)temp[t++]=a[j++];//将右序列剩余元素填充进temp中
    t=0;
   // cout<<"xwhdewjdb"<<endl;
    //将temp中的元素全部拷贝到原数组中
    while(left<=right)
    {
       // cout<<a[left]<<"  ";
        a[left++]=temp[t++];
    }
   // cout<<"加速度快的---------------"<<endl;
}
void Mergesort(int left,int right)
{
    if(left<right)
    {
        int mid=(left+right)/2;
        Mergesort(left,mid);
        Mergesort(mid+1,right);
        Merge(left,right);
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    Mergesort(0,n-1);
    int flag=0;
    for(int i=0;i<n;i++)
    {
        if(i==n-1)
        {
            cout<<a[i]<<endl;
            continue;
        }
        if((i+1)%10==0)cout<<a[i]<<endl;
        else cout<<a[i]<<' ';
    }
}