Algorithms in Swift 3
Insertion sort
插入排序是最基礎(chǔ)的排序算法之一。它最核心的思想旬薯，由以下幾條構(gòu)成。當(dāng)我們要對(duì)一個(gè)值為[1, 5, 6]
的數(shù)組從大到小排列時(shí)：
1.把序列的第一個(gè)元素想象成一個(gè)“子序列”[1]适秩，它是已經(jīng)排序的；
2.按照既定的排序規(guī)則硕舆，把由序列的前兩個(gè)元素構(gòu)成的“子序列”排序：[5, 1]秽荞；
3.之后，讀入6抚官，在之前已經(jīng)排序好的“子序列”中扬跋，從右向左逐個(gè)和新讀入的元素進(jìn)行比對(duì)。如果滿足排序規(guī)則凌节，就交換已排序數(shù)組中的元素和待排序的元素：
[5, 1, 6]
^ 6 > 1 == true
[5, 1, 6]
<--->
swap
[5, 6, 1]
簡單來說钦听，就是不斷通過比對(duì)，移動(dòng)待排序元素的位置倍奢。直到待排序元素和之前已排序“子序列”全部元素都比對(duì)完之后：
[5, 6, 1]
^ 6 > 5 == true
[5, 6, 1]
<--->
swap
[6, 5, 1]
新形成的序列就已經(jīng)是排序好的了朴上。（當(dāng)然，這里也有一個(gè)潛臺(tái)詞卒煞，就是如果和子序列中第一個(gè)元素比對(duì)之后不需要移動(dòng)痪宰，則新添加進(jìn)來的元素就應(yīng)該直接添加到子序列末尾）；
- 反復(fù)3的操作畔裕，當(dāng)讀完所有待排序的元素之后衣撬，整個(gè)序列就排序完成了；
在理解插入排序的時(shí)候蒸健，要時(shí)刻記住一件事情：元素的操作永遠(yuǎn)只發(fā)生在相鄰的兩個(gè)元素之間烤镐。當(dāng)我們?cè)陬^腦中執(zhí)行插入排序時(shí)帘饶，偶爾會(huì)忘記這條，會(huì)想著是否存在著跨元素交換的情況扛点，然后就把自己搞暈了。
實(shí)現(xiàn)
如何使用毫蚓？
在實(shí)現(xiàn)之前占键，我們要先考慮下開發(fā)者會(huì)如何使用這個(gè)算法，例如這樣：
let a: Array<Int> = [1, 5, 6]
insertionSortOf(a)
或者元潘，我們?cè)试S用戶指定一個(gè)排序方法
let a: Array<Int> = [1, 5, 6]
insertionSortOf(a, byCriteria: >) // [6, 5, 1]
然后畔乙，我們還應(yīng)該允許對(duì)包含任何“可比較”元素的Array進(jìn)行排序。于是翩概，insertionSort
的聲明可以是下面這樣的牲距。
如何按Swift 3的方式聲明
typealias CRITERIA<T> = (T, T) -> Bool
func insertionSortOf<T: Comparable>(
_ coll: Array<T>,
byCriteria: CRITERIA<T> = { $0 < $1 }) ->Array<T>
在這個(gè)聲明里返咱，有以下和Swift 3相關(guān)的說明：
首先，我們使用了SE-0048中的新特性牍鞠，允許在typealias
中使用泛型參數(shù)咖摹；
其次，在方法的命名上难述，我們參考了SE-0023 API設(shè)計(jì)指南中的要求：
“如果方法中第一個(gè)參數(shù)和方法名一起形成了一個(gè)語法正確的短語萤晴，去掉第一個(gè)參數(shù)的label，并且把參數(shù)label放到方法名中”
因此胁后，我們把“表示要排序的集合”使用的介詞“of”店读，從第一個(gè)參數(shù)名，放到了函數(shù)名中攀芯。
第三屯断，在Swift 3里，根據(jù)SE-0046中的提議侣诺，函數(shù)的第一個(gè)參數(shù)不再默認(rèn)省略label殖演，它將和其他參數(shù)一樣擁有默認(rèn)的label行為。因此年鸳，如果我們要省略label趴久，必須在參數(shù)名前強(qiáng)制使用_
。因此阻星，在聲明里朋鞍，我們需要強(qiáng)制省略第一個(gè)參數(shù)的label。
第四妥箕，根據(jù)SE-0023 API設(shè)計(jì)指南中的要求：
-
要讓方法調(diào)用時(shí)滥酥，形成語法正確的英文短語：因此，我們讓第二個(gè)表示自定義比較規(guī)則的參數(shù)名為
byCriteria
畦幢； - 要為方法中的closure參數(shù)設(shè)置label：因此坎吻，我們沒有去掉第二個(gè)closure參數(shù)的label；
-
當(dāng)方法的參數(shù)在絕大多數(shù)時(shí)候使用相同值時(shí)宇葱，應(yīng)為它指定默認(rèn)值：因此瘦真，我們讓
byCriteria
的默認(rèn)行為是按升序排列；
實(shí)現(xiàn)insertionSort
按照一開始我們?cè)谒惴ㄋ悸分械拿枋鍪蚯疲?code>insertionSort
中添加下面的代碼：
首先诸尽，只有一個(gè)元素的數(shù)組是無需排序的，我們直接返回就好：
func insertionSortOf<T: Comparable>(
_ coll: Array<T>,
byCriteria: CRITERIA<T> = { $0 < $1 }) -> Array<T> {
// 1. An array with a single element is ordered
guard coll.count > 1 else {
return coll
}
}
其次印颤，復(fù)制一份參數(shù)數(shù)組您机，用于在函數(shù)內(nèi)部進(jìn)行排序：
func insertionSortOf<T: Comparable>(
_ coll: Array<T>,
byCriteria: CRITERIA<T> = { $0 < $1 }) -> Array<T> {
//: #### 1. An array with a single element is ordered
guard coll.count > 1 else {
return coll
}
var result = coll
}
第三，我們從數(shù)組中第二個(gè)元素開始，通過逐個(gè)比對(duì)际看，來不斷形成已排序好的子數(shù)組：
for x in 1 ..< coll.count {
var = x
let key = result[y]
print("Get: \(key)")
// 2. If the key needs to swap in the previous ordered sub array
while y > 0 && byCriteria(key, result[y - 1]) {
print("-----------------------------")
print("Remove: \(result[y]) at pos: \(y)")
print("Insert: \(key) at pos: \(y - 1)")
print("-----------------------------")
// 3. Swap the value
// The new Swift 3 API:
// remove(at:) replaces removeAtIndex
// You can also use swap(:) instead of remove and insert.
result.remove(at: y)
result.insert(key, at: y - 1)
y -= 1
}
}
最后咸产，數(shù)組中所有的元素都遍歷之后，整個(gè)數(shù)組就完成排序了仲闽，我們直接把排序后的數(shù)組返回：
func insertionSortOf<T: Comparable>(
_ coll: Array<T>,
byCriteria: CRITERIA<T> = { $0 < $1 }) -> Array<T> {
guard coll.count > 1 else {
return coll
}
var result = coll
for x in 1 ..< coll.count {
var y = x
let key = result[y]
print("Get: \(key)")
// 2. If the key needs to swap in the previous ordered sub array
while y > 0 && byCriteria(key, result[y - 1]) {
print("-----------------------------")
print("Remove: \(result[y]) at pos: \(y)")
print("Insert: \(key) at pos: \(y - 1)")
print("-----------------------------")
// 3. Swap the value
// Notice the new Swift 3 API: remove(at:) replaces removeAtIndex
// You can also use swap(:) instead of remove and insert
result.remove(at: y)
result.insert(key, at: y - 1)
y -= 1
}
}
// 4. Return the sorted array
return result
}
測試
用一開始我們?cè)O(shè)計(jì)的使用方法來測試insertionSort：
let a: Array<Int> = [1, 5, 6]
insertionSortOf(a)
由于默認(rèn)就是從小到大排序脑溢，并且，原始數(shù)組本身就是已經(jīng)排序的赖欣，因此屑彻，我們可以在控制臺(tái)看到下面的結(jié)果：
如果我們傳遞一個(gè)自定義的比較規(guī)則，例如從大到小排序：
let a: Array<Int> = [1, 5, 6]
insertionSortOf(a, byCriteria: >)
就可以在控制臺(tái)看到這樣的結(jié)果：
數(shù)字5經(jīng)歷了一次交換畏鼓，數(shù)字6經(jīng)歷了兩次交換酱酬。
Have a try?
不用交換元素的插入排序方法
除了使用remove&insert或swap
之外，還有一種插入排序的手段云矫。用之前的[1, 5, 6]
降序排列舉例。假設(shè)算法執(zhí)行到了讀入數(shù)字6:
1.記錄讀入的值：
[5, 1, 6]
^ --> remember 6
2.在新讀入位置前已排序好的子數(shù)組里汗菜，不斷用前一個(gè)數(shù)字覆蓋后一個(gè)位置让禀，為新讀入的元素找到合適的位置：
[5, 1, 1]
--> shift 1 right
[5, 5, 1]
--> shift 5 right
[6, 5, 1]
^ --> Copy 6 here
不同的實(shí)現(xiàn)方法之間的性能差異有多大呢？
-
insert&remove陨界； -
swap巡揍； - 以及我們最后提到的移動(dòng)元素；
當(dāng)移動(dòng)大量元素時(shí)菌瘪，這些算法之間的差異有多大呢腮敌？自己試驗(yàn)一下吧，歡迎大家把實(shí)驗(yàn)的結(jié)果貼到泊學(xué)視頻下面的泊學(xué)Disqus論壇里俏扩。 :-)
