快排，代码思路详解

1.1以left为基准：推理证明

快排的基本结构如下：

1.2以right为基准：推理证明

2.while条件选择

对于这个条件

因为在这之前就有保证
因此可以直接写为

3.顺序or倒序

这个无关base基准值的选取（base的选取只关心最后 l 左指针和对应的base进行交换、先r–还是先l++）
我们以 int base = arr[left];为例（先r–后l++）

3.1顺序

3.2倒序

只需要修改大于小于即可

4.完整代码

• 本案例以left为基准，先r–后l++，同时最后无论如何都交换 l 和 left

• 顺序

    public class QuickSort2 {
        public static void main(String[] args) {
            int[] arr = new int[]{23, 5, 2, 3, 4, 6, 2345, 23, 4, 5, 12, 67, 5, 3, 6, 5, 3, 1};
            sort(arr,0 , arr.length-1);
            System.out.println(Arrays.toString(arr));
        }
        public static void sort(int[] arr, int left , int right){
            //1.指针交叉
            if(left >= right){return;}
            //2.设置基准
            int l = left;
            int r = right;
        //以arr[left] 为基准，无论如何（即便是l、r指针重合） 都需要交换l和left的位置，因此需要先对r指针左移
        //以arr[right]为基准，无论如何（即便是l、r指针重合）都需要交换l和right的位置，因此需要先对l指针左移
            int base = arr[left];
            //3.交换
            while(l!=r){ //或写成while( l= base){ r--; }
                //3.2 l指针右移
                while(l < r && base >= arr[l]){ l++; }
                //3.3本轮是否指针重合
                if(l >= r){ break; }
                     //没有指针重合才能交换l和r
                else { swap(arr,l,r); }
            }
            //4.如果l和r交叉了，两种情况（解释了:以arr[left]为基准为何需要交换l和left）
                //r--左移到头没找到比base大的，那么l不动，l==left可以随意交换
                //r--找到了，但是l++没有找到，l直接到了，l==r，即arr[l]==arr[r]==base，也可以随意交换
            swap(arr,l,left);
            //5.递归
            sort(arr,left,l-1);
            sort(arr,r+1,right);
        }
    
        public static void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    
    }