912. 排序数组 - 力扣LeetCode912. 排序数组 - 给你一个整数数组 nums请你将该数组升序排列。你必须在 不使用任何内置函数 的情况下解决问题时间复杂度为 O(nlog(n))并且空间复杂度尽可能小。 示例 1输入nums [5,2,3,1]输出[1,2,3,5]解释数组排序后某些数字的位置没有改变例如2 和 3而其他数字的位置发生了改变例如1 和 5。示例 2输入nums [5,1,1,2,0,0]输出[0,0,1,1,2,5]解释请注意nums 的值不一定唯一。 提示 * 1 nums.length 5 * 104 * -5 * 104 nums[i] 5 * 104https://leetcode.cn/problems/sort-an-array/description/归并排序一、核心思想分治思想分把待排序数组不断对半拆分直到每个子序列只有1 个元素天然有序治归并将两个有序子数组合并成一个更大的有序数组递归重复最终合并得到完整有序数组。一句话总结先拆分分到最小单元再两两有序合并。[38,27,43,3,9,82,10] [38,27,43] [3,9,82,10] [38,27] [43] [3,9] [82,10] [38] [27] [3][9] [82][10][38][27] → [27,38] [27,38] [43] → [27,38,43] [3][9] → [3,9] [82][10] → [10,82] [3,9] [10,82] → [3,9,10,82] [27,38,43] [3,9,10,82] → [3,9,10,27,38,43,82]很像是二叉树的后序遍历而快排则是像二叉树的前序遍历题目描述题目要求给你一个整数数组nums请你将该数组升序排列。你必须在不使用任何内置排序函数的情况下解决问题时间复杂度要求 \(O(n\log n)\)空间复杂度尽可能小。关键合并两个有序数组合并逻辑是归并排序最重要的模块 输入两段有序区间[l, mid]、[mid1, r]开辟临时数组存放合并结果双指针分别指向两段有序区间起点比较两个指针指向元素把更小的值放入临时数组对应指针后移其中一段遍历完成后直接追加另一段剩余元素将临时有序数组覆盖回原数组对应区间。class Solution { public: vectorint temp; vectorint sortArray(vectorint nums) { int nnums.size(); temp.resize(n); mergesort(nums,0,n-1); return nums; } void mergesort(vectorint nums,int left,int right) { if(left right) return; int mid(leftright)/2; mergesort(nums,left,mid); mergesort(nums,mid1,right); int cur1left,cur2mid1,i0; while(cur1midcur2right) temp[i]nums[cur1]nums[cur2]?nums[cur1]:nums[cur2]; while(cur1mid) temp[i]nums[cur1]; while(cur2right) temp[i]nums[cur2]; for(int ileft;iright;i) { nums[i]temp[i-left]; } } };
