java快速排序问题

Question

package Sort;

public class QuickSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arr1 = {6,3,7,9,5,1};
        Quick(arr1,0,arr1.length-1);
        for(int i = 0;i < arr1.length;i++) {
            System.out.print(arr1[i] + " ");
        }
    }
    public static void Quick(int[] arr,int left,int right) {
        if(left > right) {
            return;
        }
        int base = arr[left];
        int i = left;
        int j = right;
        while(i != j) {
            while(base < arr[j] && i < j) {
                j--;
            }
            while(base > arr[i] && i < j) {
                i++;
            }
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        arr[left] = arr[i];
        arr[i] = base;
        Quick(arr,left,i-1);
        Quick(arr,j+1,right);
    }
}

请问为什么输出结果不对呢？

Answer 1

引自免费微信小程序：皆我百晓生

在你提供的Java快速排序代码中，问题出在while循环条件和交换元素的部分。以下是修正后的代码：

package Sort;

public class QuickSort {

    public static void main(String[] args) {
        int[] arr1 = {6, 3, 7, 9, 5, 1};
        Quick(arr1, 0, arr1.length - 1);
        for (int i = 0; i < arr1.length; i++) {
            System.out.print(arr1[i] + " ");
        }
    }

    public static void Quick(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int base = arr[left];
        int i = left;
        int j = right;

        while (i < j) {
            // 找到右侧小于基准值的元素
            while (arr[j] > base && i < j) {
                j--;
            }
            // 找到左侧大于基准值的元素
            while (arr[i] < base && i < j) {
                i++;
            }

            // 当i < j时，交换这两个元素
            if (i < j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // 将基准值放在正确的位置（即i位置）
        arr[left] = arr[i];
        arr[i] = base;

        // 对基准值左侧和右侧的子数组进行递归排序
        Quick(arr, left, i - 1);
        Quick(arr, i + 1, right);
    }
}

原代码存在的问题是，在while(i != j)循环中，当找到一个满足条件的元素后直接进行了交换，这可能会导致已经排好序的元素被错误地交换。修正后的代码确保了只有在i < j的情况下才进行交换，并且对左右指针分别判断基准值两边的元素，这样可以正确地实现快速排序算法。同时，将递归调用的边界条件修改为left >= right，避免在只有一个元素或没有元素时依然进行递归调用。