算法 - 快速排序的疑问

问题描述

问 题

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 方法哪个步骤错了。

解决方案

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

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

这篇关于算法 - 快速排序的疑问的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！