我应该在什么情况下使用这些排序算法？

Question

我知道这些算法的实现方式，但是不知道它们适用于哪些大小的数据集（以及包含哪些数据）：

1. 归并排序
2. 冒泡排序（我知道，很少用）
3. 快速排序
4. 插入排序
5. 选择排序
6. 基数排序

- Jake Byman

Answer 1

首先，你需要丢弃所有时间复杂度为O(n2)的排序算法。

然后，您需要研究多种排序算法的特性，并决定哪种算法更适合解决您想要解决的问题。最重要的是：

算法是否为原地算法？这意味着排序算法不使用任何（实际上是O(1)的）额外内存。当您运行内存受限的应用程序时，此属性非常重要。

冒泡排序、插入排序和选择排序使用恒定的内存。归并排序也有一种原地变体。

算法是否稳定？这意味着如果两个元素x和y在给定比较方法的情况下相等，并且在输入中x出现在y之前，则在输出中x将在y之前找到。

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

算法能否并行化？如果您构建的应用程序可以利用并行计算，则可能要选择可并行化的排序算法。

更多信息在此处。

- alestanis

Answer 2

只有在数据存储在旋转鼓式存储器上时，才使用冒泡排序。它对此目的是最优的，但不适用于随机访问存储器。现如今，这相当于“不要使用冒泡排序”。

使用插入排序或选择排序，直到您通过对其他可用排序进行测试确定某个大小为止。这通常约为20-30个项目，但因人而异。特别是，在实现分治排序（如归并排序和快速排序）时，当当前数据块足够小时，应“退出”插入排序或选择排序。

还可以在几乎排序的数据上使用插入排序，例如如果您以某种方式知道您的数据曾经被排序过，并且自那以后没有发生太大变化。

当您需要稳定排序时，请使用归并排序（在排序链表时也很好），请注意，对于数组，它使用显着的额外内存。

通常根本不使用“普通”快速排序，因为即使选择了智能的枢轴，它仍然具有Ω（n ^ 2）最坏情况，但与插入排序不同，它没有任何有用的最佳情况。可以系统地构造“killer”案例，因此，如果您正在排序“不受信任”的数据，则某些用户可能会故意降低性能，而且可能会有一些特定于域的原因，使您的数据近似于killer案例。如果选择随机枢轴，则杀手案例的概率可以忽略不计，因此这是一种选择，但通常的方法是“IntroSort”-一种检测坏案例并切换到HeapSort的快速排序。

基数排序有点奇怪。很难找到最适合它的常见问题，但对于固定宽度的数据，它具有良好的渐近限制（O（n）），其中比较排序为Ω（n log n）。如果您的数据是固定宽度，并且输入大于可能值的数量（例如，多于40亿个32位整数），则开始有机会某种基数排序表现良好。

- Steve Jessop

Answer 3

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

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

- Bernhard Barker