为什么要插入排序的合并排序门槛交叉后使用 [英] Why should Insertion Sort be used after threshold crossover in Merge Sort

问题描述

我已阅读无处不在，对于分而治之的排序算法，如合并排序的和快速排序，而不是递归直到只有一个元素被留​​下，这是更好地转移到插入分页当达到一定阈值时，说30元，就达到了。这是好的，但为什么只有插入分页？为什么不冒泡排序或选择分页，两者有相似的 O（N ^ 2）性能？ 插入分页应该派上用场，只有当许多元素都是pre-排序（虽然这种优势也应该有冒泡排序），否则，为什么会是比其他两种更有效？

其次，在<一个href="http://stackoverflow.com/questions/8101546/why-is-insertion-sort-better-than-quick-sort-for-small-list-of-elements">this链接，在第2个答案，与之配套的评论，它说， O（N日志N）进行比较不佳O（N ^ 2）高达一定 N 。怎么来的？ N ^ 2 应该总是表现得比糟糕ñ日志N ，因为 N'GT;日志N 所有N> = 2，对吧？

解决方案

1. 插入在实践中排序更快，比冒泡最少。其渐近运行时间是一样的，但插入排序具有更好的常数（更少/更便宜每次迭代操作）。最值得注意的是，它需要对元件的互换仅一个线性编号，并且在每个内环它执行的每一个之间的比较的 N 的/ 2个元素，并且可以在一个存储一个固定元素注册（而冒泡排序已经从内存中读取值）。即插入排序确实在比冒泡排序内环少的工作。
2. 在回答称，10000的 N 的LG的 N 的> 10 N 的²为合理的 N 的。这是真实的至多约14000的元件。

I have read everywhere that for divide and conquer sorting algorithms like Merge-Sort and Quicksort, instead of recursing until only a single element is left, it is better to shift to Insertion-Sort when a certain threshold, say 30 elements, is reached. That is fine, but why only Insertion-Sort? Why not Bubble-Sort or Selection-Sort, both of which has similar O(N^2) performance? Insertion-Sort should come handy only when many elements are pre-sorted (although that advantage should also come with Bubble-Sort), but otherwise, why should it be more efficient than the other two?

And secondly, at this link, in the 2nd answer and its accompanying comments, it says that O(N log N) performs poorly compared to O(N^2) upto a certain N. How come? N^2 should always perform worse than N log N, since N > log N for all N >= 2, right?

解决方案

1. Insertion sort is faster in practice, than bubblesort at least. Their asympotic running time is the same, but insertion sort has better constants (fewer/cheaper operations per iteration). Most notably, it requires only a linear number of swaps of pairs of elements, and in each inner loop it performs comparisons between each of n/2 elements and a "fixed" element that can be stores in a register (while bubble sort has to read values from memory). I.e. insertion sort does less work in its inner loop than bubble sort.
2. The answer claims that 10000 n lg n > 10 n² for "reasonable" n. This is true up to about 14000 elements.

这篇关于为什么要插入排序的合并排序门槛交叉后使用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！