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，在这里就不多做介绍）。疾速排序