我正在尝试粗略地对 QuickSorts(单枢轴、三向和双枢轴)的性能进行基准测试。
问题1: 恐怕我在执行3路分区时遗漏了一些东西。在针对随机输入(1000 万个)数字的多次运行中,我可以看到单个枢轴总是表现更好(尽管对于 1000 万个数字,差异在 100 毫秒左右)。
我知道 3-way 的全部目的不是重复键的 0 (n^2) 性能 - 当我针对重复输入运行它时,这一点非常明显。但是真的是为了处理重复数据,用3-way来取小罚分吗?还是我的实施不好?
重复数据:
- 基本快速排序:888 毫秒
- 快速排序 3 路:522 毫秒
- 快速排序双枢轴:482 毫
随机数据:
- 基本快速排序:1677 毫秒
- 快速排序 3 方式:1717 毫秒
- 快速排序双枢轴:1595 毫秒
问题2 :
Dual Pivot 实现(下面的链接)不能很好地处理重复。执行需要 0(n^2) 时间。有没有快进的好方法。我可以看到我们可以检查枢轴是否相等并增加枢轴1,直到它与枢轴2不同。这是一个公平的实施吗?
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
QuickSort(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
测试用例: https ://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSortTest.java