插入排序是“小”数据集的一个很好的选择。什么是“小”？

Question

我见过很多地方，它谈到插入排序对小数据集有什么好处。不过，我找不到“小”的数字。我的猜测是，没有绝对答案，这取决于运行代码的机器的类型。

然而，当插入排序是一个好主意时，哪些因素会决定什么是阈值？“小”的大概数字是多少? 5? 10? 50? 100？

谢谢!

站点说插入排序对小数据集很好：https://www.toptal.com/developers/sorting-algorithms/insertion-sort

Answer 1

是的，你的猜测是正确的-没有绝对的答案，我们必须测量插入排序和其他方法之间的阈值在哪里。

例如，对于组合合并或快速排序中的小块，触发插入排序的典型值(当然还有一些增益)约为32-100 (但取决于数据和实现细节)。

Answer 2

如果我们讨论的是一般的排序问题的话，那就是试图给出一个答案。插入排序平均为O(n^2)，有效排序算法平均为O(nlogn)。因此，含糊地说，如果某事采取了K个步骤来有效地排序，那么插入排序就会执行(某种) K^2步骤。

因此，如果n>K对你来说太慢了，那么对于插入排序来说，n> K^0.5对你来说太慢了。

实际上，假设您乐于使用有效的方法对大小为10^8的数组进行排序，那么您可能很乐意使用插入排序对大小为10^4的数组进行排序。