本文是對 Swift Algorithm Club 翻譯的一篇文章。
Swift Algorithm Club是 raywenderlich.com網(wǎng)站出品的用Swift實現(xiàn)算法和數(shù)據(jù)結(jié)構(gòu)的開源項目搀暑，目前在GitHub上有18000+???忙芒，我初略統(tǒng)計了一下根灯，大概有一百左右個的算法和數(shù)據(jù)結(jié)構(gòu)毕源，基本上常見的都包含了岸更，是iOSer學習算法和數(shù)據(jù)結(jié)構(gòu)不錯的資源醇疼。
?? andyRon/swift-algorithm-club-cn是我對Swift Algorithm Club硕并，邊學習邊翻譯的項目。歡迎有興趣學習算法和數(shù)據(jù)結(jié)構(gòu)秧荆，有時間的小伙伴一起參與翻譯鲤孵，歡迎issue，或者直接提交pull request辰如。
本文的翻譯原文和代碼可以查看??swift-algorithm-club-cn/Insertion Sort
目標：把數(shù)組從低到高（或從高到低）排序
您將獲得按正確的順序排列一系列數(shù)字普监。插入排序算法的工作原理如下:
- 把一系列數(shù)字放在一個未排序的堆里。
- 從堆中挑選一個數(shù)字。 你選擇哪一個并不重要凯正，但從堆頂挑選是最容易毙玻。
- 把這個數(shù)插入一個新的數(shù)組。
- 從未排序堆中再選擇一個數(shù)字廊散，并將其插入之前的數(shù)組中桑滩。 這個數(shù)字在第一個數(shù)字之前或之后，所以現(xiàn)在這兩個數(shù)字被排序允睹。
- 再從堆中選擇一個數(shù)字运准，并將其插入到數(shù)組中的正確排序位置。
- 繼續(xù)這樣做缭受，直到堆里沒有數(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ù)組中甘萧。 3應該在8之前，所以排序的數(shù)組現(xiàn)在是[3,8]讳嘱，而堆被縮減為[5,4,6]。
從堆中選擇下一個數(shù)字5酿愧，然后將其插入到已排序的數(shù)組中沥潭。 5介于3和8之間。 排序的數(shù)組是[3,5,8]嬉挡，堆是[4,6]钝鸽。
重復上面的過程直到堆為空。
原地排序
譯注：原地排序就是指在排序過程中不申請多余的存儲空間庞钢，只利用原來存儲待排數(shù)據(jù)的存儲空間進行比較和交換的數(shù)據(jù)排序拔恰。包括：希爾排序、冒泡排序基括、插入排序颜懊、選擇排序、堆排序、快速排序河爹。
上面的解釋使你看起來需要兩個數(shù)組：一個用于存放未排序的堆匠璧，另一個用于存放按次序排好的數(shù)字。
但您可以執(zhí)行原地插入排序咸这，而無需創(chuàng)建單獨的數(shù)組夷恍。 您只需追蹤數(shù)組的哪個部分已經(jīng)排序，哪個部分是未排序媳维。
最初酿雪，數(shù)組是[8,3,5,4,6]。 |條顯示已排序部分的結(jié)束位置和堆的開始位置：
[| 8, 3, 5, 4, 6 ]
這表明排序的部分是空的侄刽，堆開始于8指黎。
處理完第一個數(shù)字后，結(jié)果為：
[ 8 | 3, 5, 4, 6 ]
排好序的部分是[8]唠梨，未排序的堆是[ 3, 5, 4, 6 ]袋励。|條向右移動了一個位置。
下面是排序期間數(shù)組內(nèi)容的變化過程：
[| 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ù)組的開始到|部分總是排好序的蚁鳖。堆縮小一位置磺芭，排序部分增加一位置，直到堆變?yōu)榭盏淖砘瑳]有更多未排序的數(shù)字為止钾腺。
怎么插入
每一步，您從未排序堆中選擇最頂部的數(shù)字讥裤，并將其插入到數(shù)組的已排序部分放棒。 但必須將該數(shù)字插入適當?shù)奈恢茫员銛?shù)組的從頭開始保持排序己英。 這是如何運作的间螟？
假設我們已經(jīng)完成了前幾個元素，數(shù)組看起來像這樣：
[ 3, 5, 8 | 4, 6 ]
要排序的下一個數(shù)字是4损肛。 我們需要將它插入到已經(jīng)排好序的[3,5,8]中厢破。
一種方法是：查看前一個元素8。
[ 3, 5, 8, 4 | 6 ]
^
前一個元素比4大嗎治拿？ 是的摩泪，所以4應該在8之前。 我們交換這兩個數(shù)字得到：
[ 3, 5, 4, 8 | 6 ]
<-->
交換
還沒有完成劫谅。 新的前一個元素5也大于4见坑。 我們還需交換這兩個數(shù)字：
[ 3, 4, 5, 8 | 6 ]
<-->
交換
再看一下前面的元素嚷掠。 3大于4嗎？ 不大于鳄梅， 這意味著我們完成了數(shù)字4保持排序的插入叠国。
下一節(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
a.swapAt(y - 1, y)
y -= 1
}
}
return a
}
代碼在 playground 里測試：
let list = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]
insertionSort(list)
代碼工作原理：
先創(chuàng)建一個數(shù)組的拷貝粟焊。因為我們不能直接修改參數(shù)
array中的內(nèi)容，所以這是非常必要的孙蒙。insertionSort()會返回一個原始數(shù)組的拷貝项棠，就像Swift已擁有的sort()方法一樣。在函數(shù)里有兩個循環(huán)挎峦，外循環(huán)依次查找數(shù)組中的每一個元素香追；這就是從數(shù)字堆中取最上面的數(shù)字的過程。變量
x是有序部分結(jié)束和堆開始的索引（也就是 | 符號的位置）坦胶。要記住的是透典，在任何時候，從0到x的位置數(shù)組都是有序的顿苇，剩下的則是無序的峭咒。內(nèi)循環(huán)則從
x位置的元素開始查找。x是堆頂?shù)脑丶退辏锌赡鼙惹懊娴乃性囟夹〈斩印?nèi)循環(huán)從有序數(shù)組的后面開始往前查找。每次找到一個大的元素幔翰，就交換它們的位置漩氨，直到內(nèi)層循環(huán)結(jié)束，數(shù)組的前面部分依然是有序的遗增，有序的元素也增加了一個叫惊。
注意： 外層循環(huán)是從1開始，而不是0做修。從堆頂將第一個元素移動到有序數(shù)組沒有任何意義霍狰，可以跳過。
不交換
上面的插入排序算法可以很好的完成任務缓待，但是也可以通過移除對 swap() 的調(diào)用來提升速度蚓耽。
通過交換兩個數(shù)字來讓下一個元素移動到合適的位置的：
[ 3, 5, 8, 4 | 6 ]
<-->
swap
[ 3, 5, 4, 8 | 6 ]
<-->
swap
可以通過將前面的元素往右挪一個位置來代替元素的交換渠牲，然后將新的數(shù)字放到正確的位置旋炒。
[ 3, 5, 8, 4 | 6 ] remember 4
*
[ 3, 5, 8, 8 | 6 ] shift 8 to the right
--->
[ 3, 5, 5, 8 | 6 ] shift 5 to the right
--->
[ 3, 4, 5, 8 | 6 ] copy 4 into place
*
代碼：
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 這行代碼就是將前一個元素往右移動一個位置，在內(nèi)層循環(huán)結(jié)束的時候签杈， y 就是 插入的數(shù)字 在有序數(shù)組中的位置瘫镇， //2 這行代碼就是將數(shù)字拷貝到正確的位置鼎兽。
泛型化
如果能排序的類型不止數(shù)字就更好了。我們可以使數(shù)組的數(shù)據(jù)類型泛型化铣除，然后使用一個用戶提供的函數(shù)（或閉包）來執(zhí)行比較操作谚咬。這只要改變兩個地方。
函數(shù)簽名變成：
譯注：函數(shù)簽名的英文原文是 function signature尚粘，而我們常接觸到是 函數(shù)聲明（function declaration）择卦，這兩個概念都是有的，暫且不去追究它們的區(qū)別了郎嫁，此處就譯為函數(shù)簽名秉继，應該不影響對下面文章的理解。
func insertionSort<T>(_ array: [T], _ isOrderedBefore: (T, T) -> Bool) -> [T] {
數(shù)組有一個類型 [T]泽铛，[T] 是泛型化的一個占位類型∩屑現(xiàn)在 insertionSort() 可以接收任何類型的數(shù)組，不管它是包含數(shù)字盔腔、字符串或者其它類型杠茬。
新的參數(shù) isOrderedBefore: (T, T) -> Bool 是一個接收兩個 T 對象然后返回一個 Bool 值的方法，如果第一個對象大于第二個弛随，那么返回 true瓢喉，反之則返回 false。這與 Swift 內(nèi)置的 sort() 方法是一樣的撵幽。
另外一個變化就是內(nèi)循環(huán)灯荧，現(xiàn)在是這樣的：
while y > 0 && isOrderedBefore(temp, a[y - 1]) {
temp < a[y - 1]被 isOrderedBefore() 替代，不僅可以比較數(shù)字盐杂，還可以比較各種對象了逗载。
在 playground 中測試:
let numbers = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]
insertionSort(numbers, <)
insertionSort(numbers, >)
< 和 > 決定排序的順序，分別代表低到高和高到低链烈。
譯注：參數(shù)
isOrderedBefore可以使用<或>厉斟，是因為在Swift中運算符定義就類似(T, T) -> Bool。
在Foundation中可以看到不同類型定義了運算符强衡，比如Decimal就定義了<：public static func < (lhs: Decimal, rhs: Decimal) -> Bool擦秽。
Swift文檔介紹了Custom Operators可以參考。
當然漩勤，我們也可以對其它數(shù)據(jù)類型排序如字符串：
let strings = [ "b", "a", "d", "c", "e" ]
insertionSort(strings, <)
也可以是更復雜的對象：
let objects = [ obj1, obj2, obj3, ... ]
insertionSort(objects) { $0.priority < $1.priority }
閉包告訴 insertionSort() 方法用 priority 屬性來進行排序感挥。
插入排序是一個 穩(wěn)定 的排序算法。當元素相同時越败，排序后依然保持排序之前的相對順序触幼，那么這個排序算法就是 穩(wěn)定 的。對于像數(shù)字或者字符串這樣的簡單類型來說究飞，這不是很重要置谦。但是對于復雜的對象來說堂鲤，這就很重要了，如果兩個對象有相同的 priority媒峡， 不管它們其他的屬性如何瘟栖，這兩個對象都不會交換位置。
性能
如果數(shù)組是已經(jīng)排好序的話谅阿，插入排序是非嘲胗矗快速的。這聽起來好像很明顯签餐，但是不是所有的搜索算法都是這樣的镜沽。在實際中，有很多數(shù)據(jù)（大部分贱田，可能不是全部）是已經(jīng)排序好的缅茉，插入排序在這種情況下就是一個非常好的選擇。
插入排序的最差和平均性能是 O(n^2)男摧。這是因為在函數(shù)里有兩個嵌套的循環(huán)蔬墩。其他如快速排序和歸并排序的性能則是 O(n log n)，在有大量輸入的時候會更快耗拓。
插入排序在對小數(shù)組進行排序的時候?qū)嶋H是非衬绰快的。一些標準庫在數(shù)據(jù)量小于或者等于10的時候會從快速排序切換到插入排序乔询。
我們做了一個速度測試來對比我們的 insertionSort() 和 Swift 內(nèi)置的 sort()樟插。在大概有 100 個元素的數(shù)組中，速度上的差異非常小竿刁。然后黄锤，如果輸入一個非常大的數(shù)據(jù)量， O(n^2) 馬上就比 O(n log n) 的性能糟糕多了食拜，插入排序差很多鸵熟。
