import java.util.Arrays;
/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * 快速排序
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {6,1,8,0,0,9,5,3,7};
        quickSort(arr, 0, arr.length-1);
        System.out.println("排序后: " + Arrays.toString(arr));
    }
    //快速排序
    public static void quickSort(int[] arr, int left, int right) {
        //边界条件
        if (left > right){
            return;
        }
        //定义基准数和左右指针
        int l = left;
        int r = right;
        int base = arr[left];
        //循环，将比基准数小的放在左边，比基准数大的放在右边
        while (l != r){
            //先从右边找比基准数小的，停下
            while (arr[r] >= base && l < r){
                r--;
            }
            //从左边找比基准数大的，停下
            while (arr[l] <= base && l < r){
                l++;
            }
            //此时已经找到对应的l 和 r，进行交换
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
        }
        //至此，基准数两边都按照需要排好了，只需要将基准数与lr相遇的位置进行交换
        arr[left] = arr[l];
        arr[l] = base;
        //打印中间结果
        System.out.println(Arrays.toString(arr));
        //先向左找
        quickSort(arr, left, r-1);
        //向右递归
        quickSort(arr, l+1, right);
    }
}