(原创)算法一插入排序

请尊重作者的劳动成果,如需转载请注明出处,谢谢！

如果觉得不错,可以关注我或者点赞,这就是你们对我最大的鼓励！

相信大家都打过斗地主,当我们拿到牌的时候的时候,我们将牌打顺的过程就很像插入排序。我们将每一张牌插入其他已经有序的牌中的恰当的位置。

在选择排序中,我们说到,选择排序每一次遍历数组不能给下次遍历数组提供信息,并且使用选择排序给已经排序好的数组和乱序的数组进行排序时间是相同的。

插入排序每次遍历都能让下次遍历更快。对部分有序的数组进行排序所需要的时间比随机顺序的数组快很多。

插入排序对上图排序的实现思路是:

第一步,比较第二张牌与第一张牌的大小。我们可以看到, 1 比 8 小。 

于是进行第二步,将第二张牌与第一张牌交换位置。

得到下图

接下来看到第三张牌,同样的

第一步,比较第三张牌与第二张牌的大小。 4  比 8 小

于是进行第二步,将打三张牌与第二张牌交换位置。

得到下图

此时,比较第二张牌与第一张牌的大小。 4 不比 1 小。因此第二张牌不需要与第一张牌交换。

我们把这种排序方法称为插入排序。

用C语言表示如下

插入排序是一种较为简单的算法,并且效率比选择排序高。当数组大部分有序时,插入排序非常非常快,比很多复杂的算法都快。比如我们将要学习的希尔排序

一般情况下,即数组是随机顺序,并且数组规模较大时,我们可以发现,若是每次都交换相邻的元素,在数组末尾的较小的元素需要非常长的时间才能插入正确的位置。要是我们能够减少数组末尾元素移动交换的次数,那么算法将会更高效。希尔排序的思想就是如此。