/**
 * @author： wesen
 * @data：2021/5/19 上午1:44
 * @des:快排：:)
 * 思想：分治，分成两个数组，每个数组的左边比基数小，右边比基数大；
 **/

public class QS {
    //分——先从右往左比，直到遇到比基数小的数停下来，然后从右往左比，遇到比基数大的数字停下来，然后交换左右哨兵所在位置的数；
    //这里实现有几个注意的地方：需要记录三个值：左右哨兵（通过循环指示量来控制）；基数值；当基数选取左边值得时候，同时要先移动右哨兵，
    // 这样在循环结束时——左右哨兵相遇的时候
    //因为是右哨兵先停下来，所以该位置的值一定比基数小；同理，基数选取右边值得时候，要先移动左哨兵
    public static int partion(int[]a,int left,int right){
        int start=left;
        int temp=a[start];
        if(left>=right)return left;
        while(left<right){
            while (left<right&&temp<=a[right])--right;//非必要时使用左自增
            while (right>left&&temp>=a[left])++left;
            //交换
            if(left<right){
                int t=a[right];
                a[right]=a[left];
                a[left]=t;
            }
        }
        //当左右哨兵相遇时直接将哨兵位置所在的值与基数交换
        a[start]=a[left];
        a[left]=temp;
        return left;
        //滴滴答答——这个方法是快排的主要方法；实现比较灵活，需要考虑边界情况以及一些优化方式——比如数组反向有序的时候，
        // 会导致最差时间复杂度情况的出现，可以使用随机算法选取基准值
    }
    public static void quickSort(int []a,int left,int right){
        if(left>=right)return;//别忘了加递归边界
            int cur=partion(a,left,right);
            quickSort(a,left,cur-1);
            quickSort(a,cur+1,right);


    }
    public static void main(String []args){
        int[]nums={21,21};
        quickSort(nums,0,nums.length-1);
        for(int a:nums)System.out.println(a);
    }
}