归并排序——逆序数对的统计

逆序数对的统计

题目描述

运行代码

#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;
}

1. 添加函数注释：解释每个函数的作用，特别是merge_sort中的逻辑。
2. 使用更明确的变量名：如将q[]改为array[]，使代码意图更清晰。
3. 去除全局变量：尽量减少全局变量的使用，改用函数参数传递。
4. 优化类型别名的可读性：将LL改为更明确的别名，如typedef long long int64_t;
5. 使用C++风格的输入输出：完全替换scanf和printf为cin和cout。

归并、插入和冒泡排序比较

归并排序：

• 优点：时间复杂度在平均和最坏情况下都为 ，性能比较稳定，适合大规模数据排序。
• 缺点：需要额外的空间用于合并。

插入排序：

• 优点：对于接近有序的数据表现非常好，在小规模数据或部分有序数据上效率可能较高，代码简单。
• 缺点：最坏情况时间复杂度为 。

冒泡排序：

• 优点：实现简单。
• 缺点：时间复杂度较差，也是 。

一般来说，在数据规模较大且对性能要求较高时，归并排序通常表现更好。但如果数据规模较小或者数据有一定的特殊性（如接近有序），插入排序可能更合适。而冒泡排序相对来说在大多数情况下效率较低，较少被优先选用。

使用归并排序解决逆序数对统计问题思路：

在归并排序的合并过程中，当我们比较左右两部分元素时，左边部分一个较大元素如果出现在右边部分较小元素之前，那么就构成一个逆序数对。

当左边当前元素大于右边当前元素时，由于左右两边都是已排序的，那么左边该元素之后的所有元素与右边当前元素都构成逆序数对，数量为左边当前未处理元素的数量。我们可以在合并的同时统计这样的逆序数对数量。通过递归地执行归并排序，不断在合并过程中累加逆序数对的数量，最终就能得到总的逆序数对数量。

例如，假设有数组 [3, 1, 4, 2]，在第一次合并 [3] 和 [1] 时，因为 3 大于 1，此时就找到一个逆序数对，然后继续递归合并其他部分并统计。