聲明：算法和數(shù)據(jù)結(jié)構(gòu)的文章均是作者從github上翻譯過來，為方便大家閱讀。如果英語閱讀能力強的朋友，可以直接到swift算法俱樂部查看所有原文，以便快速學(xué)習(xí)。作者同時也在學(xué)習(xí)中，歡迎交流
目標：將一個數(shù)組按從小到大或從大到小的順序排序好。
當(dāng)我們得到一個數(shù)組，然后需要將數(shù)組內(nèi)容按照一定順序排序好，選擇排序算法可以將該數(shù)組分成兩部分，一邊是排序好的部分，另一邊是還沒排序好的部分。
[ ...已排序數(shù)字... | ...未排序數(shù)字... ]
這一部分與插值排序算法類似，而不同之處是如何將新的數(shù)字放到已排序的部分。
選擇排序算法具體流程如下：
1.從index=0開始，遍歷整個數(shù)組，找到數(shù)組中的最小值
2.將最小值與index=0的數(shù)字交換位置?，F(xiàn)在，在已排序部分中只包含了index=0的數(shù)字
3.從index=1開始，遍歷剩余整個數(shù)組，找到數(shù)組中的最小值
4.將最小值與index=1的數(shù)字交換位置?，F(xiàn)在，在已排序部分中包含了index為0，1的兩個數(shù)字
5.從index=2開始，遍歷剩余整個數(shù)組，找到最小值并與index=2的數(shù)字交換位置。
6.重復(fù)上述過程直到完成數(shù)組排序。
這里的選擇排序算法中的選擇，指的就是每個步驟中，從未排序數(shù)組中選擇出最小值這個過程。
例子
假設(shè)我們需要整理數(shù)組[ 5, 8, 3, 4, 6 ]。我們用|區(qū)分已排序和未排序部分。
在最開始階段，已排序數(shù)組為空，如下：
[| 5, 8, 3, 4, 6 ]
我們開始尋找此時數(shù)組中的最小值。從左到右，最小值為3，將3與index=0的5交換位置，并移動|得到已排序部分，如下：
[ 3 | 8, 5, 4, 6 ]
* *
此時已排序部分為[3]，未排序部分為[8, 5, 4, 6]. 我們從|右側(cè)開始重新尋找最小值，得到4并與index=1的8交換位置，同時移動|，如下：
[ 3, 4 | 5, 8, 6 ]
* *
此時已排序部分為[3,4]，未排序部分為[5, 8, 6]. 我們從|右側(cè)開始重新尋找最小值，得到5，同時移動|，如下：
[ 3, 4, 5 | 8, 6 ]
*
重復(fù)上述過程直到整個數(shù)組整理完畢。我們得到：
[ 3, 4, 5, 6, 8 |]
總體來說，選擇排序是一種就地排序，因為整個過程都發(fā)生在同一個數(shù)組內(nèi)，沒有用到更多的內(nèi)存。
代碼
func selectionSort(_ array: [Int]) -> [Int] {
guard array.count > 1 else { return array } // 1
var a = array // 2
for x in 0 ..< a.count - 1 { // 3
var lowest = x
for y in x + 1 ..< a.count { // 4
if a[y] < a[lowest] {
lowest = y
}
}
if x != lowest { // 5
swap(&a[x], &a[lowest])
}
}
return a
}
在playgroun中測試:
let list = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]
selectionSort(list)
每一行代碼解釋：
1.如果數(shù)組為空，或者只有一個數(shù)字，無需整理，直接返回
2.拷貝一份數(shù)組。這是一個必要過程，因為我們無法在swift里直接修改array參數(shù)。與swift提供的sort()函數(shù)相同，selectionSort()函數(shù)也會返回一個通過原數(shù)組整理好的數(shù)組備份
3.這里一共有兩個循環(huán)。外循環(huán)按順序遍歷整個數(shù)組，其對應(yīng)的x就是|的位置
4.內(nèi)循環(huán)，用來尋找未排序數(shù)組中的最小值
5.判斷尋找到的最小值是否剛好在調(diào)整位置上，如果是，則直接進行下一個位置的最小值尋找，否則交換位置。注意，加位置判斷是因為swift中swap()函數(shù)不能交換元素自己本身。
總結(jié)：對于數(shù)組中的每個元素，選擇算法均從未排序部分中尋找到最小值并交換到已排序部分的最右端，所以得到的數(shù)組順序是從小到大。當(dāng)然我們可以根據(jù)需要修改為從大到小。當(dāng)然，我們也可以修改數(shù)據(jù)類型，對其他數(shù)據(jù)，如字符進行排序。
性能分析
選擇排序算法十分簡單易懂，但是它的效率比較低，是O(n^2)。它比插值排序更低效但比冒泡排序更高效。在未排序數(shù)組中尋找最小值的過程很慢，而這個過程又是不斷被重復(fù)的。
值得一提的是，堆排序算法的原理與選擇排序相同，但是它在尋找最小值的速度上快于選擇排序，它的性能是O(n log n)。 接下來我們會提到。
