參考鏈接
基本思想
選擇排序和插入排序類似胎围，都將數(shù)據(jù)分為有序區(qū)和無序區(qū)桃煎，不同的是選擇排序是從無序區(qū)選一個(gè)最小的元素直接放到有序區(qū)的最后花颗。
設(shè)數(shù)組為a[0…n-1]弊添。
- 初始時(shí)，數(shù)組全為無序區(qū)為a[0..n-1]删性。令i=0
- 在無序區(qū)a[i…n-1]中選取一個(gè)最小的元素适揉，將其與a[i]交換荧恍。交換之后a[0…i]就形成了一個(gè)有序區(qū)岳守。
- i++并重復(fù)第二步直到i==n-1其屏。排序完成杰标。
算法的實(shí)現(xiàn)
extension Array where Element: Comparable {
mutating func selectSort() {
for i in 0 ..< count {
var minIndex = i
for j in (i + 1) ..< count where self[j] < self[minIndex] {
minIndex = j
}
if minIndex != i {
swapAt(i, minIndex)
}
}
}
}
改進(jìn)（二元選擇排序）
簡(jiǎn)單選擇排序盏袄，每趟循環(huán)只能確定一個(gè)元素排序后的定位间雀。我們可以考慮改進(jìn)為每趟循環(huán)確定兩個(gè)元素（當(dāng)前趟最大和最小記錄）的位置极舔，從而減少排序所需的循環(huán)次數(shù)群发。
改進(jìn)后對(duì)n個(gè)數(shù)據(jù)進(jìn)行排序晰韵，最多只需進(jìn)行n/2趟循環(huán)即可。具體實(shí)現(xiàn)如下：
extension Array where Element: Comparable {
mutating func selectSortBetter() {
var next, end, minIndex, maxIndex: Int
/*
1. 整個(gè)排序過程共進(jìn)行n/2趟
2. 每次循環(huán)熟妓，會(huì)找出最小和最大的元素雪猪，與開始和結(jié)束位置的元素交換
*/
for begin in 0 ..< count / 2 {
end = count - 1 - begin
minIndex = begin
maxIndex = begin
next = begin + 1
while next <= end {
if self[next] < self[minIndex] {
minIndex = next
continue
}
if self[next] > self[maxIndex] {
maxIndex = next
}
next += 1
}
/*
先放最小的元素
因?yàn)闀?huì)將最小元素和第一個(gè)元素交換
所以如果第一個(gè)元素就是最大的元素，那么max應(yīng)該指向交換后的索引
*/
if minIndex != begin {
swapAt(begin, minIndex)
if maxIndex == begin {
maxIndex = minIndex
}
}
if maxIndex != end {
swapAt(end, maxIndex)
}
}
}
}
