public class Hello {

    public static void main(String[] args) {

        //int[] arr = {2,5,1,6,9,3};
        int[] arr = {12,20,5,16,15,1,30,45,23,9};
        quickSort(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }


    public static int quickSort(int[] arr, int left, int right){

        if(left > right){
            return 0;
        }

        int i = left;
        int j = right;
        // 基准位
        int base = arr[left];

        while(i < j){
            // 先看右边，依次往左递减
            // i < j 防止越界
            while(arr[j] >= base && i < j){
                j--;
            }
            // 再看左边，依次往右递增
            while(arr[i] <= base && i < j){
                i++;
            }
            // 如果满足条件则交换
            int tmp = arr[j];
            arr[j] = arr[i];
            arr[i] = tmp;
        }
        // 最后将基准为与i和j相等位置的数字交换
        // 必须注意交换顺序
        arr[left] = arr[i];
        arr[i] = base;

        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);

        return 0;
    }
}