插入排序對于少量元素的排序是很高效的，而且這個排序的手法在每個人生活中也是有的哦。
你可能沒有意識到，當你打牌的時候，就是用的插入排序。
概念
從桌上的牌堆摸牌，牌堆內是雜亂無序的，但是我們摸上牌的時候，卻會邊摸邊排序，借用一張算法導論的圖。
摸牌時，對牌進行排序
每次我們從牌堆摸起一張牌，然后將這張牌插入我們左手捏的手牌里面，在插入手牌之前，我們會自動計算將牌插入什么位置，然后將牌插入到這個計算后的位置，雖然這個計算轉瞬而過，但我們還是嘗試分析一下這個過程：
- 我決定摸起牌后，最小的牌放在左邊，摸完后，牌面是從左到右依次增大
- 摸起第1張牌，直接捏在手里，現在還不用排序
- 摸起第2張牌，查看牌面大小，如果第二張牌比第一張牌大，就放在右邊
- 摸起第3張牌，從右至左開始計算，先看右邊的牌，如果摸的牌比最右邊的小，那再從右至左看下一張，如果仍然小，繼續(xù)順延，直到找到正確位置（循環(huán)）
- 摸完所有的牌，結束
所以我們摸完牌，牌就已經排完序了。
講起來有點拗口，但是你在打牌的時候絕對不會覺得這種排序算法會讓你頭疼。
這就是傳說中的插入排序。
想象一下，假如我們認為左手拿的牌和桌面的牌堆就是同一數組，當我們摸完牌以后，我們就完成了對這個數組的排序。
示例
插入排序過程
上圖就是插入排序的過程，我們把它想象成摸牌的過程。
格子上方的數字：表示格子的序號，圖(a)中，1號格子內的數字是5，2號格子是2，3號格子是4，以此類推
灰色格子：我們手上已經摸到的牌
黑色格子：我們剛剛摸起來的牌
白色格子：桌面上牌堆的牌
- 圖(a)，我們先摸起來一張5，然后摸起來第二張2,發(fā)現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-插入排序
非常的簡單吧，其他語言的寫法也都簡單，不再贅述。
