![](https://csdnimg.cn/release/download_crawler_static/87264969/bg5.jpg)
给一列 a
1
,a
2
,…,a
n
,求它的逆序对数,即有多少个有序对(i,j),使得 i<j 但 a
i
>a
j
。n
可以高达 10
6
。
【分析】
受到归并排序的启发,可以用“分治三步法”来做:
(1)划分问题:把序列分成元素个数尽量相等的两半;
(2)递归问题:统计 i 和 j 均在左边或者均在右边的逆序对个数;
(3)合并问题:统计 i 在左边,但 j 在右边的逆序对个数。
解决本问题的关键在于合并:如何求出 i 在左边,而 j 在右边的逆对序对数目呢:按照
j 的不同把这些“跨越两边”的逆序对进行分类:只在对于右边的每个 j,统计左边比它大
的元素个数。对于合并操作是从小到大进行的,当右边的 A[j]复制到 T 中时,左边还没有
来得及复制到 T 的那些数就是左边所有比 A[j]大的数,此时累加器中加上左边元素个数 m-p
即可(左边所剩的元素在区间[p,m]中,因此元素个数为 m-p)。
完整的程序如下:
#include <stdio.h>
int A[] = {8,7,6,5,4,3};
int T[] = {0,0,0,0,0,0};
void inverse_pair(int* A, int x, int y, int* cnt, int* T) {
if(y-x > 1){
int m = x + (y-x)/2; //划分
int p = x, q = m, i = x;
inverse_pair(A, x, m, cnt, T); //递归求解
inverse_pair(A, m, y, cnt, T); //递归求解
while(p < m || q < y) {
if(q >= y || (p < m && A[p] <= A[q])) /从左半数组复制到临时空间
T[i++] = A[p++];
else { //从右半数组复制到临时空间
T[i++] = A[q++];
*cnt += m-p; //计算逆序对数
}
}
for(i = x; i < y; i++) A[i] = T[i]; //从辅助空间复制到 A 数组
}
}
int main(){
int i, cnt = 0;;
inverse_pair(A, 0, 6, &cnt, T);
printf("%d\n", cnt);
return 0;
}
8.2.2 快速排序
快速排序由 Hoare 于 1962 年提出,相对归并排序来说不仅速度更快,并且不需要辅助
空间。按照分治三步法,将快速排序算法作如下介绍。
(1)划分问题:数组的各个元素重排后分成左右两部分,使得左边的任意元素都小于
或等于右边的任意元素。
(2)递归问题:把左右两部分分别排序;
(3)合并问题:不用合并,因为此时数组已经完全有序。
例 8-3 第 k 小的数。
输入 n 个整数和一个正整数(1≤k≤n),输入这些整数从小到大排序后的第 k 个(例如,
k=1 就是最小值)。n≤10
7
。