思想 （分治）

1.确定分界点 （可以是arr[l] , arr[r] , arr[(l+r)/2] , 也可以是随机的）
2.（调整区间）通过分界点确定区间，是左边的数都小于分界点，右边的数都大于分界点
3.递归处理左右两端

详解

如何调整区间：

未优化前：
	原数组是arr，以x为分界点，重新开辟两个新的数组，将小于x的数全部放入a数组中，将大于x的数全部放入b数组中，最后将a，b数组全部合并到arr数组。（增加了空间，但时间复杂度并未增加）
优化操作：
	双指针（l，r），以x为分界值，若l指针所指数小于x，l指针继续向前移动，直至l所指数大于x，然后移动右指针，直至r所指数小于x，此时交换l，r指针所指的数，当左右指针重合（穿过）时，调整区间完成。

模板

/**
 *  时间复杂度（ n log(n) ）
 * 		注意边界取值问题，如果数据较大时，java一定要使用BufferedReader读入（要比scanner快10倍左右）
 */

 static void sort_quick(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int x = arr[left];//以左边界的值为基准值
        int i = left - 1; //因为是先移动指针，在进行判断，所以初始化指针为空
        int j = right + 1;
        while (i<j){
            do {
                i++;
            } while (arr[i] < x);

            do {
                j--;
            }while (arr[j]>x);

            if (i<j){
                int temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }
        //以j为分界值进行递归，基准值就不能是右边界的值
        
        sort_quick(arr,left,j);
        sort_quick(arr,j+1,right);
    }