排序：归并排序和快速排序

力扣leetcode：912.排序数组，可以用来练习排序算法

题目：给你一个整数数组 nums，请你将该数组升序排列。

目录

归并排序

快速排序

---

归并和快排都运用了递归和分治的思想。归并：二叉树的后续遍历；快排：二叉树的前序遍历。

为什莫这么说呢？排序的核心代码框架：

归并排序
public void sort(int[] nums,int low,int high){
        if(low == high) return;
        int mid = low + (high - low)/2;
        //对左半数组排序，nums[low...mid]
        sort(nums,low,mid);
        //对右半边数组排序，nums[mid+1...high]
        sort(nums,mid+1,high);
        
        //二叉树遍历的后续位置，合并nums[low...mid]和nums[mid+1...high]
        merge(nums,low,mid,high);
}

先对左右数组进行排序，再合并。 

快速排序
public void sort(int[] nums,int low,int high){
        if(low >= high) return;
        //二叉树的前序位置，进行划分
        int p = partition(nums,low,high);

        //对划分的左半nums[low...p-1]进行排序
        sort(nums,low,p - 1);
        //对划分的右半nums[p+1...high]进行排序
        sort(nums,p + 1,high);
} 

 先构造分界点，然后去左右子树组构造分界点。

归并排序

过程：

• 先将要进行排序的数组分为两部分Left和Right
• 对Left部分排序
• 对Right部分排序
• 合并Left和Right两部分，合并成一个有序数组

代码：

class Solution {
    int[] temp; //归并排序的辅助数组
    public int[] sortArray(int[] nums) {
        //归并
        temp = new int[nums.length];
        sort(nums,0,nums.length-1);
        return nums;

    }

    public void sort(int[] nums,int low,int high){
        if(low == high) return;
        //有效防止溢出，其实和(low + high)/2等价
        int mid = low + (high - low)/2;
        //对左半数组排序
        sort(nums,low,mid);
        //对右半边数组排序
        sort(nums,mid+1,high);
        merge(nums,low,mid,high);
    }

    public void merge(int[] nums,int low,int mid,int high){
        //先将nums[low...high]的值存入辅助数组temp中
        for(int i = low;i <= high;i++){
            temp[i] = nums[i];
        }
        //双指针合并
        int i = low,j = mid + 1;
        for(int m = low; m <= high; m++){
            if(i == mid + 1) nums[m] = temp[j++];
            else if( j == high + 1) nums[m] = temp[i++];
            else if(temp[i] > temp[j]) nums[m] = temp[j++];
            else nums[m] = temp[i++]; 
        }
    }
}

快速排序

快速排序是先将一个元素排好序，再将剩下的元素排好序。核心函数是partition函数：

过程：

• 是在nums[low...high]中寻找一个分界点p
• 交换元素使得nums[low...p-1]的元素都小于等于nums[p]
• nums[p+1...high]的元素都大于nums[p]

partition其实就是把nums[p]这个元素排好序了

 代码：

class Solution {
    public int[] sortArray(int[] nums) {
       //快排
       sort(nums,0,nums.length - 1);
       return nums;
    }
    public void sort(int[] nums,int low,int high){
        if(low >= high) return;
        //对nums[low...high]进行划分
        //使得nums[low...p-1] <= nums[p] < nums[p+1...high]
        int p = partition(nums,low,high);
        sort(nums,low,p - 1);
        sort(nums,p + 1,high);
    } 

    public int partition(int[] nums,int low,int high){
        int pivot = nums[low];
        int i = low + 1,j = high;
        while(i <= j){ //不断交换，直到满足左边都小于，右边都大于
            while(i < high && nums[i] <= pivot) i++; //该while结束的时候num[i] > pivot
            while(j > low && nums[j] > pivot) j--; //该while结束的时候num[j] <= pivot 
            if(i >= j) break;
            swap(nums,i,j); //将这两交换
        }
        //将pivot放到合适的位置上，pivot左边的元素比它小，pivot右边的元素比它大
        swap(nums,low,j);
        return j;
    }
    public void swap(int[] nums,int a,int b){
        int temp = nums[b];
        nums[b] = nums[a];
        nums[a] = temp;
    }
}