c++ - 面对昂贵的交换的双枢轴快速排序

Question

将此问题移至 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 只有基元和引用类型，所以交换总是很便宜的。 (即便如此，它只对原语使用这种排序，因为它不稳定)

所以我想看看是否有人已经测试了标准快速排序与双主元快速排序，当元素交换成本很高并且有数字(可能还有来源)时，或者我是否必须自己测试这个。

这个问题专门针对快速排序变体。

Answer 1

我实际上在我的论文中对此进行了广泛的研究。 https://arxiv.org/ftp/arxiv/papers/1505/1505.00558.pdf

简短的回答是，不。与交换大元素时的高端版本的快速排序相比，双枢轴的性能不佳。请看图 22 和 23。