分治算法归并排序

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
比如一个元素个数为4的数列，其元素为2，4，3，1，则(2,1)，(4,3)，(4,1)，(3,1)是逆序，逆序数是4
现在求给定数列的逆序数
输入描述:
第一行为N，表示数列的元素个数(N<=1000)
第二行为N个用空格隔开的整数,其值在int范围内
输出描述:
输出占一行，为逆序数的个数
示例1
输入
复制
4
2 4 3 1
输出
复制
4
备注:
2020暑期集训选拔
以下是使用归并排序来计算逆序数的 C++ 代码：
cpp
#include
using namespace std;

// 合并两个已排序的子数组，并计算逆序数
long long merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    long long inv_count = 0;
    int i = 0, j = 0, k = l;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
            // 当 R[j] 小于 L[i] 时，说明 L[i] 到 L[n1 - 1] 都大于 R[j]，产生逆序数
            inv_count += n1 - i;
        }
    }

    while (i < n1)
        arr[k++] = L[i++];
    while (j < n2)
        arr[k++] = R[j++];

    return inv_count;
}

// 归并排序主函数，同时计算逆序数
long long mergeSort(int arr[], int l, int r) {
    long long inv_count = 0;
    if (l < r) {
        int m = l + (r - l) / 2;

        inv_count += mergeSort(arr, l, m);
        inv_count += mergeSort(arr, m + 1, r);

        inv_count += merge(arr, l, m, r);
    }
    return inv_count;
}

int main() {
    int n;
cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++)
cin >> arr[i];

    long long result = mergeSort(arr, 0, n - 1);

    cout << result << endl;

    return 0;
}
以下是对代码的解释：
归并排序与逆序数计算原理
归并排序是一种分治算法，它将数组分成两半，分别对两半进行排序，然后再将排序好的两半合并起来。在合并的过程中，可以计算逆序数。
当合并两个已排序的子数组 L 和 R 时，如果 R[j] 小于 L[i]，那么说明 L[i] 到 L[n1 - 1] 都大于 R[j]，此时会产生 n1 - i 个逆序数，将这些逆序数累加到 inv_count 中。
代码实现细节
merge 函数：
首先创建两个临时数组 L 和 R，分别存储左半部分和右半部分的元素。
然后通过三个循环，将原数组 arr 中的元素分别复制到 L 和 R 中，并进行合并操作。在合并过程中，按照上述原理计算逆序数。
mergeSort 函数：
这是归并排序的主函数，如果 l 小于 r，说明数组还可以继续分割。先计算中间索引 m，然后递归地对左半部分和右半部分调用 mergeSort 函数，并将返回的逆序数累加到 inv_count 中。最后调用 merge 函数进行合并，并将合并过程中产生的逆序数也累加到 inv_count 中。
main 函数：
首先读取输入的数组长度 n 和数组元素，然后调用 mergeSort 函数计算逆序数，并输出结果。

分治算法 归并排序

全站热榜

分治算法归并排序