接下來就到插入排序了。我前面寫了關于交換排序的算法，連結位址：
冒泡排序 快速排序 雞尾酒排序插入排序
插入排序是比較簡單也比較直接的一種排序算法。它是從一堆資料中取出一個資料并将它插入到已排序的資料中合适的位置。
比如按身高排隊，有一個人指揮排隊從第二個人開始，按身高把目前的人安插到之前排序好隊的合适的位置。
或者打撲克牌，假設我們拿到了10，J，K，A這四張牌，然後拿到了Q這張牌，那如何讓手中的五張牌變為升序呢？如果我們隻學了冒泡排序和快速排序，初始狀态是10，J，K，A，Q。
如果是用冒泡排序或者快速排序去做的話，那就可能不合适。結果是對，但是浪費了很多比較次數。
正常人最簡單的方式就是，把Q安插到J和K之間就可以了。
插入排序正是如此，它的思想就是維護一個有序區，把元素一個一個插入到有序區中的合适的位置，直到所有元素有序為止。
視訊動畫
Code
Result
優化減少不必要的交換
回顧一下上面代碼運作的結果，發現有很多次的交換，會有一點一點的時間上的消耗。如果我們做減少交換次數的代碼，那如何去寫呢？
回顧一下快速排序那篇文章，也使用了減少交換次數的方法。它是一個一個待比較完之後，定位最大的元素或者最小的元素，然後進行交換。
插入排序把待插入的元素做一個标記，和有序區一個一個元素去做比較。假設是從待插入元素的鄰近元素開始比較（從後往前），符合條件的前一個元素去複制粘貼到待插入元素的位址。直到不符合條件才插入到合适的位置。
-----End-----
來源 | 算法無遺策
作者 | 我脫下短袖