912. 排序数组

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

输入：nums = [5,2,3,1] 输出：[1,2,3,5]

示例 2：

输入：nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5]

提示：

• 1 <= nums.length <= 5 * 10(4)

• -5 * 10(4) <= nums[i] <= 5 * 10(4)

递归函数，定义递归函数mergeSort将nums数组中[left,right]区间元素进行升序排序。

递归内部逻辑，将[left,mid][mid+1,right]两个区间分别进行排序，排序完的两个独立的升序的区间，利用双指针进行合并。

递归的出口是left>=right，表示区间已经没有元素或者只有一个元素的情况，此时不需要进行排序操作。

内部递归逻辑维护意义的代码，实际上是利用双指针将两个有序的区间[left,mid][mid+1,right]进行合并的过程。

双指针遍历两个部分，将小的尾插到tmp临时数组中，直到所有元素都存储在tmp数组中。

定义将升序区间[left,mid][mid+1,right]两个区间分割出两个待处理的区间，[left,cur1-1][cur1,mid][mid+1,cur2-1][cur2,right]。

定义end1=mid，end2=right，得到最终的区间划分，[left,cur1-1][cur1,end1][mid+1,cur2-1][cur2,end2]。

[left,cur1-1]和[mid+1,cur2-1]全都是已经处理完的区间，[cur1,end1]和[cur2,end2]是待处理的区间。

定义tmp数组，和index，[0,index-1][index,right-left]区间划分。

总区间长度是right-left+1,[0,index-1]表示处理完毕的区间，[index，right-left]表示待处理的区间。

while (cur1 <= end1 && cur2 <= end2) tmp[index++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];

不断地维护nums和tmp区间的定义。当有一个区间待处理区间没有元素时，循环退出。此时需要把另一个还没有处理完的区间剩余元素添加到tmp数组中。

while (cur1 <= end1) tmp[index++] = nums[cur1++]; while (cur2 <= end2) tmp[index++] = nums[cur2++];

维护区间定义。

for (int i = left; i <= right; i++) nums[i] = tmp[i - left];

最后将tmp临时数组，排好序的依次赋值给nums数组中，完成合并排序。

class Solution {
public:
    vector<int> tmp;
    vector<int> sortArray(vector<int>& nums) {
        tmp.resize(nums.size());
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }

    void mergeSort(vector<int>& nums, int left, int right) {
        // 定义mergeSort递归函数，将nums数组中[left,right]区间进行排序
        // 内部逻辑，将[left,mid][mid+1,right]左右区间分别进行排序，排序完的利用双指针合并排序
        // 因此递归出口是left>=right表示区间只有一个元素或者没有元素，不需要再排序
        if (left >= right)
            return;
        int mid = left + (right - left) / 2;

        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        int cur1 = left, end1 = mid;
        int cur2 = mid + 1, end2 = right;
        int index = 0;
        while (cur1 <= end1 && cur2 <= end2)
            tmp[index++] =
                nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];

        while (cur1 <= end1)
            tmp[index++] = nums[cur1++];
        while (cur2 <= end2)
            tmp[index++] = nums[cur2++];

        for (int i = left; i <= right; i++)
            nums[i] = tmp[i - left];
    }
};

vector<int> tmp; 声明了一个成员变量 tmp，它是一个整型向量，用于临时存储排序过程中的元素。

sortArray 函数

tmp.resize(nums.size()); 调整 tmp 的大小，使其与输入数组 nums 的大小相同，这是为了确保有足够的空间来存储排序过程中的数据。

mergeSort(nums, 0, nums.size() - 1); 调用 mergeSort 函数，对整个数组进行排序。这里传入 nums、起始索引 0 和结束索引 nums.size() - 1 作为参数。

return nums; 返回排序后的数组。

mergeSort 函数

