algorithm - 在什么情况下使用这些排序算法？

Question

我知道大多数这些算法的实现，但我不知道将它们用于什么大小的数据集（以及包含的数据）：

1. 合并排序
2. 冒泡排序（我知道，不经常）
3. 快速排序
4. 插入排序
5. 选择排序
6. 基数排序

Answer 1

首先，您将所有具有O(n2)复杂性的排序算法都扔掉。

然后，您必须研究排序算法的几种特性，并确定它们中的每一种是否更适合您要解决的问题。最重要的是：

算法到位了吗？这意味着排序算法不使用任何（O(1)实际上）额外的内存。当您运行内存关键型应用程序时，此属性非常重要。

冒泡排序、插入排序和选择排序使用常量内存。合并排序也有一个就地变体。

算法稳定吗？这意味着如果给定比较方法的两个元素x和y相等，并且在输入x中找到之前y，那么在输出x中将找到之前y。

合并排序、冒泡排序和插入排序是稳定的。

算法可以并行化吗？如果您正在构建的应用程序可以使用并行计算，您可能需要选择可并行排序算法。

更多信息在这里。

Answer 2

仅当要排序的数据存储在转鼓内存中时才使用冒泡排序。它最适合该目的，但不适用于随机存取存储器。如今，这相当于“不要使用冒泡排序”。

使用插入排序或选择排序，直到您通过针对您可用的其他排序进行测试而确定的某个大小。这通常是大约 20-30 个项目，但 YMMV。特别是，在实现像合并排序和快速排序这样的分治排序时，当当前数据块足够小时，您应该“突破”到插入排序或选择排序。

还要对几乎排序的数据使用插入排序，例如，如果您以某种方式知道您的数据曾经是排序的，并且此后没有太大变化。

当您需要稳定的排序时使用合并排序（在对链表进行排序时也很好），请注意对于数组，它会使用大量额外的内存。

通常，您根本不使用“普通”快速排序，因为即使智能选择枢轴，它仍然有Omega(n^2)最坏的情况，但与插入排序不同，它没有任何有用的最佳情况。“杀手”案例可以系统地构建，因此如果您正在对“不可信”数据进行排序，那么某些用户可能会故意破坏您的性能，并且无论如何可能存在某些特定领域的原因导致您的数据接近杀手案例。如果您选择随机枢轴，那么致命案例的概率可以忽略不计，因此这是一个选项，但通常的方法是“IntroSort”——一种检测不良案例并切换到堆排序的快速排序。

基数排序有点奇怪。很难找到最适合的常见问题，但它对于固定宽度数据（O(n)，比较排序是Omega(n log n)）具有良好的渐近限制。如果您的数据是固定宽度的，并且输入大于可能值的数量（例如，超过 40 亿个 32 位整数），那么某些种类的基数排序就有可能表现良好。

Answer 3

1. 当使用等于数组大小的额外空间时不是问题
2. 仅在非常小的数据集上
3. 当您需要就地排序且不需要稳定排序时
4. 仅在非常小的数据集上，或者如果数组很可能已经排序
5. 仅在非常小的数据集上
6. 当取值范围与项数比值较小时（建议实验）

请注意，通常合并或快速排序实现对子例程中子数组非常小的部分使用插入排序。