【算法】分治：归并之 912.排序数组（medium)

系列专栏

双指针

模拟算法

分治思想

目录

1、题目链接

2、题目介绍

3、解法

解决方案选择

解题步骤

4、代码

1、题目链接

912. 排序数组 - 力扣（LeetCode）

2、题目介绍

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

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

示例 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 * 104
• -5 * 104 <= nums[i] <= 5 * 104

3、解法

解决方案选择

为了满足时间复杂度的要求，我们选择使用归并排序（Merge Sort）算法。归并排序是一种分而治之的算法，它将数组分成两半，递归地对它们进行排序，然后将结果合并成一个有序数组。这个过程的时间复杂度为 O(nlog(n))，因为它将问题分解成更小的子问题，直到子问题的大小为1（即已经排序），然后将它们合并起来。

解题步骤

1. 定义辅助函数：
   • merge 函数：负责将两个已排序的子数组合并成一个有序数组。它使用了一个临时数组 tmp 来存储合并过程中的元素，以避免在原始数组上进行复杂的元素移动。
   • mergeSort 函数：递归地将数组分成更小的部分，直到每个部分只包含一个元素（自然是有序的），然后调用 merge 函数将它们合并成有序数组。
2. 归并排序过程：
   • 拆分：通过递归调用 mergeSort，将数组不断拆分成更小的部分，直到每个部分只包含一个元素。
   • 合并：在递归返回的过程中，使用 merge 函数将相邻的两个已排序的子数组合并成一个有序数组。
3. 空间复杂度：
   • 归并排序的空间复杂度主要由临时数组 tmp 决定，其大小为 nums.size()，因此空间复杂度为 O(n)。
4. 时间复杂度：
   • 归并排序的时间复杂度为 O(nlog(n))，这主要是由于每次递归调用都将问题规模减半，并且合并操作的时间复杂度为 O(n)。

4、代码

class Solution {
public:
    //归并排序
    //
    void merge(vector<int>& nums, vector<int>& tmp, int left, int mid, int right)
    {
        int lsort = left, rsort = mid + 1;//两个需要进行合并区域的第一个元素下标
        int cur = left;//遍历tmp数组的计数器

        while (lsort <= mid && rsort <= right)
        {
            if (nums[lsort] <= nums[rsort])
            {
                tmp[cur++] = nums[lsort++];
            }
            else {
                tmp[cur++] = nums[rsort++];
            }
        }

        //如果有剩余的数，没有参与比较，直接插入到tmp中
        while (lsort <= mid)
        {
            tmp[cur++] = nums[lsort++];
        }
        while (rsort <= right)
            tmp[cur++] = nums[rsort++];

        while (left <= right)
        {
            nums[left] = tmp[left];
            left++;
        }

    }
    //先拆分，再合并
    void mergeSort(vector<int>& nums, vector<int>& tmp, int left, int right)
    {
        if (left < right)
        {
            int mid = (right + left) / 2;
            mergeSort(nums, tmp, left, mid);
            mergeSort(nums, tmp, mid + 1, right);

            merge(nums, tmp, left, mid, right);
        }

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

💗感谢阅读！💗