【C++算法】47.分治_归并_排序数组

题目链接：

912. 排序数组

题目描述：

解法

归并排序

快排有点像前序遍历，归并有点像后序遍历。

C++ 算法代码：

class Solution 
{
    vector<int> tmp; // 用于临时存储合并后的数组
    public:
    vector<int> sortArray(vector<int>& nums) 
    {
        tmp.resize(nums.size()); // 初始化临时数组的大小与 nums 相同
        mergeSort(nums, 0, nums.size() - 1); // 调用归并排序函数，从数组的起始位置到末尾位置
        return nums; // 返回排序后的数组
    }
    void mergeSort(vector<int>& nums, int left, int right)
    {
        if(left >= right) return; // 基本情况：如果左边界大于或等于右边界，说明当前区间只有一个元素或为空，无需排序
        // 1. 选择中间点划分区间
        int mid = (left + right) >> 1; // 这里两个加起来不会溢出，使用位运算 (left + right) >> 1 代替 (left + right) / 2 以提高效率
        // [left, mid] [mid + 1, right]为划分后的两个子区间
        // 2. 递归地对左右两个子区间进行排序
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        // 3. 合并两个有序的子数组
        // 初始化指针
        // cur1指向第一个子数组的当前元素
        // cur2指向第二个子数组的当前元素
        // i指向临时数组的当前位置
        int cur1 = left, cur2 = mid + 1, i = 0;
        // 当两个子数组都还有元素时，比较并复制较小的元素到临时数组
        while(cur1 <= mid && cur2 <= right)
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++]; // 如果第一个子数组的当前元素小于或等于第二个子数组的当前元素
        // 处理没有遍历完的数组
        while(cur1 <= mid) tmp[i++] = nums[cur1++]; // 处理第一个子数组中剩余的元素（如果有）
        while(cur2 <= right) tmp[i++] = nums[cur2++]; // 处理第二个子数组中剩余的元素（如果有）
        // 4. 将临时数组中的合并结果复制回原数组的对应位置
        for(int i = left; i <= right; i++)
            nums[i] = tmp[i - left];
        //tmp[i - left] 是因为 tmp 是从索引 0 开始存储合并后的结果，而 nums 的索引是从 left 开始。
        //因此，tmp 的第 0 个元素对应 nums 的第 left 个元素，tmp 的第 1 个元素对应 nums 的第 left + 1 个元素，依此类推
    }
};