@[toc[

1.leetcode 912.排序数组

1.1 题目

题目链接

1.2 思路

上图 左侧是归并排序：类似二叉树后序遍历
右侧是快速排序：类似二叉树前序遍历

1.3 代码

class Solution {
public: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;int mid = (left + right) >> 1;// 分成两个数组 [left, mid] [mid + 1, right]// 排序数组mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);// 合并两个有序数组int i = 0, cur1 = left, cur2 = mid + 1;while(cur1 <= mid && cur2 <= right){tmp[i++] = nums[cur1] > nums[cur2] ? nums[cur2++] : nums[cur1++];}// 处理没有遍历完的数组while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];// 还原数组for(int i = left; i <= right; i++){nums[i] = tmp[i - left];}}};