algorithm - 选择排序算法的标准

Question

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

应该是输入的大小还是输入的排列方式（Asc / Desc）或使用的数据结构等......？

Answer 1

一般来说，算法的重要性，以及在排序算法中的重要性如下：

(*)正确性——这是最重要的。如果您的算法超级快速且高效，但它是错误的，那么它一文不值。在排序中，即使您有 2 个正确排序的候选者，但您需要一个稳定的排序- 即使它效率较低，您也会选择稳定的排序算法 - 因为它对您的目的是正确的，而另一个则不是。

接下来基本上是在运行时间、所需空间和实现时间之间进行权衡（如果您需要从头开始实现某些东西而不是使用库，以实现较小的性能增强 - 这可能不值得）

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

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

Answer 2

它应该基于所有这些。

• 您需要考虑数据的大小，因为对于小型数据集等，插入排序可能比快速排序更快

• 由于每种算法的最坏/平均/最佳情况渐近运行时间不同，您需要知道数据的排列（其中一些最坏/平均情况相同，而另一种可能具有明显更差的最坏情况与平均）

• 而且您显然需要知道使用的数据结构，因为如果您的数据已经采用特殊格式，或者即使您可以有效地将其放入一个新的数据结构中，它会自动为您进行排序（a la BST 或堆）

Answer 3

决定您选择排序算法的两个主要因素是时间复杂度和空间复杂度。根据您的方案和可用的资源（时间和内存），您可能需要根据每种排序算法必须提供的内容在排序算法之间进行选择。

排序算法的实际性能也取决于输入数据，如果我们事先知道输入数据的某些特征，例如输入的大小、数组已经排序的程度，将会有所帮助。

例如，如果您事先知道输入数据只有 1000 个非负整数，则可以很好地使用counting sort线性时间对这样的数组进行排序。

排序算法的选择取决于空间和时间的限制，以及输入数据的大小/特征。

Answer 4

在非常高的水平上，您需要考虑插入与每种算法比较的比率。

对于文件中的整数，这不会有很大的相关性，但如果说您正在根据内容对文件进行排序，您自然会希望尽可能少地进行比较。