分治-归并-912.排序数组-力扣(LeetCode)

白天的黑夜

发布于 2025-10-22 17:16:06

10000

代码可运行

文章被收录于专栏：leetcode题目解析和知识分享leetcode题目解析和知识分享

运行总次数：0

代码可运行

一、题目解析

1、将数组排升序

2、在不使用任何内置函数的情况下解决问题

二、算法原理

分治-归并

合并两个有序数组

1、双指针遍历两个合并数组

2、将比较后的较小值放到新开数组中

3、防止有指针未遍历完，特殊处理

4、将nums中的元素还原

三、代码示例

 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)
    {
        //只有一个元素或者区间不存在直接返回
        if(left>=right) return;
        //1、选择中间点划分区间
        int mid = (left+right)>>1;
        //2、左右区间排序
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);
        //3、合并两个有序数组
        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];
    }