排序算法中最快的排序-排序表是什么？

Question

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

Answer 1

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

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

1. 在小输入上切换到更快的排序:插入排序在二次时间内运行，但对于小输入，它可以比快速排序快得多。一旦要排序的元素数量低于某个阈值，快速排序实现就会切换到插入排序，这会显著减少runtimes.
2. Adding自省。内部排序是快速排序的快速变体，它跟踪递归深度，并在算法看起来正在退化时切换到堆排序。这保证了运行时将是O( n )，并且如果这种情况不是triggered.
3. Using (一种更好的分区算法)，则只会产生很小的开销。双轴快速排序最近作为传统分区算法的替代算法出现在舞台上。它在许多输入上都有更好的性能。此外，如果您希望获得带有大量duplicates.
4. Introduce尾部调用消除的输入，请考虑使用一种能够优雅地处理重复元素的分区方案。许多快速排序实现对需要排序的两个子数组执行两次递归调用，但实际上并不需要这样做。您可以启动一个递归调用，然后通过覆盖初始调用的参数并将整个过程放入while循环中，将第二个调用视为尾部调用。