归并排序求逆序数

• 问题：求逆序数。
• 算法：归并排序。

归并排序是分治法(分而治之)的一种典型应用，应用递归的思想，自顶向下思考：先假定mergesort()可以将一个乱序的数组排好序，因此就可以开始"分"(将一个数组平均分成两部分），再"治"(分别对前后部  分调用mergesort()使它们有序)，最后再写一个合并子函数Combine()，它可以将两个有序的数组合并，Combine()实现起来比较容易．只需要管理两个指针，分别指向两个子数组的开头，开辟新内存保存中间结 果，遍历完两个数组就可以完成，时间是Θ(n).

假定n个元素的数组调用mergesort()需要时间T(n).因此，T(n)=2T(n/2)+Θ(n)．由主定理可知：T(n)=Θ(nlogn).归并排序算法的时间复杂度是Θ(nlogn)，空间复杂度是Θ(n).

代码如下：

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <algorithm>
 4 
 5 using namespace std;
 6 
 7 int arr[100];
 8 int temp[100];
 9 int number = 0;
10 //合并函数。
11 void Combine(int left,int middle,int right){
12     int i = left;
13     int j = middle+1;
14     int k = left;
15     while (i <= middle && j <= right){
16         if(arr[i] <= arr[j]){
17             temp[k++] = arr[i++];
18         }else{
19             number+=middle-i+1;//1.归并排序求逆序数核心，记录逆序数对数。
20             temp[k++] = arr[j++];
21         }
22     }
23     while(i <= middle){
24         temp[k++] = arr[i++];
25     }
26     while(j <= right){
27         temp[k++] = arr[j++];
28     }
29     for(int m=left; m<=right; m++){
30         arr[m] = temp[m];
31     }
32     return;
33 }
34 
35 void mergersort(int left,int right){
36     if(left < right){
37         int middle = left + (right-left)/2;
38         mergersort(left,middle);
39         mergersort(middle+1,right);
40         Combine(left,middle,right);
41     }
42     return;
43 } 
44 int main(){
45     int n;
46     while( scanf("%d",&n)!= EOF){
47     for(int i=0; i<n; i++){
48         scanf("%d",&arr[i]);
49     }
50     mergersort(0,n-1);
51     for(int j=0; j<n; j++){
52         printf("%d ",arr[j]); //排序后的数组。
53     }
54     
55     printf("\n");
56     printf("%d\n",number);    
57 }
58 }

当然求逆序数也可以暴力求解，直接双重循环，此时算法复杂度为O(n 2 )，废话不多说代码如下：

 1 # include <cstdio>
 2 # include <iostream>
 3 
 4 using namespace std;
 5 int number;
 6 int arr[100];
 7  int main (){
 8      int n;
 9      while( scanf("%d",&n) != EOF){
10           number=0; 
11          for(int k=0; k<n; k++){
12              scanf("%d",&arr[k]);
13          }
14         for(int i=0; i<n; i++)
15          for(int j=i; j<n; j++){
16              if(arr[i]>arr[j]){
17                  number++;//记录逆序数对数
18              }
19          }
20          printf("%d\n",number);
21         
22      }
23  }

显然暴力求解代码量少，但是归并排序的效率更高。