package test.fastsort;

public class FastSort {

    public static void main(String[] args) {
        int[] test = {8, 3, 6, 1, 9, 10, 3, 4, 5, 2, 11};
        FastSort fs = new FastSort();
        int end = test.length - 1;
        fs.fastSort(test, 0, end);
        for(int i: test){
            System.out.print(i);
        }
    }
    public void fastSort(int[] array, int start, int end){
        if(start < end){
            //用递归实现 随便一个数的左边都是大于他的数 右边都是小于他的数 从而有序
            int flag = getFlag(array, start, end);
            //左边乱序递归排序，直到最小单位数对比交换也就是两个数
            fastSort(array, start, flag - 1);
            //右边乱序递归排序
            fastSort(array, flag + 1, end);
        }
        
    }
    //flag标识位置，位置左边都是比对比数大的，位置右边都是比对比数小的  index数组角标
    //返回标识位
    public int getFlag(int[] array, int start, int end){
        int flag = start;
        int fixNum = array[end];
        for(int index = start; index <= end - 1;index++){
            if(array[index] > fixNum){
                //大于对比位的->当前为数组末尾的数是对比数，放到flag位置，flag右移，相当于数组大小不变，将大的数放到左边
                swap(array, index, flag);
                flag++;
            }else if(array[index] == fixNum){
                flag++;
            }
        }
        //最后将flag位置的数换成对比数，以实现对比数左边的都比其大，右边的都比其小
        swap(array, flag, end);
        return flag;
    }
    private void swap(int[] array, int index, int flag) {
        int temp = array[index];
        array[index] = array[flag];
        array[flag] = temp;//可以优化，如果交换的两个数相等可以跳过
        
    }

}