sorting - 什么是最快的快速排序 - 排序算法的排行榜？

Question

我试图优化我的快速排序以提高性能。对于 4M (1<<22) 个整数项（每个 4 个字节），在可以支持 72 个并发线程（72 个内核）的系统上进行排序需要 0.5 (0.499703) 秒的并行快速排序算法。我有兴趣了解进一步优化并行快速排序的有效方法。此外，在给定工作量的情况下，如果所有排序算法都有一个排名表，是否有兴趣与其他排序算法进行比较？

Answer 1

据我所知，没有用于排序算法的规范排行榜。排序算法的性能取决于很多不同的因素——你得到的输入分布、输入的大小、编程语言的选择、使用的编译器的类型和设置、内核的数量、环境温度房间、操作系统等

至于你的另一个问题——如何优化你的快速排序——没有看到你的代码，很难确定。以下是您可能想要尝试的常见快速排序优化列表。

1. 在小输入上切换到更快的排序：插入排序以二次时间运行，但对于小输入，它可能比快速排序快得多。一旦要排序的元素数量低于某个阈值，快速排序实现切换到插入排序的情况并不少见，这会显着减少运行时间。

2. 增加内省。Introsort 是快速排序的一种快速变体，它跟踪递归深度并在算法看起来退化时切换到堆排序。这保证了运行时间将为 O(n log n)，并且如果不触发这种情况，只会产生很小的成本。

3. 使用更好的分区算法。双轴快速排序最近出现在现场，作为传统分区算法的替代方案。它在许多输入上具有更好的性能。此外，如果您希望获得包含大量重复项的输入，请考虑使用可以优雅地处理重复元素的分区方案。

4. 引入尾调用消除。许多快速排序实现对需要排序的两个子数组触发两次递归调用，但实际上没有必要这样做。您可以触发一个递归调用，然后将第二个调用视为尾调用，方法是将参数覆盖到初始调用并将整个调用置于 while 循环中。