选择排序算法的标准

Question

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

它应该是在输入大小或如何安排输入（Asc/Desc）或数据结构使用等...？

Answer 1

的算法的重要性一般，和排序算法以及是如下：

（*）正确性 - 这是最重要的事情。如果你的算法速度快，效率高，但是错误，那么它就毫无价值。在排序，即使你有2名候选人是正确排序，但你需要一个stable sort - 你会选择稳定的排序算法，即使是低效率的 - 因为它是正确的你的目的，另一种是没有。

下一页基本运行时间之间权衡，需要空间和实施时间（如果你需要从头开始实现的东西而不是使用一个库，为未成年人提高性能 - 它可能不值得）

有些东西考虑上述关闭提到的贸易时要考虑到：

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

Answer 2

它应该基于所有这些东西。

• 你需要考虑到数据的账户规模为插入排序可能速度比快速排序的小数据集等

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

• 并且您显然需要知道用作如果你的数据已经存在，有一些非常专门的排序算法pecial格式或者即使你可以把它变成一个新的数据结构有效，它会自动做你的排序为你（一拉BST或堆）

Answer 3

决定你的排序算法的选择的2分主要的事情是时间复杂度和空间复杂度。根据您的场景以及可用的资源（时间和内存），您可能需要根据每种排序算法必须提供的排序算法进行选择。

排序算法的实际性能取决于输入数据量太大，而且它有助于如果我们知道输入数据的某些特性事前，如输入的大小，如何排序的数组已经是了。

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

排序算法的选择取决于空间和时间的约束以及输入数据的大小/特性。

Answer 4

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

对于文件的整数，这不会是巨大的相关性，但如果说你排序基于内容的文件，你会很自然想要做的尽可能少的比较成为可能。