计算逆序对数

数学术语

逆序对，数学术语，设 A 为一个有 n 个数字的有序集 (n>1)，其中所有数字各不相同。
如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则 <A[i], A[j]> 这个有序对称为 A 的一个逆序对，也称作逆序数。

c++ 版

实现原理：归并排序

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int n;
int q[N], tmp[N];

LL merge_sort(int q[], int l, int r)
{
    if (l >= r) return 0;
    int mid = l + r >> 1;
    LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
    {
        if (q[i] <= q[j]) tmp[k ++] = q[i ++];
        else
        {
            tmp[k ++] = q[j ++];
            res += mid - i + 1;    // 如果左区间的数大于有区间的一个数 那么左区间的这个数和它之后的数都大于右区间的这个数
                                   // 都可以组成 对
        }
    }
    while (i <= mid) tmp[k ++] = q[i ++];
    while (j <= r) tmp[k ++] = q[j ++];
    for (i = l, j = 0; i <= r; ++i, ++j) q[i] = tmp[j];
    return res;
}
int main()
{
    cout << "输入数字的个数：";
    cin >> n;
    cout << "输入数字：";
    for (int i = 0; i < n; ++i) scanf ("%d", &q[i]);

    cout << merge_sort(q, 0, n - 1) << endl;
    return 0;
}

JAVA版

import java.util.Scanner;

public class Main {
	public static final int N = 100010; // 这里不能写 1e5 + 10 这个是语法错误 // 这里相当于 c++的 const int N = 1e5 + 10;
	public static int [] temp = new int [N];   // 这里一定要记得前面加上 static 这里写static 的话那么上面那个也要写 或者全部方法 成员都不写
    public static void main(String[] args) {
        System.out.print("输入数字序列（例如123456）：");
        Scanner sc = new Scanner(System.in);
        String digit = sc.nextLine();
        int [] arr = new int [digit.length()];
        for (int i = 0; i < digit.length(); ++ i) {
        	arr[i] = (int)(digit.charAt(i) - '0');
        }
        System.out.println("逆序对数：" + merge_sort(arr, 0, digit.length() - 1));
    }   
    public static int merge_sort(int [] arr, int l, int r) {
    	if (l >= r) return 0;    	    	    	
    	int mid = l + r >> 1;
    	int res = merge_sort(arr, l, mid) + merge_sort(arr, mid + 1, r);
    	int i = l, j = mid + 1, k = 0;
    	while (i <= mid && j <= r) {
    		if (arr[i] <= arr[j]) {
    			temp[k ++] = arr[i ++];
    		} else {
    			res += mid - i + 1;
    			temp[k ++] = arr[j ++];
    		}    	
    	}
    	while(i <= mid) {
    		temp[k ++] = arr[i ++];
    	}
    	while (j <= r) {
    		temp[k ++] = arr[j ++];
    	}
    	for (i = l, k = 0; i <= r; i ++) {
    		arr[i] = temp[k ++];
    	}
    	return res;
    }
}

Python版

def merge_sort(nums):
    if (len(nums) <= 1):
        return 0
    mid = len(nums) // 2
    L = nums[:mid]
    R = nums[mid:]
    ans = merge_sort(L) + merge_sort(R)
    
    i = j = k = 0
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            nums[k] = L[i]
            i += 1
            k += 1
        else:
            nums[k] = R[j]
            j += 1
            k += 1
            ans += len(L) - i
    while i < len(L):
        nums[k] = L[i]
        i += 1
        k += 1
    while j < len(R):
        nums[k] = R[j]
        k += 1
        j += 1
    return ans

print("输入数字序列: ", end="")
nums = input()
nums = list(map(int, list(nums)))
print(merge_sort(nums))