java - 使用重复键快速排序会变得更快(没有三向分区)。到底是怎么回事？

Question

我有点困惑。我一直在尝试测试快速排序，一切似乎都工作正常，除了，当我有许多重复的数组元素时，我得到了意想不到的结果。

• 代码实际上对数组进行了排序。
• 代码实际上在一个时间范围内对数组进行排序，即期望快速排序。
• 当数组排序或反向排序时，我会得到预期的低效率(当然，当枢轴设置为第一个元素时)
• 我使用随机库 nextInt 方法来填充数组。

当我减少数据范围(从而在数组中放入更多重复项)时，快速排序运行得更快。

100 万个元素(范围 0 - 100 万):155 毫秒

100 万个元素(范围 0 - 2):118 毫秒

3000 万个元素(范围 0-100 万):3085 毫秒

3000 万个元素(范围 0-2):1021 毫秒

我尝试了很多次，所以这似乎不是由于随机化造成的。随着数据的增加，差异变得更加明显。

我找不到任何解释为什么会发生这种情况。

这是我的代码:

public void qsort2median(int array [], int lowest, int highest)
    {
        int pivot = array[(lowest+highest)/2];
        int left = lowest;
        int right = highest;

        while (left <= right){
            while (array[left] < pivot){
                left ++;
            }
            while (array[right] > pivot){
                right--;
            }
            if (left <= right){
                int temp = array [left];
                array[left] = array[right];
                array[right] = temp;
                left ++;
                right--;
            }
        }
        if (lowest < right) {
            qsort2median(array, lowest, right);
        }
        if (left < highest) {
            qsort2median(array, left, highest);
        }
    }

这是我的运行方式:

    int [] arraytest = new int  [1000000];
    int [] arraytest1 = new int [1000000];

    Quicksort qsorttest = new Quicksort();

    qsorttest.randomArrayGenerator(arraytest,2);

    System.arraycopy(arraytest,0,arraytest1,0,arraytest.length);
    int endpoint = arraytest.length-1;

    //RUN FIRST ARRAY
    long startTime = System.currentTimeMillis();
    qsorttest.qsort2median(arraytest,0,endpoint);
    long endTime = System.currentTimeMillis();

    long duration = (endTime - startTime); 
    System.out.println("Quicksort with Median Element pivot ran in: " + duration);

这是我的randomArrayGenerator方法:

void randomArrayGenerator(int [] array, int n){

    Random generator = new Random();

    System.out.println();
    System.out.println(array.length);

    for (int i = 0; i < array.length; i++){

        array[i]= generator.nextInt(n);
    }
}

感谢您的任何意见。

截至周一，我仍在努力解决这个问题。

Answer 1

我想我可以回答我自己的问题。

经过进一步研究，我发现只有当快速排序算法使用 Lomuto 的分区时，重复才会成为问题。另一方面，这使用了霍尔划分。

我测试了它们并得到了预期的结果。

因此，Lomuto 的分区随着重复项的增加而变慢，而 Hoare 的算法随着重复项的增加而变得更快。