对于 "small" 数据集，插入排序是一个不错的选择。什么是 "small"？
Insertion Sort is a good choice for "small" data sets. What is "small"?
我看到很多地方都在谈论插入排序如何适用于小型数据集。不过，我找不到 "small" 的数字。我的猜测是，没有绝对的答案，这取决于运行代码的机器类型 运行。
但是，什么因素决定了插入排序是一个好主意的阈值是多少？ "small" 的大概数字是多少？ 5？ 10？ 50？ 100？
谢谢！
网站说插入排序适用于小数据集：
https://www.toptal.com/developers/sorting-algorithms/insertion-sort
尝试回答，前提是我们讨论的是一般排序问题。插入排序平均为 O(n^2)，高效排序算法平均为 O(nlogn)。所以含糊地说，如果某件事需要 K 个步骤来有效地排序，那么插入排序将需要大约（大约）K^2 个步骤。
因此，如果 n > K 对于您喜欢的高效排序来说太慢了，那么 n > K^0.5 对于您来说（大致）对于插入排序来说太慢了。
实际上，假设您乐于使用高效的方法对大小为 10^8 的数组进行排序，那么您可能乐于使用插入排序对大小为 10^4 的数组进行排序。
是的，您的猜测是正确的 - 没有绝对的答案，必须衡量插入排序和其他方法之间的阈值在哪里。
例如，对于组合合并或快速排序中的小片段，触发插入排序（当然会获得一些收益）的典型值约为 32-100（但可能会因数据和实现细节而异）
我看到很多地方都在谈论插入排序如何适用于小型数据集。不过，我找不到 "small" 的数字。我的猜测是，没有绝对的答案，这取决于运行代码的机器类型 运行。
但是，什么因素决定了插入排序是一个好主意的阈值是多少？ "small" 的大概数字是多少？ 5？ 10？ 50？ 100？
谢谢！
网站说插入排序适用于小数据集： https://www.toptal.com/developers/sorting-algorithms/insertion-sort
尝试回答，前提是我们讨论的是一般排序问题。插入排序平均为 O(n^2)，高效排序算法平均为 O(nlogn)。所以含糊地说，如果某件事需要 K 个步骤来有效地排序，那么插入排序将需要大约（大约）K^2 个步骤。
因此，如果 n > K 对于您喜欢的高效排序来说太慢了，那么 n > K^0.5 对于您来说（大致）对于插入排序来说太慢了。
实际上，假设您乐于使用高效的方法对大小为 10^8 的数组进行排序，那么您可能乐于使用插入排序对大小为 10^4 的数组进行排序。
是的，您的猜测是正确的 - 没有绝对的答案，必须衡量插入排序和其他方法之间的阈值在哪里。
例如，对于组合合并或快速排序中的小片段，触发插入排序（当然会获得一些收益）的典型值约为 32-100（但可能会因数据和实现细节而异）