参考资料
水平有限，欢迎交流！
【如何优雅地排序——3分钟看懂【归并排序】的基本思想】
练习题
P1177 【模板】排序 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
LCR 170. 交易逆序对的总数 - 力扣（LeetCode）
关键步骤与应用
步骤
在归并过程中，主要包含两个关键步骤：
- 分割（Divide）：将数组递归地分成两个或多个子数组。
- 合并（Merge）：将两个或多个已排序的子数组合并成一个有序的大数组。
应用
可用于求逆序对的对数（力扣LCR 170）
归并排序
P1177 【模板】排序 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;public class Main {static int N;static int[] arr;static int[] tmp;//分割static void MergeSort(int[] a, int l, int r) {if (l >= r) {return;}int mid = (l + r) >> 1;MergeSort(a, l, mid);MergeSort(a, mid + 1, r);merge(a, l, mid, r);}//合并static void merge(int[] a, int l, int mid, int r) {int i = l, j = mid + 1, k = 0;// 合并两个已排序的子数组while (i <= mid && j <= r) {if (a[i] <= a[j]) {tmp[k++] = a[i++];} else {tmp[k++] = a[j++];}}// 处理剩余的元素while (i <= mid) {tmp[k++] = a[i++];}// 将临时数组中的元素复制回原数组for (int x = 0; x < k; x++) {a[l+x] = tmp[x];}}public static void main(String[] args) throws IOException {BufferedReader in = new BufferedReader(new InputStreamReader(System.in));BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));N = Integer.parseInt(in.readLine());arr = new int[N];tmp = new int[N];String[]line = in.readLine().split(" ");for (int i = 0; i < N; i++) {arr[i] = Integer.parseInt(line[i]);}MergeSort(arr, 0, N - 1);for (int i : arr) {out.write(i + " ");}out.flush();in.close();out.close();}
}
求逆序对对数（仅考虑思路，不考虑消耗）
LCR 170. 交易逆序对的总数 - 力扣（LeetCode）
class Solution {int []tmp;int mergeSort(int []nums,int l,int r){if(l>=r)return 0;int cnt = 0;int mid = l +r >>1;cnt+=mergeSort(nums, l, mid);cnt+=mergeSort(nums, mid+1, r);int i = l,j = mid +1 ,k = 0;while(i<=mid&&j<=r){if(nums[i]<=nums[j]){tmp[k++] = nums[i++];}else{cnt+=(mid-i+1);tmp[k++] = nums[j++];}}while(i<=mid){tmp[k++] = nums[i++];}for(int x = 0;x<k;x++){nums[x+l] = tmp[x];}return cnt;}public int reversePairs(int[] record) {tmp = new int[record.length];return mergeSort(record, 0, record.length-1);}
}
3193. 统计逆序对的数目 - 力扣（LeetCode）
下面为暴力写法，过一半左右
import java.util.ArrayList;
import java.util.List;class Solution {final int mod = 1000000007;List<List<Integer>> ans;int[] tmp;boolean[] vis;// 调整mergeSort方法以正确计算逆序对int mergeSortAndCount(List<Integer> cur, int l, int r) {if (l >= r) return 0;int mid = (l + r) >> 1;int count = 0;count += mergeSortAndCount(cur, l, mid);count += mergeSortAndCount(cur, mid + 1, r);count += mergeAndCount(cur, l, mid, r);return count;}int mergeAndCount(List<Integer> cur, int l, int mid, int r) {int i = l, j = mid + 1, k = 0;int count = 0;while (i <= mid && j <= r) {if (cur.get(i) <= cur.get(j)) {tmp[k++] = cur.get(i++);} else {tmp[k++] = cur.get(j++);count += (mid - i + 1); // 确定逆序对的个数}}while (i <= mid) {tmp[k++] = cur.get(i++);}for (i = 0; i < k; i++) {cur.set(l + i, tmp[i]);}return count;}void dfs(int[] nums, List<Integer> res, int[][] requirements) {int len = nums.length;if (res.size() == len) {// 判断所有的要求是否都满足boolean isValid = true;for (int[] req : requirements) {int end = req[0];int cnt = req[1];List<Integer> sublist = new ArrayList<>(res.subList(0, end + 1));tmp = new int[sublist.size()];int inversionCount = mergeSortAndCount(sublist, 0, end);if (inversionCount != cnt) {isValid = false;break;}}if (isValid) {ans.add(new ArrayList<>(res)); // 只有满足所有要求时才添加到结果集}return;}for (int i = 0; i < len; i++) {if (!vis[i]) {vis[i] = true;res.add(nums[i]);dfs(nums, res, requirements);res.remove(res.size() - 1);vis[i] = false;}}}public int numberOfPermutations(int n, int[][] requirements) {ans = new ArrayList<>();int[] nums = new int[n];for (int j = 0; j < n; j++) {nums[j] = j;}vis = new boolean[n];dfs(nums, new ArrayList<>(), requirements);return ans.size() % mod;}
}
