java中的快速排序不正确

Question

我一直试图了解这里发生的事情：

import java.util.Random;

public class QuickSort {
    static Random random = new Random();

    static void quickSort(int[] arr,
                          int lo,
                          int hi){
        //best case
        if(lo >= hi){return;}

        int pivot = partition(arr,lo,hi);

        quickSort(arr, pivot+1, hi);
        quickSort(arr, lo, pivot-1);
    }

    static int partition(int arr[],
                         int lo,
                         int hi){
        int pivPoz=lo + random.nextInt(hi - lo + 1);
        int pivot = arr[pivPoz];

        int index = lo - 1;

        for(int i = lo;i<=hi; i++){
            if(arr[i] <= pivot && i!=pivPoz ){
                index++;
                int a = arr[index];
                arr[index] = arr[i];
                arr[i] = a;
            }
        }

        index++;
        int a = arr[index];
        arr[index] = arr[pivPoz];
        arr[pivPoz] = a;

        return index;
    }

    public static void main(String[] args){

        int arr[] = new int[]{4,2,8,12,30,1,3,9,10,9,12};
        quickSort(arr,0,arr.length-1);
        for(int i : arr){
            System.out.print(i + "\t");
        }
    }
}

这是我用 Java 实现的快速排序算法。我知道代码太长了，我可以做得更好，但是解决这个错误之后我就可以做到。我注意到一些奇怪的事情。我正在使用相同的输入运行相同的程序，但以不同的结果结束，例如：

1. 输入 = {4,2,8,12,30,1,3,9,10,9,12} 输出 = {1 2 3 4 8 9 9 10 12 12 30}

2. 输入 = {4,2,8,12,30,1,3,9,10,9,12} 输出 = {8 3 2 4 9 9 10 12 12 30 1}

3. 输入 = {4,2,8,12,30,1,3,9,10,9,12} 输出 = {2 4 8 9 9 10 12 3 1 12 30}

我没有对代码进行任何更改，只需运行它即可。您对为什么会发生这种情况有什么建议吗？

Answer 1

问题在于，在类似 Lomuto 的算法中，您将主元留在正在迭代的范围内。您确实对

i != pivPoz

采取了一些预防措施，但是当

index

超越

pivPoz

时，仍然会留下一些问题的余地：

当

index++

使

index

等于

pivPoz

时，枢轴将交换到另一个索引，因此您将无法跟踪枢轴所在的位置，并返回错误的索引。

避免这些问题的通常方法是首先将随机选择的枢轴交换到范围的右端，因此它位于索引

hi

。然后，该索引将从循环中排除，这样就不会出现此问题。