1.归并排序模板
// 归并排序模板 #include <iostream> using namespace std; const int N = 1e6 + 5; int n; int q[N], tmp[N]; void merge_sort(int q[], int l, int r) { if (l >= r) return; int mid = (l + r) / 2; merge_sort(q, l, mid); merge_sort(q, mid + 1, r); // 先递归 // 递归完，结果有两个有序数组，再归并 int k = 0, i = l, j = mid + 1; // k表示结果数组下标，i指向左半边起点，j指向右半边起点 while (i <= mid && j <= r) { if (q[i] < q[j]) tmp[k++] = q[i++]; else tmp[k++] = q[j++]; } while (i <= mid) tmp[k++] = q[i++]; // 左边还剩下 while (j <= r) tmp[k++] = q[j++]; // 右边还剩下 // tmp数组赋回q for (int a = l, b = 0; a <= r; a++, b++) // a指向q，b指向tmp q[a] = tmp[b]; } int main() { cin >> n; for (int i = 0; i < n; i++) { scanf("%d", &q[i]); } merge_sort(q, 0, n - 1); for (int i = 0; i < n; i++) { printf("%d ", q[i]); } return 0; }
2.求逆序对数量：
给定一个长度为 n的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i个和第 j个元素，如果满足 i<j且 a[i]>a[j]，则其为一个逆序对；否则不是。
#include <iostream> using namespace std; // 此题会爆int(因为降序数组的逆序对最大，为n(n-1)/2约等于5*10e9) // 所以用long long 来存 typedef long long ll; const int N = 1e5 + 5; int n; int q[N], tmp[N]; ll merge_sort(int l, int r) { // 返回区间l~r所有逆序对的数量 if (l >= r) return 0; int mid = (l + r) / 2; ll res = merge_sort(l, mid) + merge_sort(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; // 推导的公式 这里res+逆序对分布在左右两边的个数 } } // 收尾 谁剩下就全赋给tmp while (i <= mid) tmp[k++] = q[i++]; while (j <= r) tmp[k++] = q[j++]; // 物归原主 tmp赋回q中 for (int a = l, b = 0; a <= r; a++, b++) // a:q b:tmp { q[a] = tmp[b]; } return res; } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &q[i]); } ll num = merge_sort(0, n - 1); cout << num; return 0; }
