已将此问题移至 Programmers ，因为它对于 CS 来说似乎不够理论。
TLDR
有人用昂贵的交换元素测试过双枢轴快速排序性能吗？看来在这种情况下，它的性能应该大大低于标准快速排序。
背景故事
受到最近“问题”的启发here on stack overflow ，我决定去实现给定排序的非平凡版本( introsort 、 quicksort 和 3-way partition 、3 个主元选择的中值、小块插入排序等)。
在一些研究过程中，我还发现了双枢轴快速排序，which is the current implementation of quicksort in Java standard library 。一般来说，它声称它总是至少与标准快速排序一样好，并且经验测试似乎支持它。 (这就是当前实现的原因。)
但是，似乎没有 STL 实现在 introsort 的快速排序阶段使用双枢轴快速排序，这让我想知道为什么。经过更多研究，我发现this paper 。它表示，虽然双枢轴快速排序的比较次数平均减少 5%，但它执行的交换次数却显着增加。 (大约多出 80%)显然，由于 Java 只有原语和引用类型，因此交换总是很便宜。 (即便如此，它仅对基元使用这种排序，因为它不稳定)
因此，我想看看是否有人已经测试了标准快速排序与双枢轴快速排序(当元素交换成本昂贵并且有数字(可能还有源)存在时)，或者我是否必须自己进行测试。
这个问题专门涉及快速排序变体。
最佳答案
我实际上在我的论文中对此进行了广泛的研究。 https://arxiv.org/ftp/arxiv/papers/1505/1505.00558.pdf
简短的回答是，不。在交换大元素时，与高端版本的快速排序相比，双枢轴的性能较差。请看图 22 和 23。
关于c++ - 面对昂贵的交换，双枢轴快速排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25314224/