我在哪些情况下使用这些排序算法？

Question

我知道大多数的这些算法的实现，但我不知道自己适合什么尺寸的数据集使用它们（和数据在内）：

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

Answer 1

首先，您将所有具有复杂度的排序算法丢弃。

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

算法是否就地？这意味着排序算法不会使用任何（O(1)实际）额外的内存。在运行内存关键型应用程序时，这个规则非常重要。

冒泡排序，插入排序和选择排序使用常量内存。 还有一个适用于Merge-sort的就地变体。

该算法是否稳定？这意味着，如果两个元件x和y相等给出的比较方法，并在输入xy之前被发现，则在输出x将y之前找到。

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

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

更多信息here。

Answer 2

1. 当使用额外的空间等于数组的大小不是问题
2. 只有在非常小的数据集
3. 当你想就地排序和稳定排序不需要
4. 仅在非常小的数据集，或者如果阵列具有高概率已经被排序
5. 仅在非常小的数据集
6. 当值项的数的范围比小（实验建议的）

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

Answer 3

使用气泡仅当要排序的数据存储在旋转鼓内存上时才进行排序。这是最佳的，但不适用于随机存取存储器。这些日子，这相当于“不使用泡沫排序”。

使用插入排序或选择根据您可用的其他种类对其进行测试，按照您确定的大小排序。这通常是约20-30项，但YMMV。特别是，当实施合并排序和快速排序等分而治之的排序时，当您当前的数据块足够小时，您应该“分解”为插入排序或选择排序。

还可以使用插入对接近排序的数据进行排序，例如，如果您以某种方式知道您的数据曾经被排序，并且自那以后没有多大改变。

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

一般而言，您根本不使用“普通”快速排序，因为即使智能选择枢轴，它仍然有最坏情况Omega(n^2)，但与插入排序不同，它没有任何有用的最佳情况。 “杀手”案件可以系统地构建，所以如果你排序“不可信”的数据，那么一些用户可能故意杀死你的表现，无论如何，可能存在一些特定领域的原因，为什么你的数据接近杀手案件。如果您选择随机枢纽，那么杀手案件的可能性可以忽略不计，所以这是一种选择，但通常的方法是“IntroSort” - 一种QuickSort，可检测不良情况并切换到HeapSort。

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