快速排序

从数列中挑出一个元素，称为 "基准"（pivot）;
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

package com.example.leetcode.easy;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Arrays;

/**
 * 快速排序,分而治之
 * @author LiPeng01
 * @since 2021/3/1 4:10 下午
 */
public class Fast {
    public static void main(String[] args) {
        int[] num ={9,8,7,6,5,4,3,2,1};
        quick(num,0,num.length-1);
        Logger logger = LoggerFactory.getLogger(Merge.class);
        logger.info(Arrays.toString(num));
    }

    /**
     * 快排
     * @param nums
     * @param l
     * @param r
     */
    public static void quick(int[] nums,int l, int r){
        if(l < r) {
            //一轮快排将元素按照大小以基准i为为边界左右分开
            int mid = partition(nums,l,r);
            //对左边进行快排
            quick(nums,l,mid-1);
            //对右边进行快排
            quick(nums,mid+1,r);
        }
    }

    /**
     * 一轮排序,将比基准数大的放在基准数右边,小的放在左边
     * @param nums 数组
     * @param l 左边界
     * @param r 右边界
     * @return
     */
    public static int partition(int[] nums,int l,int r) {
        int i = l;
        int j = r;
        //将最左边的数字作为基准数(即把基准数从i坑中挖出)
        int pivot = nums[i];
        while(i < j) {
            //从右向左,直到比基准数小
            while(i < j && nums[j] >= pivot) {
                j--;
            }
            //如果比基准数小,则该数填入到i的坑中,此时j的位置空出一个坑来(实际值还在),j不变记录坑位
            if(i < j && nums[j] < pivot) {
                nums[i] = nums[j];
                i++;
            }
            //从左向右,直到比基准数大
            while (i<j && nums[i] <= pivot) {
                i++;
            }
            //如果比基准数大,则将该数填入到j的坑中,此时i的位置空出一个坑来(实际值还在),i不变记录坑位
            if(i< j && nums[i] > pivot) {
                nums[j] = nums[i];
                j--;
            }
        }
        //直至i,j相遇,此时比基准数大的放在基准数右边,小的放在左边
        //由于i或j停在此处一定是因为上一轮发生了填坑,即此处的已经被挖坑,所以将基准数填入即可
        nums[i] = pivot;

        return i;
    }
}