快速排序的疑问

Question

QuickSort.java

    public static int partition1(long[] arr, int left, int right, long point){
        
        int leftPoint = left;
        int rightPoint = right - 1; // 因为是以数组最后一个元素的值为中间值，因此最右边从倒数第二个元素开始
        
        while(true){
            
            // 比point值小的，留在左边，循环结束，找到比point大的数
            while(leftPoint < rightPoint && arr[leftPoint] < point) leftPoint++;
            // 比point值大的，留在右边，循环结束，找到比point小的数
            while(leftPoint < rightPoint && arr[rightPoint] > point) rightPoint--;
            
            if(arr[leftPoint] > arr[rightPoint]){
                long temp = arr[rightPoint];
                arr[rightPoint] = arr[leftPoint];
                arr[leftPoint] = temp;
            }else{
                break;
            }
            // printArray(arr);
        }
        
        // 和中间的值进行交换
        long temp = arr[leftPoint];
        arr[leftPoint] = arr[right];
        arr[right] = temp;
        return leftPoint; // 返回中间值的坐标
    }

public static void sort1(long[] arr, int left, int right){
        
        if(left > right) return;
        
        // 设置中间的值
        long point = arr[right];
        int partition = partition1(arr, left, right, point);
        sort1(arr, left, partition - 1);
        sort1(arr, partition + 1, right);
    }

以数组"public static long[] arr = new long[]{20, 8, 12, 45, 18, -8, -20, 35, -1, 58, 90, -7, 65, 2, 14};"为例：
单独调用 partition1方法，可以实现"取数组里最后一个元素，比这个数小的排在左边 比这个数大的排在右边"，以下是运行的截图：

但是递归调用时，快速的结果是不正确的，不知道 partition1 方法哪个步骤错了。

Answer 1

当右边是最大值或者最小值的时候

这里换的位置是默认的初始位置，所以就错了。问题帮你指出来了，接下去懂了吧？

Answer 2

同意@奔跑如风 的解答，但是还有个问题，考虑{1,5,1,1} ，你的partition1的break在这里就会有问题，这个问题就是：小于主元的放左边，大于主元的放右边，那等于主元的呢？按照你的程序，你是把左边的放右边，右边的放左边，虽然你后面写了if判断，但是你的break会直接结束程序，即使你把break换成其它使其继续前进的语句，依旧会有问题，就是在交换主元和划分好的中间的位置时。详情看我的博客：http://www.61mon.com/index.ph...，里边关于等于主元的数的讨论，还有最后多嘴句，哪里来的代码，写的啰嗦。。。。。

Answer 3

    public static int partition2(long[] arr, int left, int right, long point){
        
        int leftPoint = left - 1;
        int rightPoint = right + 1 - 1; // 因为是以数组最后一个元素的值为中间值，因此最右边从倒数第二个元素开始
        
        while(true){
            
            // 比point值小的，留在左边，循环结束，找到比point大的数
            while(leftPoint < rightPoint && arr[++leftPoint] < point);
            // 比point值大的，留在右边，循环结束，找到比point小的数
            while(leftPoint < rightPoint && arr[--rightPoint] > point);
            
            if(arr[leftPoint] > arr[rightPoint]){
                long temp = arr[rightPoint];
                arr[rightPoint] = arr[leftPoint];
                arr[leftPoint] = temp;
            }else{
                break;
            }
            // printArray(arr);
        }
            
        // 和中间的值进行交换
        long temp = arr[leftPoint];
        arr[leftPoint] = arr[right];
        arr[right] = temp;
        
        return leftPoint; // 返回中间值的坐标
    }

这是视频里的partition方法

这是排序算法

    public static void sort2(long[] arr, int left, int right){
        
        if(left > right) return;
        
        // 设置中间的值
        long point = arr[right];
        int partition = partition2(arr, left, right, point);
        sort2(arr, left, partition - 1);
        sort2(arr, partition + 1, right);
    }

单独调用 partition2()方法，也存在您所描述的问题， 但是调用sort2方法，是可以完成排序的。
我没看出 partition1 和 partition2 有啥具体的区别。
@奔跑如风