插入排序?qū)τ谏倭吭氐呐判蚴呛芨咝У?，而且這個(gè)排序的手法在每個(gè)人生活中也是有的哦。
你可能沒(méi)有意識(shí)到，當(dāng)你打牌的時(shí)候，就是用的插入排序。
概念
從桌上的牌堆摸牌，牌堆內(nèi)是雜亂無(wú)序的，但是我們摸上牌的時(shí)候，卻會(huì)邊摸邊排序，借用一張算法導(dǎo)論的圖。
摸牌時(shí)，對(duì)牌進(jìn)行排序
每次我們從牌堆摸起一張牌，然后將這張牌插入我們左手捏的手牌里面，在插入手牌之前，我們會(huì)自動(dòng)計(jì)算將牌插入什么位置，然后將牌插入到這個(gè)計(jì)算后的位置，雖然這個(gè)計(jì)算轉(zhuǎn)瞬而過(guò)，但我們還是嘗試分析一下這個(gè)過(guò)程：
- 我決定摸起牌后，最小的牌放在左邊，摸完后，牌面是從左到右依次增大
- 摸起第1張牌，直接捏在手里，現(xiàn)在還不用排序
- 摸起第2張牌，查看牌面大小，如果第二張牌比第一張牌大，就放在右邊
- 摸起第3張牌，從右至左開(kāi)始計(jì)算，先看右邊的牌，如果摸的牌比最右邊的小，那再?gòu)挠抑磷罂聪乱粡?，如果仍然小，繼續(xù)順延，直到找到正確位置（循環(huán)）
- 摸完所有的牌，結(jié)束
所以我們摸完牌，牌就已經(jīng)排完序了。
講起來(lái)有點(diǎn)拗口，但是你在打牌的時(shí)候絕對(duì)不會(huì)覺(jué)得這種排序算法會(huì)讓你頭疼。
這就是傳說(shuō)中的插入排序。
想象一下，假如我們認(rèn)為左手拿的牌和桌面的牌堆就是同一數(shù)組，當(dāng)我們摸完牌以后，我們就完成了對(duì)這個(gè)數(shù)組的排序。
示例
插入排序過(guò)程
上圖就是插入排序的過(guò)程，我們把它想象成摸牌的過(guò)程。
格子上方的數(shù)字：表示格子的序號(hào)，圖(a)中，1號(hào)格子內(nèi)的數(shù)字是5，2號(hào)格子是2，3號(hào)格子是4，以此類推
灰色格子：我們手上已經(jīng)摸到的牌
黑色格子：我們剛剛摸起來(lái)的牌
白色格子：桌面上牌堆的牌
- 圖(a)，我們先摸起來(lái)一張5，然后摸起來(lái)第二張2,發(fā)現(xiàn)2比5小，于是將5放到2號(hào)格子，2放到1號(hào)格子（簡(jiǎn)單的人話：將2插到5前面）
- 圖(b)，摸起來(lái)一張4，比較4和2號(hào)格子內(nèi)的數(shù)字5，4比5小，于是將5放到3號(hào)格子，再比較4和1號(hào)格子內(nèi)的2，4大于2，4小于5，于是這就找到了正確的位置。（說(shuō)人話：就是摸了張4點(diǎn)，將4和5交換位置）
- 圖(c)、圖(d)、圖(e)和圖(f)，全部依次類推，相信打牌的你能夠看懂。
看到這里，我相信應(yīng)該沒(méi)人看不懂什么是插入排序了，那么插入排序的代碼長(zhǎng)什么模樣：
Insertion Sort (seq)
// 從第2個(gè)元素開(kāi)始
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
這就是傳說(shuō)中的插入排序的模板了，拿一種語(yǔ)言來(lái)套用吧。
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-插入排序
非常的簡(jiǎn)單吧，其他語(yǔ)言的寫法也都簡(jiǎn)單，不再贅述。
