InsertionSort和大型数据集[O(n平方公里)]

Question

在研究一些基本的排序算法时，我注意到文献中总是说，对于大数据集，任何n阶排序算法或多或少都是不切实际的，甚至是不合适的。

嗯，这似乎是合理的，因为每次输入数据加倍，该算法的运行时间就会增加四倍。但是..。当要处理的数据集太大时，边框在哪里？这个问题有什么一般性的答案吗？

Answer 1

人们普遍认为，对于超过10-20个元素的任何元素，您都会使用更高效的排序算法，如快速排序或合并排序。

没有一个比另一个更快的确切点，因为它取决于您正在使用的机器的数据和规格。

而且，这可能需要一段时间，但是没有什么可以阻止您使用插入排序来排序几个兆字节的数据。

Answer 2

在小数据集上，InsertionSort算法比快速线性化算法更有效。我在教科书中看到的建议只有10到20，但Tim被认为非常有效，它是合并和插入排序的混合体。如果我没记错的话，它使用的数据设置为63个元素，用于插入可排序的部件。

编辑:您可以找到关于在维基百科的更多信息。

Tim仅在63个元素或更小的数据集中使用插入排序。对于较大的数据集，它插入大小为32-64的排序范围并合并这些数据集。

但是，有时您只需要尝试不同的技术并测量结果，或者您可能受到可用的数据结构的限制。如果你以毫秒标度来衡量，你会发现时间上的差异已经在20到100项左右，但它可能不会被用户察觉。通常，您已经在高级语言标准库中为您实现了快速排序算法。