leetcode912 排序数组
给你一个整数数组 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
归并排序（重点）
- 基本思路：借助额定空间，合并两个有序数组，失去更长的有序数组。例如：「力扣」第 88 题：合并两个有序数组。
- 算法思维：分而治之（分治思维）。「分而治之」思维的形象了解是「曹冲称象」、MapReduce，在肯定状况下能够并行化。
集体倡议：「归并排序」是了解「递归思维」的十分好的学习材料，大家能够通过了解：递归实现当前，合并两个有序数组的这一步骤，想分明程序的执行流程。即「递归函数执行实现当前，咱们还能够做点事件」。因而，「归并排序」我集体感觉十分重要，肯定要把握。
class Solution {
// 归并排序
public int[] sortArray(int[] nums) {return mergeSort(nums, 0, nums.length-1);
}
public int[] mergeSort(int[] nums, int left, int right){
// 递归退出条件
// 如果左指针大于右指针，就退出循环
// 通过左右拆分，数组元素造成单个元素的树
if(left >=right){return nums;}
// 数组中的中位数
int mid = (right+left)/2;
// 数组左拆分
mergeSort(nums, left, mid);
// 数组右拆分
mergeSort(nums, mid+1, right);
// 数组合并，将单个元素进行合并
return merge(nums, left, mid, right);
}
public int[] merge(int[] nums, int left, int mid, int right){
// 定义一个长期数组，存储排序好的元素
int[] temp = new int[right-left+1];
// 左排序的元素数组的左指针
int i = left;
// 右排序的元素数组的左指针
int j = mid+1;
// 定义一个指向长期数组的左指针
int t = 0;
// 循环判断条件
// 左数组到 mid，右数组到 right
// 左右数组都有元素的时候，进行比拟
while(i<=mid&&j<=right){
// 取左右数组中较小的元素，填入长期数组中
// 并将较小元素所在数组的左指针和长期数组的左指针都一起右移
if(nums[i]<=nums[j]){temp[t++] = nums[i++];
}else{temp[t++] = nums[j++];
}
}
// 当左右数组其中一个数组没有元素的时候
// 如果左数组中还有残余元素，就将残余元素全副退出到长期数组中
while(i<=mid){temp[t++]=nums[i++];
}
// 如果有数组中还有元素，就将残余元素全副退出到长期数组中
while(j<=right){temp[t++] = nums[j++];
}
// 将长期数组的元素复制到原数组中去
for(int k = 0; k<temp.length;k++){
// 特地留神这便 nums 数组起始地位要从 k+left 开始
// 起因在加右数组的时候，起始地位要加 left
// 这里不了解，间接把它记住。nums[left+k]=temp[k];
}
// 返回原数组
return nums;
}
}- 优化 1：在「小区间」里转向应用「插入排序」，Java 源码外面也有相似这种操作，「小区间」的长度是个超参数，须要测试决定，我这里参考了 JDK 源码；
- 优化 2：在「两个数组」自身就是有序的状况下，无需合并；
-
优化 3：全程应用一份长期数组进行「合并两个有序数组」的操作，防止创立长期数组和销毁的耗费，防止计算下标偏移量。
留神：实现归并排序的时候，要特地留神，不要把这个算法实现成非稳固排序，区别就在 <= 和 <，已在代码中注明。
「归并排序」比「疾速排序」好的一点是，它借助了额定空间，能够实现「稳固排序」，Java 里对于「对象数组」的排序工作，就是应用归并排序（的升级版 TimSort，在这里就不多做介绍）。疾速排序