逆序数问题是这样的一个问题：给定一个不含重复元素的序列<a
1, a
2, ..., a
n>，对于元素a
i，若从a
1~a
i-1这i - 1个数中有k个数是比a
i大的，那么a
i的逆序数就是k，其中序列中的元素是可进行大小比较的。那么如何求一个序列的所有逆序的数量的总和呢？
我们可以考虑试试分治法，对于序列<a
1, a
2, ..., a
n>，我们可否先求<a
1, a
2, ..., a
n/2>和<a
n/2+1, a
n/2+2, ..., a
n>两个序列的各自的逆序数，然后再将两个逆序数相加是否就得到了总的逆序数呢？其实先求两个子序列的逆序数没有问题，直接相加也没问题，问题就出在，上述解法还漏掉了在子序列1中的元素比子序列2中的元素大的那种逆序，也就是跨越两个子序列的逆序。其实也就是下面的公式：T(n) = 2T(n/2) + T(merge)。关键问题就是如何求T(merge)。若序列seq1<a
1, a
2, ..., a
n/2>和序列seq2<a
n/2+1, a
n/2+2, ..., a
n>都是无序的，那么要找seq1中比a
n/2+i大的元素的数量则必须遍历seq1，这时候T(merge)的时间复杂度为O(n
2)。那么T(n) = 2T(n/2) + O(n
2)。总的时间复杂度太高。这样的merge不理想。那么如果seq1和seq2已经各自有序了呢？我们该如何merge呢？为了保持在递归过程中始终使子序列有序，我们每次merge后的序列都必须是有序的，所以这就个merge的过程就成了归并排序的merge过程了！！！关键就是在归并排序merge过程中该如何正确记录两个子序列之间的逆序数呢？归并排序其实就是对两个子序列，两个index i和j依次向后扫，对seq1[i]和seq2[j]做判断，若seq1[i]比seq2[j]大，则j++；若seq1[i]比seq2[j]小，则i++；我们仔细想想其实不难发现，若seq1[i]比seq2[j]小，那么seq2[1]~seq2[j - 1]肯定都比seq1[i]小，这时候由seq1[i]决定的逆序数肯定为1 ~ j - 1；若seq1[i]比seq2[j]大，那么由于seq1[i]还有可能比seq2[j]后面的元素大，所以我们不计算。最后i和j有一个走到尾部之后，若seq1[]还有元素没有被扫描过，那么这些剩余的未被扫描的元素肯定比seq2[]中的所有元素都大，所以剩余这些的逆序数为seq1[]中剩余的元素数量 * seq2[]中总元素的数量。
根据poj2299(ultra quicksort)题目写的程序比较容易理解：
1 #include <cstdio>
2 #include <cstdlib>
3
4 #define MAX 500005
5 int a[MAX];
6
7 long long merge(int *array, int low, int mid, int high) {
8 if (!array) {
9 return 0;
10 }
11 long long res = 0;
12 int *buf = (int *)malloc(sizeof(int) * (high - low + 1));
13 int i = low, j = mid + 1, k = 0;
14 while (i <= mid && j <= high) {
15 if (array[i] < array[j]) {
16 buf[k++] = array[i++];
17 res += j - mid - 1; //逆序数
18 } else {
19 buf[k++] = array[j++];
20 }
21 }
22 while (i <= mid) {
23 buf[k++] = array[i++];
24 res += high - mid;
25 }
26 while (j <= high) {
27 buf[k++] = array[j++];
28 }
29 for (i = 0; i < k; ++i) {
30 array[low + i] = buf[i];
31 }
32 free(buf);
33 return res;
34 }
35
36 long long merge_sort(int *array, int low, int high) {
37 if (!array || low >= high) {
38 return 0;
39 }
40 int mid = (low + high) / 2;
41 long long res1 = merge_sort(array, low, mid);
42 long long res2 = merge_sort(array, mid + 1, high);
43 long long res3 = merge(array, low, mid, high);
44 return res1 + res2 + res3;
45 }
46
47 int main() {
48 int n;
49 while (scanf("%d", &n), n) {
50 int i;
51 for (i = 0; i < n; ++i) {
52 scanf("%d", &a[i]);
53 }
54 printf("%lld\n", merge_sort(a, 0, n - 1));
55 }
56 return 0;
57 }
另外这道题目其实还可以用线段树来解决，和上篇文章中秋stars的level的很像，stars那道题目是求序列中所有在自己前面的不大于自己值的数的数量。而逆序数是求所有在自己前面的大于自己值的数的数量。用同样的方法就可以解决，只不过由于该题的a[i]值比较大，最大值为999999999，这样的线段树太耗费内存。
到此时，其实上面的算法都比较常规，大部分人都知道求逆序数该用归并排序做，但是其实告诉大家一个事实，一个类似快排的树形结构，二叉排序树BST其实也可以做。只不过在二叉排序树的每个节点中都记录一个新的值，该值表示当前节点的右子树有多少个节点。具体算法不讲了，很简单，看代码：
1 #include <cstdio>
2 #include <cstdlib>
3
4 #define MAX 500005
5
6 struct BST {
7 int value;
8 int larger;
9 BST *left;
10 BST *right;
11 };
12
13 BST* insert(BST *t, int x, long long *count) {
14 if (!t) {
15 t = (BST *)malloc(sizeof(BST));
16 t->value = x;
17 t->larger = 0;
18 t->left = t->right = NULL;
19 return t;
20 }
21 if (t->value > x) {
22 (*count) += 1 + t->larger;
23 t->left = insert(t->left, x, count);
24 } else {
25 (t->larger)++;
26 t->right = insert(t->right, x, count);
27 }
28 return t;
29 }
30
31 void release(BST *t) {
32 if (!t) {
33 return;
34 }
35 release(t->left);
36 release(t->right);
37 free(t);
38 }
39
40 int main() {
41 int n;
42 while (scanf("%d", &n), n) {
43 int i, tmp;
44 long long res = 0;
45 BST *root = NULL;
46 for (i = 0; i < n; ++i) {
47 scanf("%d", &tmp);
48 root = insert(root, tmp, &res);
49 }
50 printf("%lld\n", res);
51 release(root);
52 }
53 return 0;
54 }
但是考虑到二叉排序树在最差情况下的性能为O(n
2)的，所以用二叉排序树的算法会比采用归并排序的算法慢，时间为2700MS。这里要说明的是这里讲用二叉排序树来求逆序数只是讲这种思想，平均时间性能肯定没有归并排序快，但是这种思想还是需要仔细揣摩揣摩的。
posted on 2012-09-15 14:56
myjfm 阅读(2855)
评论(0) 编辑 收藏 引用 所属分类:
算法基础