排序

倒置个数

倒置指的是在数组中出现了逆序。给定一组下标 $(i,j)$，$i<j$ 但是 $A[i]>A[j]$。如何统计倒置的个数呢？

最简单的方法是两层 for 循环，遍历每一组可能的 $(i,j),i<j$，判断是否有 $A[i]>A[j]$，时间复杂度是 $O(n^2)$。

下面分析一种更高效的算法，使用分治法的思想，整体过程类似于归并排序，准确地说，就是一个归并排序，顺带计算了导致个数。

将数组分成两半，那么倒置有三种可能：

1. 两个值都在前半段
2. 两个值都在后半段
3. 两个值分别位于前半段和后半段

前面两种情况容易处理，递归调用即可。如何计算第三种情况的倒置个数呢？下面分析归并两个有序数组和倒置的关系。

假定两个有序数组 $A,B$，长度均为 $n$，归并的时候，$A$ 的第 $i$ 个值和 $B$ 的第 $j$ 个比较，如果 $A$ 的第 $i$ 个值比较小，放到结果数组，这里没有倒置；如果 $A$ 的第 $i$ 个值比较大，那么包含这个值在内的 $A$ 中剩下的值都比 $B$ 的第 $j$ 个值要大，那么有 $n-i+1$ 个倒置，即 $A$ 中未排序的元素个数。

整个算法的时间复杂度与归并排序一致，$O(n\log_n)$。

实现代码参考CountInversion。

Merge Sort

归并排序是一种古老的算法，但仍旧非常实用。

整个算法的基本思想是分治法，使用递归比较容易实现。

如果待排序包含零个和一个元素，已经有序了，直接返回，这是整个递归实现的基本情况。

然后将整个数组分成两半，分别对这两边递归调用归并排序使其有序。

最后，将两半有序的数组合并成一个。合并的逻辑也很简单，每个数组有一个迭代器，比较其大小，较小的复制到有序数组，然后迭代器向后移动一位，直到两个迭代器其中一个结束。如果剩余一个迭代器还有值，直接拷贝到有序数组的尾部即可。

实现代码参考MergeSort。

整个过程上图所示。对于归并函数而言，假定两个数组的长度都是 $l$，那么开销是 $O(l)$。假定第 $i$ 层有 $2^i$ 个子数组，每个数组长度是 $n/2^i$，其中 $n$ 是原始数组的大小，那么每层合并的开销是 $O(n)$。整棵树的高度是 $n\log_2 n+1$，因此归并排序的时间复杂度是 $O(n\log_2 n)$。

Quick Sort