为什么我的快速排序方法非常慢？

Question

只是尝试合并排序的迭代版本，它的执行速度比所有排序算法都慢得多。我哪里错了？

public static void quickSort(int[] arr) {
    int size = arr.length;
    int count = 0;
    int[] stackArr = new int[size]; 

    stackArr[count] = 0;
    stackArr[++count] = size - 1;

    while (count >= 0) {
        int end = stackArr[count--];
        int start = stackArr[count--];
            
        int pivot = partition(arr, start, end);

        if (pivot - 1 > start) {
            stackArr[++count] = start;
            stackArr[++count] = pivot - 1;
         }
        if (pivot + 1 < end) {
            stackArr[++count] = pivot + 1;
            stackArr[++count] = end;
        }         
    }
}

public static int partition(int[] arr, int start, int end) {
    int countIndex = start ;
    for (int i = start; i < end; i++) {
        if (arr[i] <= arr[end]) {
            swap(arr, i, countIndex);
            countIndex++;
        }
    }
    swap(arr, countIndex, end);
    return countIndex;
}

public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

我刚刚尝试在 java 中编写一个 quickSort() 方法进行测试，但它执行起来非常慢。我想找出问题所在？

Answer 1

问题中的代码使用最后一个元素作为主元，这是对已排序或反向排序数据的最坏情况。问题中未显示用于对排序函数进行基准测试的代码：第一个排序可能对数组进行排序，然后排序后的数组用于基准测试中的其余排序函数。为避免这种情况，请使用第二个数组。创建随机数组后，对于每个排序测试，将其复制到第二个数组并在第二个数组上测试排序。

问题还使用 Lomuto 分区方案，如果存在重复值，它会向最坏情况退化。

以下代码几乎是 Hoare 原始版本的快速排序的副本，它是在没有本机堆栈的系统上实现的。为了将堆栈大小限制为 O(log2(n))，较大的分区索引被压入堆栈，而较小的分区通过循环回分区代码来处理。

    @SuppressWarnings("empty-statement")
    public static void qsort(int[] a)
    {
        if(a.length < 2)
            return;
        // count = (1+floor(log2(a.length)))<<1 
        int count  = (32-Integer.numberOfLeadingZeros(a.length))<<1;
        int[] stack = new int[count];
        count = 0;
        stack[count++] = a.length-1;
        stack[count++] = 0;
        while(count != 0){
            int lo = stack[--count];
            int hi = stack[--count];
            while(lo < hi){
                int  md = lo+(hi-lo)/2;     // partition
                int  ll = lo-1;
                int  hh = hi+1;
                int t;
                int p = a[md];
                while(true){
                    while(a[++ll] < p);
                    while(a[--hh] > p);
                    if(ll >= hh)
                        break;
                    t     = a[ll];
                    a[ll] = a[hh];
                    a[hh] = t;
                }
                ll = hh++;
                // push larger partition indexes onto stack
                // loop on smaller partition
                if((ll - lo) >= (hi - hh)){
                    stack[count++] = ll;
                    stack[count++] = lo;
                    lo = hh;
                } else {
                    stack[count++] = hi;
                    stack[count++] = hh;
                    hi = ll;
                }
            }
        }
    }