排序算法 – 插入排序(Insertion sort)

插入排序对于少量元素的排序是很高效的,而且这个排序的手法在每个人生活中也是有的哦。
你可能没有意识到,当你打牌的时候,就是用的插入排序。

概念

从桌上的牌堆摸牌,牌堆内是杂乱无序的,但是我们摸上牌的时候,却会边摸边排序,借用一张算法导论的图。

每次我们从牌堆摸起一张牌,然后将这张牌插入我们左手捏的手牌里面,在插入手牌之前,我们会自动计算将牌插入什么位置,然后将牌插入到这个计算后的位置,虽然这个计算转瞬而过,但我们还是尝试分析一下这个过程:
1. 我决定摸起牌后,最小的牌放在左边,摸完后,牌面是从左到右依次增大
2. 摸起第1张牌,直接捏在手里,现在还不用排序
3. 摸起第2张牌,查看牌面大小,如果第二张牌比第一张牌大,就放在右边
4. 摸起第3张牌,从右至左开始计算,先看右边的牌,如果摸的牌比最右边的小,那再从右至左看下一张,如果仍然小,继续顺延,直到找到正确位置(循环)
5. 摸完所有的牌,结束
所以我们摸完牌,牌就已经排完序了。
讲起来有点拗口,但是你在打牌的时候绝对不会觉得这种排序算法会让你头疼。
这就是传说中的插入排序。

想象一下,假如我们认为左手拿的牌和桌面的牌堆就是同一数组,当我们摸完牌以后,我们就完成了对这个数组的排序。

示例


上图就是插入排序的过程,我们把它想象成摸牌的过程。
格子上方的数字:表示格子的序号,图(a)中,1号格子内的数字是5,2号格子是2,3号格子是4,以此类推
灰色格子:我们手上已经摸到的牌
黑色格子:我们刚刚摸起来的牌
白色格子:桌面上牌堆的牌
1. 图(a),我们先摸起来一张5,然后摸起来第二张2,发现25小,于是将5放到2号格子,2放到1号格子(简单的人话:将2插到5前面)
2. 图(b),摸起来一张4,比较4和2号格子内的数字545小,于是将5放到3号格子,再比较4和1号格子内的24大于24小于5,于是这就找到了正确的位置。(说人话:就是摸了张4点,将45交换位置)
3. 图(c)、图(d)、图(e)和图(f),全部依次类推,相信打牌的你能够看懂。
看到这里,我相信应该没人看不懂什么是插入排序了,那么插入排序的代码长什么模样:

Insertion Sort (seq)

// 从第2个元素开始
for j = 2 to seq.length
    key = seq[j]
    // 将seq[j]插入到已排序的seq[1..j-1]中
    i = j - 1
    while i > 0 and seq[i] > key
        seq[i + 1] = seq[i]
        i = i - 1
    seq[i + 1] = key

这就是传说中的插入排序的模板了,拿一种语言来套用吧。

Python版

def sort(seq):
    for j in range(1, len(seq)):
        key = seq[j]
        i = j - 1
        while i >= 0 and seq[i] > key:
            seq[i + 1] = seq[i]
            i = i - 1
        seq[i + 1] = key
    return seq

Python源码:Github-Syler-Fun-插入排序

Java版

public static void sort(int[] seq) {
    for (int i, j = 1; j < seq.length; j++) {
        int key = seq[j];
        i = j - 1;
        while (i > 0 && seq[i] > key) {
            seq[i + 1] = seq[i];
            i = i - 1;
        }
        seq[i + 1] = key;
    }
}

Java源码:Github-Syler-Fun-插入排序
非常的简单吧,其他语言的写法也都简单,不再赘述。

发表评论

电子邮件地址不会被公开。 必填项已用*标注