计算逆序对数

冷不防 2024-03-31 13:11 52阅读 0赞

## 计算逆序对数 ##

### 数学术语 ###

逆序对，数学术语，设 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))