并归排序

介绍

说道并归排序，其实运用到了递归，首先将一个很大很大的数分割为两个两个的，然后让这两个数进行比较排序，比较之后返回上一级，然后4个4个比较，首先举个例子：

举例讲解

初始数据：4 3 5 9 6 2 8 1

分割：4 3 5 9 6 2 8 1

比较：3 4 5 9 2 6 1 8

合并：（1）：3 4 5 9

首先3和5比较 3进队：3

（2）： 4 5 9

然后5和4比较 4进队：3 4

（3）： 5 9

然后5进队 3 4 5

（4）： 9

最后9进队 3 4 5 9

相同的方法合并2 6 1 8

然后把两个有序数列再次排序：

3 4 5 9 1 2 6 8

1和3比较 1进队：1

2和3比较 2进队：1 2

6和3比较 3进队：1 2 3

6和4比较 4进队：1 2 3 4

……

最后9进队：1 2 3 4 5 6 8 9

这里特别说明一下：我们在比较的时候，给两个有序数列分别记录下来比到哪里了,不如我们可以用a=1，b=1分别表示两个有序数列分别记录下来比较到了哪个数。

举个例子

3 4 5 9 1 2 6 8

1和3比较 1进队：1

那么现在因为第二个数列的一个数进队，那么下一次就该第二个去比较，所以b++即b=2；a不变为1；

2和3比较 2进队：1 2

现在因为是第二个数列又有一个数进队，所以下次要拿下一个数去比较
，则b++,a不变；

如果第一个数列有数进队的话，a是需要++的；

这就是抽风的并归排序！

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
long long a[1000001],c[1000001],n;
void Merge(int tall,int end)
{
    int mid,well,i,j;
    if(tall+1<end)
    {
        mid=(tall+end)/2;
        Merge(tall,mid-1);
        Merge(mid,end);
        well=1;
        for(i=tall,j=mid;i<=mid-1&&j<=end;)
        {
            if(a[i]>a[j])
                c[well++]=a[j++];
            else c[well++]=a[i++];
        }
        if(j<=end) for(;j<=end;)
        c[well++]=a[j++];
        else for(;i<=mid-1;)
        c[well++]=a[i++];
    }
    else
    {
        if(tall+1==end)
        {
        if(a[tall]>=a[end])
        swap(a[tall],a[end]);
        cout<<a[tall]<<' '<<a[end]<<endl;
        }
        return;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    Merge(1,n);
    for(int i=1;i<=n;i++)
    cout<<c[i]<<' ';
    return 0;
}