并归排序+P1136求逆序对个数

并归排序

介绍

说道并归排序,其实运用到了递归,首先将一个很大很大的数分割为两个两个的,然后让这两个数进行比较排序,比较之后返回上一级,然后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;
}