POJ 2299 Ultra-QuickSort 归并排序、二叉排序树，求逆序数

题意就是求冒泡排序的交换次数，显然直接冒泡会超时，所以需要高效的方法求逆序数。

利用归并排序求解，内存和耗时都比较少，但是有编码难度。。

二叉排序树，内存巨大，时间复杂度高，但是非常好写。。

归并排序版本：

 1 #include <stdio.h>
 2 #include <string.h>
 3 long long merge_arr(int arr[], int first, int mid, int last, int tmp[])
 4 {
 5     long long ret = 0;
 6     int i = first, j = mid+1, k = 0;
 7     while(i <= mid && j <= last)
 8     {
 9         if(arr[i] < arr[j])
10         {
11             tmp[k++] = arr[i++];
12             ret += j - mid - 1;
13         }
14         else tmp[k++] = arr[j++];
15     }
16     while(i <= mid)
17     {
18         tmp[k++] = arr[i++];
19         ret += last - mid;
20     }
21     while(j <= last)
22         tmp[k++] = arr[j++];
23     for(i = 0; i < k; i++)
24         arr[first+i] = tmp[i];
25     return ret;
26 }
27 
28 long long merge_sort(int arr[], int first, int last, int tmp[])
29 {
30     long long ret = 0;
31     if(first < last)
32     {
33         int mid = (first + last) / 2;
34         ret += merge_sort(arr, first, mid, tmp);
35         ret += merge_sort(arr, mid+1, last, tmp);
36         ret += merge_arr(arr, first, mid, last, tmp);
37     }
38     return ret;
39 }
40 
41 int n, num[500010], tmp[500010];
42 int main()
43 {
44     while(scanf("%d", &n) != EOF && n)
45     {
46         for(int i = 0; i < n; i++)
47             scanf("%d", &num[i]);
48         printf("%I64d
", merge_sort(num, 0, n-1, tmp));
49     }
50     return 0;
51 }

View Code

二叉排序树版本：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 struct node
 5 {
 6     int data, cnt_right;
 7     struct node *left, *right;
 8 };
 9 
10 long long ans;
11 
12 void build(struct node *&p, int k)
13 {
14     if(p == NULL)
15     {
16         p = (struct node *)malloc(sizeof(struct node));
17         p->data = k;
18         p->cnt_right = 0;
19         p->left = p->right = NULL;
20     }
21     else if(p->data > k)
22     {
23         ans += p->cnt_right + 1;
24         build(p->left, k);
25     }
26     else
27     {
28         p->cnt_right++;
29         build(p->right, k);
30     }
31 }
32 
33 void del(struct node *p)
34 {
35     if(p == NULL)return;
36     del(p->left);
37     del(p->right);
38     free(p);
39 }
40 
41 int main()
42 {
43     int n, x;
44     while(scanf("%d", &n) != EOF && n)
45     {
46         ans = 0;
47         struct node *root = NULL;
48         while(n--)
49         {
50             scanf("%d", &x);
51             build(root, x);
52         }
53         del(root);
54         printf("%I64d
", ans);
55     }
56     return 0;
57 }

View Code