为什么QuickSort Single比3路分区快速转换？

Question

我试图粗略地测试QuickSorts（Single Pivot，3-way和Dual Pivot）的性能。

问题1： 恐怕我在执行3路分区时丢失了一些东西。在对数随机输入（1000万个）数字进行的几次运行中，我可以看到单个数据透视总是表现更好（尽管对于1000万个数字，差异大约在100毫秒左右）。

我知道3-way的全部目的不是0（n^2）在重复键上的性能 - 当我对重复输入运行时，这非常明显。但是，为了处理重复的数据，是否真的有一个小的惩罚是通过3路？或者我的执行不好？

重复数据：

• 快速排序基本：888米利斯
• 快速排序3路：522米利斯
• 快速排序双枢轴：482米利斯

随机数据：

• 快速排序基本：1677个米利斯
• 快速排序3路：1717个米利斯
• 快速排序双枢轴：1595个米利斯

问题2：

的双枢轴实施（下面的链接）不能很好地处理重复。它需要一个0（n^2）的时间来执行。有没有一种快速前进的好方法。我可以看到，我们可以检查pivot是否相等，并将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

快速排序（单枢轴）：https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSortBasic.java

快速排序（3路分区）： https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSort3Way.java

快速排序（双 透视）： https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSortDualPivot.java

的TestCase： 的所有摆脱建设者的suffle来得到正确的比较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++; 
     } 


    }