逆序数对的统计
题目描述
运行代码
#include <iostream>
using namespace std;
#define LL long long
const int N = 1e5 + 5;
int a[N], tmp[N];
LL merge_sort(int q[], int l, int r)
{if (l >= r)return 0; int mid = l + r >> 1; LL res = merge_sort(q, l, mid) + merge_sort(q, 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{res += mid - i + 1;tmp[k ++ ] = q[j ++ ];}while (i <= mid)tmp[k ++ ] = q[i ++ ];while (j <= r)tmp[k ++ ] = q[j ++ ];for (i = l, j = 0; i <= r; i ++, j ++ )q[i] = tmp[j]; return res;
}
int main()
{int n;scanf("%d", &n);for (int i = 0; i < n; i ++ )
scanf("%d", &a[i]); cout << merge_sort(a, 0, n - 1) << endl; return 0;
}
代码思路
宏定义与常量
#define LL long long
:定义LL
为long long
类型的别名,用于存储较大的整数,例如逆序对的数量。const int N = 1e5 + 5;
:定义数组的最大容量,适用于最多100,005个元素的数组。
函数merge_sort
此函数递归地将数组分成更小的部分,然后合并这些部分,同时计算逆序对总数。
- 参数:
q[]
是要排序的数组,l
和r
分别是当前子数组的左右边界(索引)。 - 基础情况:当左边界大于等于右边界时(即子数组只有一个或没有元素),返回0,表示该子数组没有逆序对。
- 分解:计算中间索引
mid
,递归地对左右两部分[l, mid]
和[mid+1, r]
进行排序并计算逆序对,将结果累加到res
中。 - 合并:
- 初始化辅助数组
tmp
和三个指针k, i, j
。当i
未超过mid
且j
未超过r
时,比较q[i]
和q[j]
的大小:- 如果
q[i] <= q[j]
,说明当前元素不会形成新的逆序对,将q[i]
放入tmp
,并移动i
和k
。 - 否则,所有
q[i]
到q[mid]
之间的元素都比q[j]
大,因此增加了mid - i + 1
个逆序对,将q[j]
放入tmp
,移动j
和k
。
- 如果
- 分别处理剩余的元素,将它们依次放入
tmp
。将tmp
中的元素复制回原数组q
。
- 初始化辅助数组
- 返回值:最终返回整个数组排序过程中的逆序对总数
res
。 - 主函数
main
:读取数组长度n
。通过循环读取数组a
中的每个元素。调用merge_sort
函数,传入数组a
和其边界(0和n-1
),输出计算得到的逆序对总数。
改进思路
- 使用指针直接操作数组:在
mergeSortAndCount
函数中,直接使用指针i
,j
,k
而非索引,这在某些情况下可以略微提高访问效率。 - 保持数组作为参数:继续使用原生数组作为函数参数,保持与原始代码结构的一致性。
- 代码格式和可读性:调整代码格式,确保良好的可读性和一致性,比如增加必要的空格和换行。
- 去除不必要的类型别名:保留
int64_t
作为长整型的别名,因为它清晰地表达了数据类型的目的。
改进代码
#include <iostream>
using namespace std;
typedef long long int64_t;
// 使用指针代替数组索引来优化访问速度
int64_t mergeSortAndCount(int a[], int temp[], int left, int right) {if (left >= right) return 0; int mid = left + (right - left) / 2; // 递归排序并计数int64_t inv_count = mergeSortAndCount(a, temp, left, mid);inv_count += mergeSortAndCount(a, temp, mid + 1, right); // 合并阶段计算逆序对int i = left, j = mid + 1, k = left;while (i <= mid && j <= right) {if (a[i] <= a[j]) {temp[k++] = a[i++];} else {inv_count += mid - i + 1;temp[k++] = a[j++];}} // 复制剩余元素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 inv_count;
}
int main() {const int N = 1e5 + 10;int a[N], temp[N];int n;scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", &a[i]); int64_t inv_count = mergeSortAndCount(a, temp, 0, n - 1);cout << inv_count << endl; return 0;
}
其他方法(使用向量) AI生成
#include <iostream>
#include <vector>using namespace std;
using int64_t = long long;// 合并排序并计数逆序对
int64_t mergeSortAndCount(vector<int>& array, vector<int>& temp, int left, int right) {if (left >= right) return 0;int mid = left + (right - left) / 2;// 递归排序左右两边,并计算逆序对int64_t inv_count = mergeSortAndCount(array, temp, left, mid);inv_count += mergeSortAndCount(array, temp, mid + 1, right);// 合并阶段计算逆序对int i = left, j = mid + 1, k = 0;while (i <= mid && j <= right) {if (array[i] <= array[j]) {temp[k++] = array[i++];} else {inv_count += mid - i + 1; // 计算逆序对temp[k++] = array[j++];}}// 处理剩余元素while (i <= mid) temp[k++] = array[i++];while (j <= right) temp[k++] = array[j++];// 将排序结果复制回原数组copy(temp.begin(), temp.begin() + k, array.begin() + left);return inv_count;
}int main() {int n;cin >> n;vector<int> a(n);for (int& elem : a) cin >> elem;vector<int> temp(n); // 临时数组用于合并cout << mergeSortAndCount(a, temp, 0, n - 1) << endl;return 0;
}
- 添加函数注释:解释每个函数的作用,特别是
merge_sort
中的逻辑。 - 使用更明确的变量名:如将
q[]
改为array[]
,使代码意图更清晰。 - 去除全局变量:尽量减少全局变量的使用,改用函数参数传递。
- 优化类型别名的可读性:将
LL
改为更明确的别名,如typedef long long int64_t;
- 使用C++风格的输入输出:完全替换
scanf
和printf
为cin
和cout
。
归并、插入和冒泡排序比较
归并排序:
- 优点:时间复杂度在平均和最坏情况下都为 ,性能比较稳定,适合大规模数据排序。
- 缺点:需要额外的空间用于合并。
插入排序:
- 优点:对于接近有序的数据表现非常好,在小规模数据或部分有序数据上效率可能较高,代码简单。
- 缺点:最坏情况时间复杂度为 。
冒泡排序:
- 优点:实现简单。
- 缺点:时间复杂度较差,也是 。
一般来说,在数据规模较大且对性能要求较高时,归并排序通常表现更好。但如果数据规模较小或者数据有一定的特殊性(如接近有序),插入排序可能更合适。而冒泡排序相对来说在大多数情况下效率较低,较少被优先选用。
使用归并排序解决逆序数对统计问题思路:
在归并排序的合并过程中,当我们比较左右两部分元素时,左边部分一个较大元素如果出现在右边部分较小元素之前,那么就构成一个逆序数对。
当左边当前元素大于右边当前元素时,由于左右两边都是已排序的,那么左边该元素之后的所有元素与右边当前元素都构成逆序数对,数量为左边当前未处理元素的数量。我们可以在合并的同时统计这样的逆序数对数量。通过递归地执行归并排序,不断在合并过程中累加逆序数对的数量,最终就能得到总的逆序数对数量。
例如,假设有数组 [3, 1, 4, 2]
,在第一次合并 [3]
和 [1]
时,因为 3 大于 1,此时就找到一个逆序数对,然后继续递归合并其他部分并统计。