algorithm - 在一般情况下，`quicksort 3way` 会比 `quicksort` 慢吗？

Question

Qucksort 3way旨在帮助数组中许多/大多数项目相等的情况。

我的问题是在一般情况下会quicksort 3way节拍吗？quicksort

在一般情况下，我的意思是没有多少项目是相等的或更进一步，所有项目都是不同的。

我做了一些基准测试，我的感觉是，在一般情况下，quicksort 3way甚至比经典的quicksort.

Answer 1

想一想：您有一个算法旨在帮助您解决另一种算法的更坏情况。当然，在一般情况下，它不应该击败初始算法。三路快速排序的想法是改善最坏情况的行为，而不是平均情况。