关于leetcode:排序算法整理

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

  疾速排序

堆排序