给你一个整数数组 nums，请你将该数组升序排列。
示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]提示：
1 <= nums.length <= 5 * 104-5 * 104 <= nums[i] <= 5 * 104
递归版归并排序
其实我们之前就已经接触过归并排序了，就是很经典的分治思想，如下图所示：
它和快速排序的思想一样，都是基于分治思想的，但不同的是，快速排序是先对当前数组区间进行处理，然后再递归左右区间继续处理，所以快速排序相当于是一个前序遍历。
而归并排序则是先递归左右区间进行处理，等左右区间都处理完之后才返回给当前数组区间进行合并处理，所以归并排序相当于是后序遍历！
并且归并排序是一种二分的思路，不是去找随机位置作为基准值，方便处理！
class Solution {
public:
void merge_sort(vector<int>& nums, int left, int right, vector<int>& tmp)
{
// 递归终止条件
if(left >= right)
return;
// 先进行分治，递归到左右区间去处理，这里采用二分法
int mid = (left + right) >> 1;
merge_sort(nums, left, mid, tmp);
merge_sort(nums, mid + 1, right, tmp);
// 合并两个有序数组到tmp中
int i = left; // 用来标记tmp的下标
int cur1 = left, cur2 = mid + 1; // 分别指向两个有序数组的起始位置
while(cur1 <= mid && cur2 <= right)
{
if(nums[cur1] <= nums[cur2])
tmp[i++] = nums[cur1++];
else
tmp[i++] = nums[cur2++];
}
while(cur1 <= mid)
tmp[i++] = nums[cur1++];
while(cur2 <= right)
tmp[i++] = nums[cur2++];
// 将tmp中元素写回nums中
while(left <= right)
{
nums[left] = tmp[left];
left++;
}
}
vector<int> sortArray(vector<int>& nums) {
vector<int> tmp(nums.size()); // 开辟一个辅助数组
merge_sort(nums, 0, nums.size() - 1, tmp);
return nums;
}
};非递归版归并排序
思路：与递归不同的是，迭代是不需要分解的，只需要控制好每次归并的区间，让它们从一一归并、二二归并、四四归并……即可，直到最后归并成一个完整的数组。
注意要点：归并时候可能存在的三种情况：（1、2点可合成为一点处理）
- 最后一个小组归并时，第一个小区间不够
gap个，那么就不需要归并。 - 最后一个小组归并时，第二个小区间不存在， 那么就不需要归并。
- 最后一个小组归并时，第二个小区间存在，第二个区间不够
gap个，那么只需要归并到第二个小区间的末尾即可。
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
// 开辟一个辅助数组
int n = nums.size();
vector<int> tmp(n);
int gap = 1;
while(gap < n)
{
for(int i = 0; i < n; i += gap*2)
{
// 先用变量定义出两个区间的边界
int left1 = i, right1 = i + gap - 1;
int left2 = i + gap, right2 = i + 2*gap - 1;
// 归并最后一小组时，如果不存在第二个小区间，则无需归并
if(left2 >= n)
break;
// 归并最后一小组时，如果第二个小区间不够gap个，则要调整一个边界
if(right2 >= n)
right2 = n - 1;
// 进行合并处理
merge(nums, left1, right1, left2, right2, tmp);
}
// 别忘了让gap翻倍
gap *= 2;
}
return nums;
}
// 合并有序数组函数
void merge(vector<int>& nums, int left1, int right1, int left2, int right2, vector<int>& tmp)
{
int i = left1; // 用来标记tmp的下标
int j = left1; // 先记下left1的位置，因为后面要用到
while(left1 <= right1 && left2 <= right2)
{
if(nums[left1] <= nums[left2])
tmp[i++] = nums[left1++];
else
tmp[i++] = nums[left2++];
}
while(left1 <= right1)
tmp[i++] = nums[left1++];
while(left2 <= right2)
tmp[i++] = nums[left2++];
// 将tmp中元素写回nums中
while(j <= right2)
{
nums[j] = tmp[j];
j++;
}
}
};