归并排序

要点

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并

归并排序基本思想

将待排序序列$a[0…n-1]$看成是$1$个长度为$n$的有序序列,将相邻的有序表成对归并,得到$2$个长度为$n/2$的有序表;将这些有序序列再次归并,得到$4$个长度为$n/4$的有序序列;如此反复进行下去,最后得到一个长度为$n$的有序序列。

综上可知:

归并排序其实要做两件事:

(1)”分解”—-将序列每次折半划分。

(2)”合并”—-将划分后的序列段两两合并后排序。

我们先来考虑第二步,如何合并?

在每次合并过程中,都是对两个有序的序列段进行合并,然后排序。

这两个有序序列段分别为 $a[l, mid]$ 和 $a[mid+1, r]$。

先将他们合并到一个局部的暂存数组$temp$中,带合并完成后再将$temp$复制回R中。

为了方便描述,我们称 $a[l, mid]$ 第一段,$a[mid+1, r]$ 为第二段。

每次从两个段中取出一个数进行关键字的比较,将较小者放入$temp$中。最后将各段中余下的部分直接复制到$temp$中。

经过这样的过程,$temp$已经是一个有序的序列,再将其复制回$a$中,一次合并排序就完成了。

图示如下

例题 光荣的梦想(求逆序对)

题目描述

Prince对他在这片大陆上维护的秩序感到满意,于是决定启程离开艾泽拉斯。在他动身之前,Prince决定赋予King_Bette最强大的能量以守护世界、保卫这里的平衡与和谐。在那个时代,平衡是个梦想。因为有很多奇异的物种拥有各种不稳定的能量,平衡瞬间即被打破。KB决定求助于你,帮助他完成这个梦想。

一串数列即表示一个世界的状态。

平衡是指这串数列以升序排列,而从一串无序数列到有序数列需要通过交换数列中的元素来实现。KB的能量只能交换相邻两个数字。他想知道他最少需要交换几次就能使数列有序。

输入格式

第一行为数列中数的个数 $ N(n≤100000)$。 第二行为 $ N $ 个数 $ a_1~a_n $ $($每个数小于$100000)$,表示当前数列的状态。

输出格式

输出一个整数,表示最少需要交换几次能达到平衡状态。

样例数据 1

输入

1
2
4
2 1 4 3

输出

1
2

备注

本题另外一种描述: 给定一个序列 $a_1,a_2,…,a_n$,如果存在 $ i < j $ 并且 $ a_i > a_j $,那么我们称之为逆序对,求逆序对的数目。

代码

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cctype>
using namespace std;
/*读入优化*/
inline void R (int &v) {
static char ch;
v = 0;
bool p = 0;
do {
ch = getchar();
if (ch == '-') p = 1;
} while ( !isdigit(ch) );
while ( isdigit(ch) ) {
v = ( v << 1 ) + ( v << 3 ) + ( ch ^ '0' );
ch = getchar();
}
if (p) v = -v;
}
int n, a[1000005], temp[1000005];
long long ans;
/*归并排序求逆序对*/
void mergesort(int l, int r) {
if (l >= r) return;
/*将a序列分为[l,mid]和[mid+1,r]两段*/
int mid = l + r >> 1;
/*先递归使[l,mid]和[mid+1,r]有序*/
mergesort(l, mid), mergesort(mid + 1, r);
int k = 0, i, j;
/* 扫描第一段和第二段序列,直到有一个扫描结束*/
for (i = l, j = mid + 1; i <= mid && j <= r; ) {
/* 判断第一段和第二段取出的数哪个更小,将其存入合并序列,并继续向下扫描*/
if (a[i] <= a[j]) {
temp[++k] = a[i++];
ans += j - mid - 1;
/*若发现有a[i]<=a[j],则于此之前被放入temp中的[mid+1,r]中的数每个为答案贡献1*/
} else {
temp[++k] = a[j++];
}
}
/* 若第一段序列还没扫描完,将其全部复制到合并序列*/
while (i <= mid) {
temp[++k] = a[i++];
ans += j - mid - 1;
}
/* 若第二段序列还没扫描完,将其全部复制到合并序列*/
while (j <= r) {
temp[++k] = a[j++];
}
j = l;
/* 将合并序列复制到原始序列中*/
for (i = 1; i <= k; ++i) {
a[j++] = temp[i];
}
}
int main() {
R(n);
for (int i = 1; i <= n; ++i) {
R(a[i]);
}
mergesort(1, n);
cout << ans;
return 0;
}
文章目录
  1. 1. 要点
  2. 2. 归并排序基本思想
  3. 3. 图示如下
  4. 4. 例题 光荣的梦想(求逆序对)
    1. 4.1. 题目描述
    2. 4.2. 输入格式
    3. 4.3. 输出格式
    4. 4.4. 样例数据 1
    5. 4.5. 输入
    6. 4.6. 输出
    7. 4.7. 备注
  5. 5. 代码