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