C++ 归并排序OJ

���录

1、912. 排序数组

2、LCR 170. 交易逆序对的总数

3、315. 计算右侧小于当前元素的个数

4、493. 翻转对

1、912. 排序数组

思路：本次使用归并排序 ，快速排序相当于二叉树的前序遍历，而归并排序相当于后序遍历。

• 归并排序是一种有效的排序算法，采用分治策略，将问题分解成一系列更小的问题，然后解决这些小问题，并将解决方案合并以产生原始问题的解决方案。下面是对这个过程的逐步解释。

• 归并排序的工作原理

  归并排序通过递归地将数组分成越来越小的部分，直到每个部分只有一个元素（自然是有序的），然后将这些有序的部分合并成较大的有序部分，直至整个数组排序完成。这个过程中，合并操作是通过比较来自两个不同部分的元素并选择较小的那个来实现的，这保证了合并后的数组也是有序的。

• 性能

  归并排序的时间复杂度为O(n log n)，其中n是数组的长度。这是因为每一层递归操作都需要遍历整个数组（O(n)），而递归树的深度为log n。归并排序需要额外的存储空间来存储临时数组，因此它的空间复杂度为O(n)。

  class Solution {public:    vector tmp;    vector sortArray(vector& nums) {        tmp.resize(nums.size());        mergeSort(nums, 0, nums.size() - 1);        return nums;    }    void mergeSort(vector& nums, int left, int right) {        if (left >= right)            return;        int mid = left + ((right - left) >> 1);        mergeSort(nums, left, mid);        mergeSort(nums, mid + 1, right);        int cur1 = left, cur2 = mid + 1, i = 0;        while (cur1