public class QuickSort {
    public static void quickSort(int[] arr, int low, int high){
        if (low >= high){
            return;
        }
        //退出条件是左端哨兵在右端哨兵的右边。

            int temp = arr[low];     //temp就是基准位
            int left = low;                   //左端哨兵位置
            int right =high;                  //右端哨兵位置
            int t;                            //交换数据的临时变量
            //循环条件：左边哨兵位置还在右边哨兵位置的左边，右端哨兵往左走，左端哨兵往右走，直到相遇。
            while ( left< right) {
                //1、先看右边，依次往左递减，右端哨兵往左走。找到比基准点小的数据就停止
                while (temp <= arr[right] && left < right) {
                    right--;
                }
                //2、再看左边，依次往右递增，左端哨兵往右走，找到比基准点大的数据就停止
                while (temp >=arr[left] && left < right) {
                    left++;
                }
                //3、如果满足条件没有相遇则交换
                if (left < right) {
                    t = arr[right];
                    arr[right] = arr[left];
                    arr[left] = t;
                }
            }
        /*
        最后将基准为与i和j相等位置的数字交换，i和j相遇之后就与基准点交换数据，
        交换之后就完成了：基准点左边都是小于等于基准点，基准点右边都是大于等于基准点。
         */
            arr[low] = arr[left];
            arr[left] = temp;
            //递归调用左半数组，此时就需要传入左半数组的首尾索引值，以及数组。
            quickSort(arr, low, right - 1);
            //递归调用右半数组
            quickSort(arr, right + 1, high);

    }
}