是否有过使用插入排序的好理由？ [英] Is there ever a good reason to use Insertion Sort?

问题描述

有关通用排序，答案似乎是否定的，因为快速排序，归并排序和堆排序往往在平均 - 和最坏的情况下有更好的表现。然而，插入排序出现练成增量的排序，即，在延长的时间期间将元素添加到一个列表中的一个在一个时间同时保持排序的列表，特别是如果插入排序被实现为一个链接列表（O（日志n）的平均情况与为O（n））。然而，一个堆似乎是能够执行只（或接近），以及为增量的排序（从一个堆添加或删除一个单个元件具有为O最坏的情况下（log n）的）。那么究竟是什么插入排序必须提供比其他基于比较的排序算法或堆？

For general-purpose sorting, the answer appears to be no, as quick sort, merge sort and heap sort tend to perform better in the average- and worst-case scenarios. However, insertion sort appears to excel at incremental sorting, that is, adding elements to a list one at a time over an extended period of time while keeping the list sorted, especially if the insertion sort is implemented as a linked list (O(log n) average case vs. O(n)). However, a heap seems to be able to perform just (or nearly) as well for incremental sorting (adding or removing a single element from a heap has a worst-case scenario of O(log n)). So what exactly does insertion sort have to offer over other comparison-based sorting algorithms or heaps?

推荐答案

从<一个href="http://www.sorting-algorithms.com/insertion-sort">http://www.sorting-algorithms.com/insertion-sort:

虽然它是基本的排序算法与一个   O（N2），最坏情况下的时间，插入排序   是选择的算法要么当   数据被近排序（因为它   是自适应的），或当该问题的大小   小（因为它具有低   开销）。

Although it is one of the elementary sorting algorithms with O(n2) worst-case time, insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead).

有关这些原因，并且因为它也是稳定的，插入排序就是   经常用作递归基本情况   （当问题规模小）的   更高的开销分而治之   排序算法，比如归并排序   或快速排序。

For these reasons, and because it is also stable, insertion sort is often used as the recursive base case (when the problem size is small) for higher overhead divide-and-conquer sorting algorithms, such as merge sort or quick sort.

这篇关于是否有过使用插入排序的好理由？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！