插入排序对于少量元素的排序是很高效的，而且这个排序的手法在每个人生活中也是有的哦。
你可能没有意识到，当你打牌的时候，就是用的插入排序。
概念
从桌上的牌堆摸牌，牌堆内是杂乱无序的，但是我们摸上牌的时候，却会边摸边排序，借用一张算法导论的图。
摸牌时，对牌进行排序
每次我们从牌堆摸起一张牌，然后将这张牌插入我们左手捏的手牌里面，在插入手牌之前，我们会自动计算将牌插入什么位置，然后将牌插入到这个计算后的位置，虽然这个计算转瞬而过，但我们还是尝试分析一下这个过程：
- 我决定摸起牌后，最小的牌放在左边，摸完后，牌面是从左到右依次增大
- 摸起第1张牌，直接捏在手里，现在还不用排序
- 摸起第2张牌，查看牌面大小，如果第二张牌比第一张牌大，就放在右边
- 摸起第3张牌，从右至左开始计算，先看右边的牌，如果摸的牌比最右边的小，那再从右至左看下一张，如果仍然小，继续顺延，直到找到正确位置（循环）
- 摸完所有的牌，结束
所以我们摸完牌，牌就已经排完序了。
讲起来有点拗口，但是你在打牌的时候绝对不会觉得这种排序算法会让你头疼。
这就是传说中的插入排序。
想象一下，假如我们认为左手拿的牌和桌面的牌堆就是同一数组，当我们摸完牌以后，我们就完成了对这个数组的排序。
示例
插入排序过程
上图就是插入排序的过程，我们把它想象成摸牌的过程。
格子上方的数字：表示格子的序号，图(a)中，1号格子内的数字是5，2号格子是2，3号格子是4，以此类推
灰色格子：我们手上已经摸到的牌
黑色格子：我们刚刚摸起来的牌
白色格子：桌面上牌堆的牌
- 图(a)，我们先摸起来一张5，然后摸起来第二张2,发现2比5小，于是将5放到2号格子，2放到1号格子（简单的人话：将2插到5前面）
- 图(b)，摸起来一张4，比较4和2号格子内的数字5，4比5小，于是将5放到3号格子，再比较4和1号格子内的2，4大于2，4小于5，于是这就找到了正确的位置。（说人话：就是摸了张4点，将4和5交换位置）
- 图(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-插入排序
非常的简单吧，其他语言的写法也都简单，不再赘述。
网友评论