手写归并
基础的手写归并排序模板 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include <bits/stdc++.h> using namespace std; using i64 = long long; void merge_range(i64 *arr, int left, int mid, int right) { int i = left, j = mid + 1, k = left; vector<i64> tmp(right + 1, 0); while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { tmp[k++] = arr[i++]; } else { tmp[k++] = arr[j++]; } } while (i <= mid) tmp[k++] = arr[i++]; while (j <= right) tmp[k++] = arr[j++]; // 回写到原数组 for (int p = left; p <= right; ++p) { arr[p] = tmp[p]; } } void merge_sort(i64 *arr, int left, int right) { if (left >= right) return; int mid = left + (right - left) / 2; merge_sort(arr, left, mid); merge_sort(arr, mid + 1, right); merge_range(arr, left, mid, right); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<i64> a(n + 1); for (int i = 1; i <= n; ++i) { cin >> a[i]; } merge_sort(a.data(), 1, n); for (int i = 1; i <= n; ++i) { cout << a[i] << " \n"[i == n]; } return 0; } 逆序对的个数 ...