沒(méi)有什么比數(shù)據(jù)結(jié)構(gòu)和算法能更純粹的展示一門(mén)編程語(yǔ)言的用法了疾嗅。做為更具表現(xiàn)力黍衙、更加類型安全、支持多種編程范式的Swift 3料扰，單純理解語(yǔ)法上的變化是遠(yuǎn)遠(yuǎn)不夠的凭豪，讓我們通過(guò)一系列算法，從設(shè)計(jì)初衷到具體的語(yǔ)言實(shí)現(xiàn)晒杈，來(lái)感受這些Swift proposal吧嫂伞。有些改變的確帶了breaking change，但是拯钻，接受它們帖努，你一定可以收獲更多。
源自泊學(xué)
選擇排序（Selection sort）
SelectionSort
Selection sort是一種和insertion sort類似的排序方法粪般，它同樣只適用于對(duì)規(guī)模不大的集合進(jìn)行排序拼余。
它的核心思想是，在序列內(nèi)部亩歹，把序列邏輯上分成已排序和未排序兩部分匙监，不斷找到未排序部分中最符合排序規(guī)則的元素，添加進(jìn)已排序部分小作，直到序列中所有元素都已經(jīng)添加到了已排序部分亭姥，此時(shí)，整個(gè)序列就排序完成了躲惰。
我們用數(shù)組[1, 5, 7, 6]進(jìn)行降序排列來(lái)舉例致份，整個(gè)過(guò)程是這樣的：
1、我們用一個(gè)豎線來(lái)區(qū)分序列中“已排序”和“未排序”的部分础拨，初始時(shí)氮块，“已排序“部分為空，”未排序“部分是整個(gè)序列诡宗；
[ | 1, 5, 7, 6 ]
然后滔蝉，第一個(gè)應(yīng)該從“未排序部分”取出的元素，是7塔沃。把7和緊挨豎線右側(cè)的數(shù)字交換蝠引，并且把豎線向右移動(dòng)一個(gè)位置；
[ | 1, 5, 7, 6 ]
*<--->*
[ | 7, 5, 1, 6 ]
^-->
[ 7, | 5, 1, 6 ]
然后蛀柴，繼續(xù)從“未排序部分”取出元素6螃概，它和5交換，并且把豎線移動(dòng)一個(gè)位置：
[ 7, | 5, 1, 6 ]
*<--->*
[ 7, | 6, 1, 5 ]
^-->
[ 7, 6, | 1, 5 ]
接下來(lái)是5鸽疾，交換它和1的位置吊洼，然后把豎線向右移動(dòng)一個(gè)位置：
[ 7, 6, | 1, 5 ]
* *
[ 7, 6, | 5, 1 ]
^-->
[ 7, 6, 5, | 1 ]
最后，當(dāng)序列中“未排序部分”只有一個(gè)元素的時(shí)候制肮，實(shí)際上整個(gè)序列就已經(jīng)全部排序完成了冒窍。
實(shí)現(xiàn)
理解和選擇排序的核心思想之后，實(shí)現(xiàn)的部分就很簡(jiǎn)單了豺鼻。首先是和插入排序類似的“套路聲明”：
typealias Criteria<T> = (T, T) -> Bool
func SelectionSortOf<T: Comparable>(_ coll: Array<T>,
byCriteria: Criteria<T> = { $0 > $1 }) -> Array<T> {
guard coll.count > 1 else { return coll }
var result = coll
// TODO: add implementation here
return result
}
關(guān)于聲明中和Swift 3相關(guān)的內(nèi)容综液，大家可以參考插入排序中的相關(guān)說(shuō)明，我們就不再重復(fù)了儒飒。直接來(lái)看實(shí)現(xiàn)谬莹。
首先，遍歷數(shù)組中的 0 - (N-1) 元素桩了，每一次迭代届良，都表示把豎線右移，在“未排序部分”找下一個(gè)要交換的元素圣猎，在執(zhí)行真正的交換前士葫，我們先打印了序列的“已排序”和“未排序”部分；
// 1. Increase the sorted sub array
for x in 0 ..< coll.count - 1 {
var candidateIndex = x
print("--------------------------")
print("Sorted:\t\(result[0 ..< candidateIndex])")
print("Unsorted:\t\(result[candidateIndex ..< result.count])")
}
其次送悔，我們?cè)偾短滓粋€(gè)for循環(huán)慢显，用于在“未排序部分”尋找下一個(gè)要交換的元素：
// 1. Increase the sorted sub array
for x in 0 ..< coll.count - 1 {
var candidateIndex = x
print("--------------------------")
print("Sorted:\t\(result[0 ..< candidateIndex])")
print("Unsorted:\t\(result[candidateIndex ..< result.count])")
// 2. Find the next element to be moved into the sorted portion
for y in x + 1 ..< coll.count {
if byCriteria(result[candidateIndex], result[y]) {
candidateIndex = y
}
}
}
第三，找到后欠啤，由于Swift不允許交換同一個(gè)位置的元素荚藻，我們需要判斷下“待移進(jìn)已排序數(shù)組”中的元素是否需要交換：
// 1. Increase the sorted sub array
for x in 0 ..< coll.count - 1 {
var candidateIndex = x
print("--------------------------")
print("Sorted:\t\(result[0 ..< candidateIndex])")
print("Unsorted:\t\(result[candidateIndex ..< result.count])")
// 2. Find the next element to be moved into the sorted portion
for y in x + 1 ..< coll.count {
if byCriteria(result[candidateIndex], result[y]) {
candidateIndex = y
}
}
// 3. Swap the candidate into sorted sub array if needed
print(">>> Move \(result[candidateIndex]) into the sorted portion")
if (candidateIndex != x) {
swap(&result[candidateIndex], &result[x])
}
}
最后，當(dāng)除了最后一個(gè)元素之外的其他元素都已經(jīng)移進(jìn)“已排序”部分時(shí)洁段，整個(gè)序列就已經(jīng)排序完成了应狱，我們直接把result返回：
typealias Criteria<T> = (T, T) -> Bool
func SelectionSortOf<T: Comparable>(_ coll: Array<T>,
byCriteria: Criteria<T> = { $0 > $1 }) -> Array<T> {
guard coll.count > 1 else { return coll }
var result = coll
// 1. Increase the sorted sub array
for x in 0 ..< coll.count - 1 {
var candidateIndex = x
print("--------------------------")
print("Sorted:\t\(result[0 ..< candidateIndex])")
print("Unsorted:\t\(result[candidateIndex ..< result.count])")
// 2. Find the next element to be moved into the sorted portion
for y in x + 1 ..< coll.count {
if byCriteria(result[candidateIndex], result[y]) {
candidateIndex = y
}
}
// 3. Swap the candidate into sorted sub array if needed
print(">>> Move \(result[candidateIndex]) into the sorted portion")
if (candidateIndex != x) {
swap(&result[candidateIndex], &result[x])
}
}
return result
}
測(cè)試
用一開(kāi)始的[1, 5, 7, 6]來(lái)測(cè)試。
首先是默認(rèn)的升序排列：
let a: Array<Int> = [1, 5, 7, 6]
SelectionSortOf(a)
然后是自定義的降序排列：
let a: Array<Int> = [1, 5, 7, 6]
SelectionSortOf(a, byCriteria: <)
從這些結(jié)果里祠丝，我們就能看到選擇排序的執(zhí)行流程了疾呻。
