目標：從小到大（或從大到信车住）對數(shù)組進行排序。
給你一組數(shù)組笙蒙，將他們排序。插入排序算法的步驟如下：
把未排序的數(shù)字放在一堆庆锦。
從這堆數(shù)字里面挑一個捅位。選哪個并不重要，但從頂部拿最容易。
將選出來的數(shù)字插入新數(shù)組中艇搀。
從未排序的數(shù)字堆中挑一個數(shù)字尿扯，并將其插入新數(shù)組。 在您選擇的第一個數(shù)字之前或之后焰雕，將這兩個數(shù)字排序衷笋。
再選擇一個數(shù)字，并按順序插入到數(shù)組中適當?shù)奈恢谩?/p>
重復(fù)這樣做矩屁，直到堆里沒有數(shù)字辟宗。 你最終得到一個空堆和一個排序的數(shù)組。
這就是為什么這被稱為“插入”排序吝秕，因為你從堆中取一個數(shù)字泊脐，并將其插入在數(shù)組里正確的排序位置。
舉個栗子
未排序的數(shù)字堆是 [ 8, 3, 5, 4, 6 ] 容客。
選擇第一個數(shù)字 8 ，并將其插入新數(shù)組约郁。 新數(shù)組是空的缩挑，所以很容易。 排序的數(shù)組現(xiàn)在是 [8] 鬓梅，未排序的堆是 [ 3, 5, 4, 6 ] 供置。
從堆中選擇下一個數(shù)字 3 ，并將其插入到排序的數(shù)組中己肮。 它應(yīng)該在8之前士袄，所以排序的數(shù)組現(xiàn)在 [ 3, 8 ] ，堆是 [ 5, 4, 6 ] 谎僻。
從堆中選擇下一個數(shù)字5娄柳，并將其插入到排序的數(shù)組中。 它在3和8之間艘绍。排序的數(shù)組是 [ 3, 5, 8 ] 赤拒，堆是 [ 4, 6 ] 。
重復(fù)此過程诱鞠，直到堆是空的挎挖。
在一個數(shù)組中排序
上面的解釋會你看起來需要兩個數(shù)組：一個用于未排序的數(shù)組，一個排序好的數(shù)組航夺。
但是你可以在一個數(shù)組里執(zhí)行插入排序蕉朵，而無需創(chuàng)建新的數(shù)組。 你只需知道數(shù)組的哪個部分已經(jīng)排序阳掐，哪個部分是未排序的堆始衅。
最初冷蚂，數(shù)組是 [ 8, 3, 5, 4, 6 ] 。用 | 區(qū)別排序部分和未排序部分：
[| 8, 3, 5, 4, 6 ]
這表示排序部分是空的汛闸，未排序的數(shù)字堆從8開始蝙茶。
處理完第一個數(shù)字后，是這樣的：
[ 8 | 3, 5, 4, 6 ]
排序部分是 [ 8 ] 诸老，堆是 [ 3, 5, 4, 6 ] 隆夯。 | 已經(jīng)向右移位了一位。
這是數(shù)組的排序過程：
[| 8, 3, 5, 4, 6 ]
[ 8 | 3, 5, 4, 6 ]
[ 3, 8 | 5, 4, 6 ]
[ 3, 5, 8 | 4, 6 ]
[ 3, 4, 5, 8 | 6 ]
[ 3, 4, 5, 6, 8 |]
在每個步驟中别伏，| 從數(shù)組的開頭蹄衷，一下一下的向后移動，直到排序完成時到達數(shù)組的結(jié)尾畸肆。 數(shù)字堆一個個縮小宦芦，并且排序部分一個個增加，直到數(shù)字堆是空的轴脐，并且所有數(shù)字都排序完成调卑。
怎樣插入？
每個步驟大咱，都要從未排序的堆中選擇最頂層的數(shù)字恬涧，并將其插入排序數(shù)組。 您必須把數(shù)字放在合適的位置碴巾，保證數(shù)組是排序好的溯捆。 怎樣做呢？
我們假設(shè)已經(jīng)做了幾步厦瓢，數(shù)組看起來像這樣：
[ 3, 5, 8 | 4, 6 ]
下一個要排序的數(shù)字是 4 提揍，排序好的部分是 [ 3, 5, 8 ] 。
用這種方法：看看上一個元素 8 煮仇。
[ 3, 5, 8, 4 | 6 ]
^
8 是否大于 4 劳跃？ 是的，所以 4 應(yīng)該在 8 之前浙垫。我們交換這兩個數(shù)字得到：
[ 3, 5, 4, 8 | 6 ]
<-->
交換
還沒完刨仑。 新的前一個元素 5 也大于 4 。我們還交換這兩個數(shù)字：
[ 3, 4, 5, 8 | 6 ]
<-->
交換
再看看前面的元素夹姥。 3 大于 4 嗎杉武？ 不是。 這意味著我們完成了 4 在數(shù)組中的排序辙售。
這是插入排序算法轻抱，您將在下一節(jié)中看到內(nèi)部循環(huán)的描述部分：通過交換數(shù)字將從堆的頂部的數(shù)字插入到排序的部分。
代碼
這是用 Swift 實現(xiàn)的插入排序：
func insertionSort(_ array: [Int]) -> [Int] {
var a = array // 1
for x in 1..<a.count { // 2
var y = x
while y > 0 && a[y] < a[y - 1] { // 3
swap(&a[y - 1], &a[y])
y -= 1
}
}
return a
}
把這段代碼放到 playground 里測試：
let list = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]
insertionSort(list)
注釋對應(yīng)的代碼分析：
創(chuàng)建數(shù)組的副本旦部。這是必要的十拣，因為我們不能直接修改參數(shù)
array的內(nèi)容封拧。 像Swift 中的sort()一樣，insertionSort()函數(shù)將返回原始數(shù)組的副本夭问，并將它排序。這個函數(shù)里有兩個循環(huán)：外部循環(huán)遍歷數(shù)組中的每個元素曹铃，從數(shù)字堆的最頂端挑選數(shù)字缰趋；變量
x是排序區(qū)分排序不分與數(shù)字堆的索引（相當于|的作用）。請記住陕见，任何時候秘血，array[0]到array[x]都是排序完成的。從array[x]到結(jié)束评甜，是未排序的數(shù)字堆灰粮。循環(huán)查看
array[x]，這是在數(shù)字堆中頂部的數(shù)組忍坷，它可能小于排序數(shù)組的任何元素粘舟。循環(huán)排序好的數(shù)組，每次往前找一個佩研，如果前面的更大柑肴，就交換它們。當循環(huán)完成時旬薯，排序好的數(shù)組就增長了一個元素晰骑。
注意：外循環(huán)從（注釋2處）索引從1開始，將第一個元素從數(shù)字堆中移動到排序部分并不會改變?nèi)魏蝺?nèi)容绊序，所以我們可以跳過它硕舆。
減少交換
上面的插入排序雖然能使用，但是如果能刪除 swap() 方法會運行的更快骤公。
您已經(jīng)看到抚官，我們交換數(shù)字，將下一個元素根據(jù)排序移動到合適的位置：
[ 3, 5, 8, 4 | 6 ]
<-->
swap
[ 3, 5, 4, 8 | 6 ]
<-->
swap
我們可以不交換淋样，將數(shù)字向右移動耗式，然后把新數(shù)字放到合適的位置就可以了。
[ 3, 5, 8, 4 | 6 ] 復(fù)制 4
*
[ 3, 5, 8, 8 | 6 ] 將 8 向右移動
--->
[ 3, 5, 5, 8 | 6 ] 將 5 向右移動
--->
[ 3, 4, 5, 8 | 6 ] 把 4 粘貼到合適的位置
*
代碼：
func insertionSort(_ array: [Int]) -> [Int] {
var a = array
for x in 1..<a.count {
var y = x
let temp = a[y]
while y > 0 && temp < a[y - 1] {
a[y] = a[y - 1] // 1
y -= 1
}
a[y] = temp // 2
}
return a
}
// 1 處是將數(shù)字向右移動一位趁猴。內(nèi)循環(huán)結(jié)束時刊咳，y 是排序數(shù)組中和新數(shù)字比較的索引。// 2 處是將新數(shù)字復(fù)制到對應(yīng)的位置儡司。
給其他類型排序
我們可以給其他類型排序娱挨，添加泛型并提供比較函數(shù)即可。只需要修改兩處代碼捕犬。
方法定義變?yōu)椋?/p>
func insertionSort<T>(_ array: [T], _ isOrderedBefore: (T, T) -> Bool) -> [T] {
數(shù)組具有泛型 [T]跷坝，現(xiàn)在 isOrderedBefore() 方法將接受任何類型酵镜，無論是數(shù)組，字符串柴钻，或是其他類型淮韭。
新的參數(shù) isOrderedBefore: (T, T) -> Bool 是一個方法 ，接受兩個 T 類型的對象贴届，如果兩個參數(shù)比較厚滿足這個表達式靠粪，返回 true，不滿足則返回 false毫蚓。就像是 Swift 內(nèi)置的 sort() 方法占键。
另一個改動的地方是在內(nèi)循環(huán)：
while y > 0 && isOrderedBefore(temp, a[y - 1]) {
將 temp < a[y - 1] 替換為 isOrderedBefore() 方法。它做了同樣的事情元潘，并且可以比較任何類型畔乙。
在 Playground 中測試：
let numbers = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]
insertionSort(numbers, <)
insertionSort(numbers, >)
< 和 > 決定排序順序，分別是從小到大和從大到小翩概。
當然牲距，你也可以排序其他類型，如字符串：
let strings = [ "b", "a", "d", "c", "e" ]
insertionSort(strings, <)
甚至是更復(fù)雜的對象：
let objects = [ obj1, obj2, obj3, ... ]
insertionSort(objects) { $0.priority < $1.priority }
閉包是告訴 insertionSort() 根據(jù)對象的屬性 priority 進行排序氮帐。
插入排序是一種穩(wěn)定的排序嗅虏。對于都具有排序鍵的元素，是相對穩(wěn)定的上沐。這對于簡單的數(shù)字或字符串不重要 皮服，但對于復(fù)雜對象就非常重要了。在上面的例子中参咙，兩個對象的 priority 一樣的話龄广，就不會交換，不管其他屬性的值多大多小蕴侧。
性能
如果數(shù)組已經(jīng)排序择同，那插入排序真的很快。這聽起來很明顯净宵，但不是所有的排序算法都能做到敲才。在實踐中，如果是大量數(shù)據(jù)并不完全排序择葡，插入排序會表現(xiàn)的很好紧武。
最壞情況下插入排序的平均情況性能是 O(n ^ 2) 。 這是因為在這個函數(shù)中有兩個嵌套循環(huán)敏储。 其他排序算法（如快速排序和合并排序）的性能是 O(n log n)阻星，在數(shù)據(jù)量較大時更快。
插入排序?qū)嶋H上對排序小數(shù)組非骋烟恚快妥箕。 當元素個數(shù)為10或更小需要排序的時候滥酥，一些標準庫會把它們的排序方法從快速排序切換到插入排序。
我做了一個簡單的測試比較我們的 insertionSort() 與 Swift 的內(nèi)置 sort() 畦幢。 在大約100個元素左右的數(shù)組上坎吻，速度的差異很小。 然而呛讲，隨著個數(shù)增加禾怠，O(n ^ 2) 很快開始執(zhí)行比 O(n log n) 差很多，并且插入排序不能跟上贝搁。
作者：Matthijs Hollemans -- Swift 算法俱樂部
英文鏈接：
https://github.com/raywenderlich/swift-algorithm-club/tree/master/Insertion%20Sort
