文章目录
- 题目链接：
- 题目描述：
- 解法
- C++ 算法代码：
题目链接：
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 个元素，依此类推}
};