目录
1.题目
2.思路
这个题可以作为练习手写各种排序的场景题。这里回顾一下归并排序。
归并排序——nlogn
思想——递归
每次都把这个数组分成两堆【0， mid】和 【mid + 1， end】，分别对两堆进行排序，然后再合并两个有序的数组，中间借助了一个temp[]数组。这里借助的是递归的思想，每次都把数组分成两堆。比如在排序前半部分的时候，也就是【0， mid】的时候，同样的也是把这个数组分成两堆，然后分别排序好之后，然后再合并。所以会不断地递归下去。直到不能分成两堆为止。
代码
- 归并排序主函数为public?void?mergeSort(int[]nums,?int?start,?int?end)
- 合并两个有序数组的函数：public?void?merge(int[]nums,?int?start,?int?mid,?int?end)
- 注意归并排序结束条件：if(start >= end) return ;
- 注意借助了一个暂时的数组存放合并好的数组temp[]
class Solution {
public int[] sortArray(int[] nums) {
int n = nums.length;
mergeSort(nums, 0, n - 1);
return nums;
}
// 归并排序
public void mergeSort(int[]nums, int start, int end){
if(start >= end) return;
int mid = start + (end - start) / 2;
mergeSort(nums, start, mid);
mergeSort(nums, mid + 1, end);
// 合并到一起
merge(nums, start, mid, end);
return ;
}
// 合并两个有序的数组到一起
public void merge(int[]nums, int start, int mid, int end){
int[]temp = new int[end - start + 1];
int i = start, j = mid + 1, k = 0;
while(i <= mid && j <= end){
if(nums[i] <= nums[j]){ //如果这里<= ,那么就是稳定的，如果是<,那么就是非稳定的
temp[k++] = nums[i++];
}
else{
temp[k++] = nums[j++];
}
}
// 跳出循环有两个可能
while(i <= mid){
temp[k++] = nums[i++];
}
while(j <= end){
temp[k++] = nums[j++];
}
// 更新nums
for(int l = start; l < start + temp.length; l++){
nums[l] = temp[l - start];
}
return ;
}
}时间复杂度——O（nlogn）
我们可以把时间分成两块乘积，一个是把一个数组分成两堆的时间。一个是合并两个有序数组的时间。分别来简单计算一下，首先是第一次会把数组分成两堆，下一次总共就会有4堆，一直往下，相当于是一颗满二叉树，这个满二叉树的深度为logn,也就是需要nlogn时间.
对于另外一块，合并两个有序数组的时间，因为会遍历这两个数组的元素各一次，所以是O（n）, 不管分成多少堆，每一次的合并数组的时间都是O（n）,因为数组总元素没有变化。
所以最终就是nlogn的时间复杂度。
空间复杂度——O（n）
因为借助了临时数组来保存结果。所以是O（n）
稳定性——稳定
稳定性：就是如果两个值相同，排序完后，这两个元素的相对位置没变化，那么就说明是稳定的。
这里归并的稳定性主要取决于合并两个有序数组的函数merge()的写法。
比如我这里写得是<=，那么就是稳定的。因为假如nums[i] == nums[j],那么我们是先把nums[i]放在temp数组的前面的，所以相对顺序并不会改变。所以是稳定的。
我们在讨论归并排序的时候，因为他可以是稳定的，所以这个方法一般被称为稳定的排序算法。
3.结果
