最小相邻交换排序次数——逆序对计数及其C++实现

这个问题描述的场景非常经典——**通过相邻交换完成排序**。你提到的“桥旋转180度”其实等价于**交换相邻两个元素**。而交换相邻元素完成排序的最小次数，正好是**逆序对的数量**。 --- ## 🧠 核心思路 - 每次旋转只能将**相邻两节车厢**交换位置。 - 排序的目标是将车厢按编号从小到大排列。 - 最少旋转次数 = **当前序列中的逆序对总数**。 **逆序对定义**：对于数组 `a`，如果 `i < j` 且 `a[i] > a[j]`，则 `(i, j)` 为一个逆序对。 > 为什么？因为每次交换相邻元素，恰好能消除一个逆序对，且无法一次消除多个。因此最少次数 = 逆序对总数。 --- ## 💻 C++ 解法（暴力 O(n²)） 由于 n 最大为 99，O(n²) 完全足够。 ```cpp #include <iostream> using namespace std; int main() { int n; cin >> n; int a[100]; for (int i = 0; i < n; i++) { cin >> a[i]; } int count = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (a[i] > a[j]) { count++; } } } cout << count << endl; return 0; } ``` --- ## ⚙️ 进阶解法（归并排序 O(n log n)） 如果 n 很大（比如 > 10⁵），需要用归并排序求逆序对，但本题 n 很小，暴力即可。这里附带给出归并排序法，供参考： ```cpp #include <iostream> using namespace std; long long mergeCount(int a[], int temp[], int left, int mid, int right) { int i = left, j = mid + 1, k = left; long long count = 0; while (i <= mid && j <= right) { if (a[i] <= a[j]) { temp[k++] = a[i++]; } else { temp[k++] = a[j++]; count += (mid - i + 1); // 左半剩余元素均大于当前右元素 } } while (i <= mid) temp[k++] = a[i++]; while (j <= right) temp[k++] = a[j++]; for (int p = left; p <= right; p++) a[p] = temp[p]; return count; } long long mergeSortCount(int a[], int temp[], int left, int right) { if (left >= right) return 0; int mid = (left + right) / 2; long long count = mergeSortCount(a, temp, left, mid) + mergeSortCount(a, temp, mid + 1, right) + mergeCount(a, temp, left, mid, right); return count; } int main() { int n; cin >> n; int a[100], temp[100]; for (int i = 0; i < n; i++) cin >> a[i]; cout << mergeSortCount(a, temp, 0, n - 1) << endl; return 0; } ``` --- ## 📌 样例验证 输入： ``` 4 4 3 2 1 ``` 逆序对数量： - (4,3), (4,2), (4,1) - (3,2), (3,1) - (2,1) 共 6 个，输出 `6` ✅ --- ## 💡 开发建议 - **数据规模小**时优先暴力，代码清晰易维护。 - **逆序对思想**广泛应用于排序、稳定性分析等问题，建议熟练掌握。 - 若需要多次处理不同序列，可考虑预处理或使用树状数组优化。 - 注意输入输出格式，避免多余空格或换行影响评测。 --- ######[AI写代码神器 | 918点数解答 | 2026-08-28 19:18:24]