爲什麼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++; 
     } 


    }