归并排序求逆序对和比较次数+Java代码实现

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    static int cnt = 0, n;
    static int []a, b;
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        n = cin.nextInt();
        a = new int[n];
        b = new int[n];
        for(int i = 0; i < n; i++){
            a[i] = cin.nextInt();
        }
        merge(0, n-1);
        for (int i = 0; i < n; i++){
            if (i != 0)
                System.out.print(" ");
            System.out.print(a[i]);
        }
        System.out.println();
        System.out.println(cnt);
    }
    static void merge(int left, int right){
        if(right - left < 1){
            return;
        }
        int mid = (left + right) >> 1;
        merge( left, mid);
        merge(mid + 1, right);
        int p = left, q = mid+1, pos = left;
        while(p <= mid || q <= right){
            cnt++;//统计比较的次数
            if( q > right || (p <= mid && a[p] <= a[q])){
                b[pos++] = a[p++];
            }else{
                b[pos++] = a[q++];
//                cnt += mid -p +1;//统计逆序对的个数
            }
        }
        for(int i = left; i <= right; i++){
            a[i] = b[i];
        }

    }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
 

文章来源: blog.csdn.net，作者：爱玲姐姐，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/jal517486222/article/details/86495617