逆序數問題是這樣的一個問題：給定一個不含重復元素的序列<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 閱讀(2900)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