归并排序算法及其在算法中的应用

1 归并排序算法实现步骤

归并排序的实现可以分为以下几个步骤：

1.1 分解（Divide）：

将当前数组从中间分成两个子数组，递归地对这两个子数组继续进行分解，直到每个子数组只包含一个元素（此时子数组自然有序）。

1.2 解决（Conquer）：

递归地对分解得到的子数组进行排序。由于每个子数组最终会被分解到只包含一个元素，因此排序操作实际上是在合并过程中完成的。

1.3 合并（Merge）：

将两个已排序的子数组合并成一个有序数组。这是归并排序的核心操作，需要比较两个子数组的元素，按顺序放入新的数组中。

2 归并算法实现示意图

初始数组: [38, 27, 43, 3, 9, 82, 10]

分解阶段:
          [38, 27, 43, 3, 9, 82, 10]
                 /                \
        [38, 27, 43, 3]      [9, 82, 10]
          /        \           /      \
    [38, 27]    [43, 3]    [9, 82]   [10]
    /    \      /    \     /    \     |
  [38]  [27]  [43]  [3]  [9]   [82]  [10]

合并阶段:
  [38]  [27]  [43]  [3]  [9]   [82]  [10]
    \    /      \    /     \    /     |
    [27, 38]    [3, 43]    [9, 82]   [10]
       \          /          \        /
     [3, 27, 38, 43]      [9, 10, 82]
           \                  /
      [3, 9, 10, 27, 38, 43, 82]

3 归并排序算法实现

3.1 算法实现

#include <iostream>
#include <vector>
using namespace std;

// 合并两个已排序的子数组
void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;  // 左子数组的长度
    int n2 = right - mid;     // 右子数组的长度

    // 创建临时数组
    vector<int> L(n1), R(n2);

    // 复制数据到临时数组L[]和R[]
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // 归并临时数组到arr[left..right]
    int i = 0;    // 初始化左子数组的索引
    int j = 0;    // 初始化右子数组的索引
    int k = left; // 初始归并子数组的索引

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 复制L[]的剩余元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // 复制R[]的剩余元素
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// 归并排序主函数
void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        // 计算中间点
        int mid = left + (right - left) / 2;

        // 递归排序左右两部分
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // 合并已排序的两部分
        merge(arr, left, mid, right);
    }
}

// 打印数组元素
void printArray(const vector<int>& arr) {
    for (int num : arr)
        cout << num << " ";
    cout << endl;
}

int main() {
    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
    
    cout << "排序前的数组: ";
    printArray(arr);

    // 执行归并排序
    mergeSort(arr, 0, arr.size() - 1);

    cout << "排序后的数组: ";
    printArray(arr);

    return 0;
}

3.2 算法代码实现简单解释：

3.2.1 merge 函数：

将两个已排序的子数组合并为一个有序数组。

• 创建临时数组存储左右子数组
• 比较左右子数组元素，按顺序放入原数组
• 处理剩余元素

3.2.2 mergeSort 函数：

递归实现分治策略

• 分解：将数组从中间分成两部分
• 解决：递归排序左右两部分
• 合并：调用 merge 函数合并已排序的部分

3.2.3 main 函数：

演示归并排序的使用

• 初始化测试数组
• 调用排序函数
• 输出排序结果

4 数组中的逆序对

BM20 数组中的逆序对

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int mod = 1000000007;

    int mergeSort(vector<int> &nums, int left, int right) {
        if (left >= right) {
            return 0;
        }

        int mid = (left + right) / 2;
        int res = mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right);

        res %= mod;
        int n1 = mid - left + 1;
        int n2 = right - mid;

        vector<int> L(n1), R(n2);
        for (int i = 0; i < n1; i++) {
            L[i] = nums[left + i];
        }
        for (int i = 0; i < n2; i++) {
            R[i] = nums[mid + i + 1];
        }

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (i == mid + 1) {
                nums[k++] = R[j++];
            } else if (j == right + 1) {
                nums[k++] = L[i++];
            } else if (L[i] <= R[j]) {
                nums[k++] = L[i++];
            } else {
                nums[k++] = R[j++];
                res += mid - left - i + 1;
            }
        }

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

        return res % mod;
    }

    int InversePairs(vector<int>& nums) {
        int res = 0;
        int n = nums.size();

        res = mergeSort(nums, 0, n - 1);

        for (int i = 0; i < n; i++) {
            cout << nums[i];
        }
        return res;
    }
};