使用归并排序思想计算序列逆序对的C++实现

### 🍎 思路分析 本题要求使用归并排序的思想来计算给定序列中逆序对的数目。归并排序是一种分治算法，其基本思想是将一个数组分成两个子数组，分别对这两个子数组进行排序，然后将排好序的子数组合并成一个有序的数组。在合并的过程中，我们可以统计逆序对的数量。 ### 🔧 代码实现 ```cpp #include <iostream> #include <vector> using namespace std; // 合并两个有序数组并统计逆序对 long long merge(vector<int>& arr, int left, int mid, int right) { vector<int> temp(right - left + 1); int i = left; // 左子数组的起始位置 int j = mid + 1; // 右子数组的起始位置 int k = 0; // 临时数组的起始位置 long long inv_count = 0; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { // 当 arr[i] > arr[j] 时，说明 arr[i...mid] 都与 arr[j] 构成逆序对 temp[k++] = arr[j++]; inv_count += (mid - i + 1); } } // 将左子数组剩余元素复制到临时数组 while (i <= mid) { temp[k++] = arr[i++]; } // 将右子数组剩余元素复制到临时数组 while (j <= right) { temp[k++] = arr[j++]; } // 将临时数组复制回原数组 for (i = left, k = 0; i <= right; i++, k++) { arr[i] = temp[k]; } return inv_count; } // 归并排序并统计逆序对 long long mergeSort(vector<int>& arr, int left, int right) { long long inv_count = 0; if (left < right) { int mid = left + (right - left) / 2; // 递归地对左子数组进行排序并统计逆序对 inv_count += mergeSort(arr, left, mid); // 递归地对右子数组进行排序并统计逆序对 inv_count += mergeSort(arr, mid + 1, right); // 合并两个有序子数组并统计逆序对 inv_count += merge(arr, left, mid, right); } return inv_count; } // 主函数 int main() { int n; cin >> n; vector<int> arr(n); for (int i = 0; i < n; i++) { cin >> arr[i]; } long long inv_count = mergeSort(arr, 0, n - 1); cout << inv_count << endl; return 0; } ``` ### 📝 代码解释 1. **`merge` 函数**：该函数用于合并两个有序的子数组，并统计逆序对的数量。当 `arr[i] > arr[j]` 时，说明 `arr[i...mid]` 都与 `arr[j]` 构成逆序对，因此逆序对的数量增加 `mid - i + 1`。 2. **`mergeSort` 函数**：该函数使用递归的方式对数组进行归并排序，并统计逆序对的数量。首先递归地对左子数组和右子数组进行排序，然后调用 `merge` 函数合并两个有序子数组。 3. **`main` 函数**：读取输入的数组，调用 `mergeSort` 函数统计逆序对的数量，并输出结果。 ### ⚙️ 复杂度分析 - **时间复杂度**：$O(n log n)$，其中 $n$ 是数组的长度。归并排序的时间复杂度为 $O(n log n)$。 - **空间复杂度**：$O(n)$，主要用于临时数组。 ### 💡 开发建议 - **代码复用**：可以将归并排序和统计逆序对的代码封装成一个独立的函数，方便在其他地方复用。 - **边界检查**：在读取输入时，需要确保输入的合法性，例如 `n` 的范围是否符合要求。 - **错误处理**：可以添加一些错误处理代码，例如当输入的整数超出范围时，输出错误信息。 ######[AI写代码神器 | 1060点数解答 | 2026-04-06 18:38:21]