@SuppressWarnings("all")
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {-1,-2,3,1,20,10,9,5};
        quickSort(arr,0,arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr,int left,int right){
        int low = left;//左下标
        int max = right;//右下标
        //中间下标
        int pivot = arr[(left + right) / 2];

        //临时交换值变量
        int temp = 0;
        //while循环的目的是让比pivot值小放到左边比pivot值大的放到右边
        while(low < max){
            //在pivot的左边一直找，找到大于pivot值，才退出
            while(arr[low] < pivot){
                low += 1;
            }

            //在pivot的右边一直找，找到小于pivot值，才退出
            while(arr[max] > pivot){
                max -= 1;
            }

            //如果low >= max说明pivot 的左右两边的值，已经按照左边全部是
            //小于等于pivot的值，右边全部是大于等于pivot的值
            if(low >= max){
                break;
            }

            //交换
            temp = arr[low];
            arr[low] = arr[max];
            arr[max] = temp;

            //如果交换完后，发现这个arr[low] == pivot值 相等 则 max -- ，前移
            if(arr[low] == pivot){
                max -= 1;
            }

            //如果交换完后，发现这个arr[max] == pivot值 相等 则 low ++ ，后移
            if(arr[max] == pivot){
                low += 1;
            }

            //如果low == max,必须low ++ , max -- ,否则会出现堆栈溢出
            if(low == max){
                low += 1;
                max -= 1;
            }

            //向左递归
            if(left < max){
                quickSort(arr,left,max);
            }

            //向右递归
            if(right > low){
                quickSort(arr,low,right);
            }
        }
    }
}