双边快排的基准点和先判断left还是right问题-526互联

前同事问了我一个双边快排的算法，他问我怎么都无法正常排序，代码如下，

public static void main(String[] args) {
        int[] arr = new int[]{7,3,6,4,8,9,0,22,28,2,3,79,24};
        arr = new int[]{4,4,6,5,3,2,8,1};

        System.out.println("left:"+0+"  right:"+(arr.length-1)+ " " +Arrays.toString(arr));

        TestJDBC testJDBC = new TestJDBC();
        testJDBC.quickSort(arr,0,arr.length-1);

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }

    public void quickSort(int[] arr,int startIndex,int endIndex){
        if(startIndex>=endIndex) return ;

        int pivotIndex = partation(arr,startIndex,endIndex);
        quickSort(arr,startIndex,pivotIndex-1);
        quickSort(arr,pivotIndex+1,endIndex);
    }

    public int partation(int[] arr ,int startIndex,int endIndex){
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;


        while(left!=right){

            while(left<right&&arr[left]<=pivot){
                left++;
            }

            while(left<right&&arr[right]>pivot){
                right--;
            }
//            while(left<right&&arr[left]<=pivot){
//                left++;
//            }
            if(left<right){
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }

            System.out.println("left:"+left+"  right:"+right+ " " +Arrays.toString(arr));

        }

        arr[startIndex] = arr[left];
        arr[left] = pivot;

        return left;
    }

上述快排的输出结果如下，

从上面结果可以看出，在 left:5 right:5 [4, 4, 1, 2, 3, 5, 8, 6] 这里开始出问题了，

如下图所示，当left和right在3，5时，先运算的left，导致left直接到right那了，然后进行交换4和5交换，

所以左边待排序数组变为 5, 4, 1, 2, 3 右边待排序数组变为 8, 6 。

错误的原因就在于先左边还是先右边顺序的问题，修改后代码如下，输出如下图，

基准点选择了左边，从右边先开始即可，

//            while(left<right&&arr[left]<=pivot){
//                left++;
//            }

while(left<right&&arr[right]>pivot){
    right--;
}
while(left<right&&arr[left]<=pivot){
    left++;
}

基准点是从左边选的，而left <= pivot，所以left先判断肯定left第一次是满足条件，这样有可能就直接让left==right了。