8.2 再谈排序与检索
如何排序
下面将介绍排序函数的工作原理
8.2.1 归并排序
第一种高效算法是归并排序。按照分治三步法，对归并排序算法介绍如下：
划分问题：把序列分成元素个数尽量相等的两半
递归求解：把两半元素分别排序
合并问题：把两个有序表合并成一个
这边的关键在于合并问题的实现，代码实现如下：
点击查看代码
void merge_sort(int* A, int x, int y, int* T) {
if(y-x > 1) {
int m = x + (y-x)/2;//划分，说明不是数组元（也就是最小的单位数组）
int p = x, q = m, i = x;
merge_sort(A, x, m, T);//递归求解，实现[x,m)的排序
merge_sort(A, m, y, T);//递归求解，实现[m,y)的排序
while(p < m || q < y) {//两边都到达边界才是真正的边界条件
if(q >= y || (p < m && A[p] <= A[q])) T[i++] = A[p++];
//从左半数组复制到临时空间，注意这边的q>=y
else T[i++] = A[q++];//从右半数组复制到临时空间
}
for(i = x; i < y; i++) A[i] = T[i];//从辅助空间复制回A数组
}
}
这边有两个关键，首先只要有一个序列非空，就要继续合并，因此在比较时不能直接比较A[p]和A[q]，因为可能其中一个序列为空，从而A[p]或者A[q]代表的是一个实际不存在的元素，正确的方式如下：
1.如果第二个序列为空（此时第一个序列一定非空），复制A[p]
2.否则（第二个序列非空），当且仅当第一个序列也非空，且A[p]<=A[q]的时候，才复制A[p]
上面的代码巧妙地利用短路运算符"||"将两个条件连接起来，如果条件1满足，那么就不会执行条件2，如果条件1不满足，才会执行条件2
T[i++] = P[p++]，复制后移动下标的方式挺重要的
这个时间复杂度和最大连续和的分治算法是O(nlogn)
以下是对归并的一种拓展
逆序对问题
如果n很大，很明显O(n^2)的枚举会超时，受到归并排序的启发，我们同样可以采用，划分问题，递归求解，合并问题的思路来解决
1.把序列元素尽量分成相等的两半
2.递归求解是统计i和j均在左边或者均在右边的逆序对个数
3.统计i在左边，但j在右边的逆序对个数
本题的关键在于对于合并的理解，统计的常见技巧是分类，下面按照j的不同把这些跨越两边的逆序对进行分类，只要对于右边的每个j，统计左边比他大的元素个数f(j)，则所有f(j)之和便是答案
归并排序可以顺便完成f(j)的计算（感觉该递归求解的过程，改变小区域，但是不影响大区域的答案，同时进行分类，非常巧妙，对于子问题的改造，可能简化父问题）
由于合并操作是从小到大进行的，当右边的A[j]复制到T中，左边还没来得及复制到T的那些数就是左边所有比A[j]大的数，此时在累加器中加上左边元素个数m-p即可，左边所剩的元素在区间[p,m)，因此元素个数为m-p
代码实现如下：
点击查看代码
#include
using namespace std;
typedef unsigned long long ull;
constexpr int MAXN = 5*10e5 + 10;
int n, num[MAXN];
ull merge(int x, int y) {
if(x+1 == y) return 0;
int m = x + (y-x)/2;
ull cnt = 0, l = merge(x, m), r = merge(m, y);
int pos = 0, i = x, j = m, temp[y-x];
while(i < m || j < y) {
if(j == y || (i < m && num[i] <= num[j])) { cnt += j-m; temp[pos++] = num[i++]; }
else { temp[pos++] = num[j++]; }
}
for(int i = 0; i < pos; i++) num[x+i] = temp[i];
return l+r+cnt;
}
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", &num[i]);
cout << merge(0, n) << endl;
return 0;
}
归并排序的时间复杂度为O(nlogn)，对该算法稍加修改，可以统计序列中的逆序对的个数，时间复杂度不变