在什么情况下，较慢的排序算法(冒泡排序、选择排序等)比快速排序等较快的算法更有用？

Question

我刚刚写了一篇关于不同排序算法的效率和有用性的文章。我的结论是，在对完全随机的列表进行排序时，合并排序和快速排序要好得多。我只是想问，在什么情况下，这种情况下较慢的排序算法(冒泡排序和选择排序)会比快速排序和合并排序更有用或一样有用。

Answer 1

请注意，合并排序和快速排序都可能需要额外的内存，无论这是保存堆栈以进行递归还是实际复制缓冲区所需的堆空间。

冒泡排序和选择排序不需要额外的内存。因此，在内存受到严格限制的情况下，将使用它们。

Answer 2

当我们要计算相当多的数字(可能小于100)时，快速排序或合并中涉及的递归可能会耗费大量资源

在这种情况下，插入排序的性能要好得多。

甚至Java中的排序库的标准实现也混合使用了快速合并和插入排序

HTH

Answer 3

有稳定的排序算法，可以保持比较相等的项目按原始顺序排列。如果这对你很重要，那么你会使用一个稳定的排序算法，即使速度较慢。

在某些情况下，更简单的算法更快(因为显然，如果没有其他优点，速度较慢的算法永远不会更有用)。

我见过这样一种情况:对一个数组进行排序，然后对每个数组元素进行少量的修改。因此，大多数物品都放在了正确的位置，只有少数物品需要更换。在这种情况下，shakersort被证明是最优的。

如果你知道数组被排序了，然后有一小部分项被改变了，有一个聪明的算法(你可以在cs.stackexchange.com上的某个地方找到)：如果k个项被改变了，你最多可以将2k个项提取到一个单独的数组中，排序(很可能使用快速排序)并合并这两个数组。

如果你使用库函数，它不太可能是简单的快速排序。例如，Apple的实现在数组的开始和结束处查找已排序的范围，如果有大量已排序的项，则利用这一点(例如，排序两个已排序数组的连接在线性时间内运行)。