algorithm - 选择排序算法的标准

Question

我很想知道如何根据输入选择排序算法，以便获得最佳效率。

它应该是关于输入的大小或输入的排列方式(升序/降序)或使用的数据结构等......？

Answer 1

一般而言，算法以及排序算法的重要性如下:

(*) 正确性 - 这是最重要的事情。如果你的算法 super 快速和高效，但它是错误的，那它就一文不值。在排序中，即使你有 2 个正确排序的候选人，但你需要一个 stable sort - 你会选择稳定的排序算法，即使它效率较低 - 因为它对你的目的是正确的，而另一个则不是。

接下来基本上是在运行时间、所需空间和实现时间之间进行权衡(如果您需要从头开始实现某些东西而不是使用库，以提高性能 - 它可能不会'不值得)

考虑上述权衡时需要考虑的一些事项:

1. 输入的大小(例如:对于小输入，插入排序在经验上比更高级的算法更快，尽管它需要 O(n^2))。
2. 输入的位置(磁盘上的排序算法与 RAM 上的算法不同，因为磁盘读取在非顺序时效率低得多。通常用于磁盘排序的算法是一种变体归并排序)。
3. 数据是如何分布的？如果数据可能“几乎已排序”- 也许通常糟糕的冒泡排序只需 2-3 次迭代即可对其进行排序，并且与其他算法相比速度超快。
4. 您已经实现了哪些库？实现新事物需要多少工作？值得吗？
5. 输入的类型(和范围)- 对于可枚举 数据(例如整数)- 整数设计算法(如基数排序)可能比一般情况下的算法更有效。
6. 延迟要求 - 如果您正在设计导弹头，并且结果必须在特定时间内返回，快速排序可能会在最坏的情况下衰减到二次运行时间 - 可能不是一个好的选择，并且您可能希望使用具有严格 O(nlogn) 最坏情况的不同算法。
7. 您的硬件 - 例如，如果您正在使用一个巨大的集群和大量数据 - 分布式排序算法可能比尝试在一台机器上完成所有工作更好。