为什么QuickSort单枢轴比3路分区快？

Question

我试图粗略基准的QuickSorts (单轴，3路和双轴)的性能。

问题1 :我恐怕在实现3路分区时遗漏了一些东西。在几个随机输入(1,000万个)的情况下，我可以看到单支点的性能总是更好(尽管1,000万个数字的差异在100毫秒左右)。

我知道，3-way的全部目的不是对重复键执行0 (n^2)性能--当我对重复输入运行它时，这一点非常明显。但是，为了处理重复的数据，三分制是否真的会造成小的损失呢？还是我的执行不好？

重复数据:

• 快速排序基本: 888 millis
• 快速排序3路: 522 millis
• 快速排序双轴: 482 millis

随机数据:

• 快速排序基本: 1677 millis
• 快速排序3路: 1717 millis
• 快速排序双轴: 1595 millis

问题2 :

双轴实现(下面的链接)不能很好地处理重复。执行它需要0(n^2)时间。快进有好办法吗？我可以看到，我们可以检查枢轴是否相等，并增加pivot1，直到它与pivot2不同。这是否一个公平的实施？

else if (pivot1==pivot2){
        while (pivot1==pivot2 && lowIndex<highIndex){
            lowIndex++; 
            pivot1=input[lowIndex];
        }
    }

实现链接:

根文件夹：https://github.com/arunma/dsa/tree/master/src/basics/sorting/quick

QuickSort (单轴)：https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSortBasic.java

QuickSort (三向分区)：https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSort3Way.java

QuickSort (双轴)：https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSortDualPivot.java

TestCase：https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSortTest.java

Answer 1

首先，消除构造函数中的杂乱，得到正确的比较。

第二，行为是预期的，因为在基本版本中，只有在双方都找到合适的候选人(即在QuickSortBasic.java中)时，才会进行切换。

    while (true){

        while (less(input[++i], input[pivotIndex])){
            if (i==highIndex) break;
        }

        while (less (input[pivotIndex], input[--j])){
            if (j==lowIndex) break;
        }

        if (i>=j) break;

        exchange(input, i, j);

    }

然而，如果元素与枢轴相等，即在QuickSort3Way.java中，则无论如何，您都在做一个切换。

    while (i<=gt){


        if (less(input[i],pivotValue)){
            exchange(input, i++, lt++);
        }
        else if (less (pivotValue, input[i])){
            exchange(input, i, gt--);
        }
        else{
            i++;
        }


    }