void mergeSort(vector<int>& nums, int left, int right) { 定义了一个函数 mergeSort，它接收三个参数：一个整型向量的引用 nums 和两个整数 left、right，分别代表要排序的数组部分的起始和结束索引。这个函数用递归方式实现归并排序。

if (left >= right) 检查递归的基本情况，如果当前区间只有一个元素或无元素（即 left 大于等于 right），就不需要排序，直接返回。

int mid = left + (right - left) / 2; 计算中点 mid，这样可以把数组分成两部分。

mergeSort(nums, left, mid); 递归地对左半部分进行排序。

mergeSort(nums, mid + 1, right); 递归地对右半部分进行排序。

合并两个排序后的部分

首先，通过双指针方法遍历两个部分（左半部分由 cur1 和 end1 控制，右半部分由 cur2 和 end2 控制），比较指针所指的元素，将较小的元素移动到临时数组 tmp 中。

while 循环用来合并两个部分，直到一个部分的元素全部移动到 tmp。

当一部分的元素全部移动到tmp中，剩下一部分的元素全部加入tmp即可。

for 循环将临时数组 tmp 中已排序的元素复制回原数组 nums 的相应位置，完成合并操作。

递归函数的时间复杂度计算

具体到时间复杂度的计算，我们可以从分解、解决问题和合并三个步骤来进行分析。分解时间是指将一个待排序序列分解成两序列的时间，这个过程的时间复杂度是O(1)，因为它只需要进行一次比较就可以完成。解决问题的时间，即对这两个子序列进行排序的时间，根据归并排序的定义，这一步实际上是递归地对每个子序列进行归并排序，因此这部分的时间复杂度是T(n/2) + T(n/2)，其中n是原始数组的长度。合并时间是指将两个有序的子序列合并成一个有序序列的时间，这个操作的时间复杂度是O(n)。

将这三个步骤的时间复杂度相加，我们得到归并排序的总时间复杂度为O(1) + 2T(n/2) + O(n)。

O(1)忽略不计,得到T(n)=2*T(n/2)+O(n)。

f(n) 是关于 n 的一个函数，Θ(n(d))，d 代表复杂度的阶数。根据 a, b, d 不同的取值，我们可以借助 Master Theorem 来求得不同情况下的复杂度：

空间复杂度

归并排序的空间复杂度主要由临时数组 tmp 和递归调用栈所使用的空间组成：

临时数组 tmp： 在整个排序过程中，需要一个大小与原数组 nums 相同的临时数组，所以临时数组的空间复杂度是 O(N)。

递归调用栈： 归并排序是通过递归实现的，最大的递归深度与数组二分的次数相同，即 O(log N)。

因此，归并排序的总空间复杂度是 O(N + log N)。由于在分析空间复杂度时常常忽略低阶项和常数项，可以简化为 O(N)。

LCR 170. 交易逆序对的总数

在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。

示例 1:

输入：record = [9, 7, 5, 4, 6] 输出：8 解释：交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。

限制：

0 <= record.length <= 50000

定义递归函数mergeSort，计算nums数组[left,right]区间中的逆序对，并且将区间[left,right]进行升序排序。

内部逻辑，计算[left,mid][mid+1,right]区间中的逆序对，并且将其升序排序，接着计算左右逆序对个数。

递归出口，left>=right，表示只有一个元素或者没有元素时，此时无逆序对。

内部代码实现合并排序以及左右逆序对的计算。

合并升序排序的逻辑，定义nums数组中[left,mid][mid+1,right]两段升序区间，割裂出两段未处理的区间。

得到[left,cur1-1][cur1,mid][mid+1,cur2-1][cur2,right]。

定义end1==mid，end2=right。

得到[left,cur1-1][cur1,end1][mid-1,cur2-1][cur2,end2]。

[left,cur1-1]和[mid+1,cur2-1]区间是已经处理完毕的区间。

定义tmp数组，[0,index-1][index,right-left]

[0,index-1]是处理完毕的区间，[index,right-left]是待处理区间。

依次将小值加入到tmp数组中。

内部代码计算左右逆序对。固定左边一个元素，然后计算右边比这个元素小的有多少个。或者固定右边一个元素，然后计算左边比这个元素大的有多少个。简单来说就是找到所有的左右二元组。

由于两部分都是有序的区间，所以在找二元组的时候可以进行优化。

为了将排序和计算合并在一起，我们先编写排序的代码，然后将计算左右逆序对的时候选取合适的方式进行编写。

class Solution {
public:
    vector<int> tmp;
    int reversePairs(vector<int>& nums) {
        tmp.resize(nums.size());
        return mergeSort(nums, 0, nums.size() - 1);
    }

    int mergeSort(vector<int>& nums, int left, int right) {
        // 定义mergeSort递归函数，返回nums数组中[left,right]的逆序对数,计算完逆序对后排序
        // 递归出口，left>=right，只有一个元素或者无元素，无逆序对
        // 内部逻辑，[left,mid][mid+1,right]区间的逆序对+左右逆序对
        if (left >= right)
            return 0;
        int ret = 0;
        int mid = left + (right - left) / 2;

        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);

        int cur1 = left, end1 = mid;
        int cur2 = mid + 1, end2 = right;
        int index = 0;
        while (cur1 <= end1 && cur2 <= end2) {
            if (nums[cur1] <= nums[cur2]) {
                tmp[index++] = nums[cur1++];
            } else {
                ret += end1 - cur1 + 1;
                tmp[index++] = nums[cur2++];
            }
        }

        while (cur1 <= end1)
            tmp[index++] = nums[cur1++];
        while (cur2 <= end2)
            tmp[index++] = nums[cur2++];

        for (int i = left; i <= right; i++)
            nums[i] = tmp[i - left];

        return ret;
    }
};

vector<int> tmp; 声明一个整型向量 tmp 用于归并过程中临时存储元素。

reversePairs 函数

tmp.resize(nums.size()); 调整 tmp 的大小使其与 nums 相同，为归并排序过程准备空间。

return mergeSort(nums, 0, nums.size() - 1); 调用 mergeSort 函数并返回其结果。这个函数会对 nums 进行排序，并计算逆序对数量。

mergeSort 函数

int mergeSort(vector<int>& nums, int left, int right) { 定义 mergeSort 函数，该函数通过递归将数组分成更小的部分，然后合并这些部分的同时计算逆序对数量。

if (left >= right) return 0; 递归的基准情况，当区间只包含一个元素或为空时，逆序对数量为0。

int ret = 0; 初始化逆序对数量为0。

int mid = left + (right - left) / 2; 计算中点，用于分割数组。

ret += mergeSort(nums, left, mid); 递归计算左半部分的逆序对数量，并累加到 ret。

ret += mergeSort(nums, mid + 1, right); 递归计算右半部分的逆序对数量，并累加到 ret。

合并过程中计算逆序对

在合并两个已排序部分的过程中，当从右侧部分取出元素比左侧部分的当前元素小，意味着左侧部分当前元素及其后所有元素都与该右侧元素构成逆序对（因为左侧部分已排序）。

if (nums[cur1] <= nums[cur2]) { 如果左侧元素小于等于右侧元素，将左侧元素复制到 tmp。

} else { 如果左侧元素大于右侧元素，计算逆序对数量（end1 - cur1 + 1），将右侧元素复制到 tmp。

while 循环分别处理剩余的左侧和右侧元素，将它们复制到 tmp 中。

更新原数组

for (int i = left; i <= right; i++) 循环将 tmp 中的元素复制回原数组 nums 的相应位置。

时间复杂度和空间复杂度与归并排序一致。

结尾

最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。

同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。

谢谢您的支持，期待与您在下一篇文章中再次相遇！