Sex*_*ast 6 sorting algorithm mergesort quicksort divide-and-conquer
我已阅读无处不在,对于分而治之的排序算法像Merge-Sort和Quicksort,而不是递归,直到只有一个元素是左,这是更好地转移到Insertion-Sort时候一定阈值,比如30元,达到.那很好,但为什么只有Insertion-Sort？为什么不,Bubble-Sort或Selection-Sort两者都有类似的O(N^2)表现？Insertion-Sort只有当许多元素被预先排序时才应该派上用场(虽然这个优势也应该附带Bubble-Sort),但除此之外,为什么它应该比其他两个元素更有效？
其次,在这个链接中,在第二个答案及其附带的评论中,它表示O(N log N)与O(N^2)最高级别相比表现不佳N.怎么会？N^2应该总是表现得比N log N,因为N > log N对于所有N> = 2,对吧？
Ste*_*sop 11
如果你击中Quidsort的每一个分支,当它达到阈值时,你的数据看起来像这样:
[the least 30-ish elements, not in order] [the next 30-ish ] ... [last 30-ish]
插入排序具有相当令人满意的属性,您可以在整个数组上只调用一次,并且它的执行方式与每次为30的每个块调用一次时的执行方式基本相同.因此,不要在循环中调用它,而是最后调用它的选项.这可能不会更快,特别是因为它将整个数据通过缓存拉出额外的时间,但取决于代码的结构,它可能很方便.
冒泡排序和选择排序都没有这个属性,所以我认为答案可能很简单就是"方便".如果有人怀疑选择排序可能会更好,那么举证责任在于他们"证明"它更快.
请注意,这种插入排序的使用也有一个缺点 - 如果你这样做并且你的分区代码中有一个错误,那么它不会丢失任何元素,只是错误地对它们进行分区,你永远不会注意到.
编辑:显然这个修改是由Sedgewick在1975年在QuickSort上写下他的博士.最近由Musser(Introsort的发明者)进行了分析.参考https://en.wikipedia.org/wiki/Introsort
Musser还考虑了Sedgewick延迟小排序对缓存的影响,其中小范围在插入排序的单个传递中最后排序.他报告说,它可以使缓存未命中数增加一倍,但是它的双端队列性能明显更好,应该保留给模板库,部分原因是因为其他情况下立即进行排序的收益并不大.
无论如何,我不认为一般的建议是"无论你做什么,不要使用选择排序".建议是,"插入排序将Quicksort输入到令人惊讶的非小尺寸",当你实现Quicksort时,这很容易向自己证明.如果你想出另一种在同一个小阵列上明显优于插入排序的那种,那些学术资源都没有告诉你不要使用它.我认为令人惊讶的是,建议始终是插入排序,而不是每个消息来源选择自己喜欢的(介绍性教师对泡沫排序有一种坦率的惊人喜好 - 我不介意,如果我再也听不到它).插入排序通常被认为是小数据的"正确答案".问题不在于它是否应该"快速",而是它是否真的存在,而且我从未特别注意到任何消除这一想法的基准.
寻找此类数据的一个地方是Timsort的开发和采用.我很确定蒂姆·彼得斯选择插入是有原因的:他没有提供一般建议,他正在优化图书馆以供实际使用.