在一般情况下，“快速排序3路”会比“快速排序”慢吗

Question

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

我的问题是，在一般情况下，quicksort 3way会打败quicksort吗

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

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

Answer 1

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