參考
Java排序算法(二)：簡單選擇排序
數(shù)據(jù)結構和算法(Golang實現(xiàn))(20)排序算法-選擇排序
我打撲克牌的時候，會習慣性地從左到右掃描看靠，然后將最小的牌放在最左邊寄月，然后從第二張牌開始繼續(xù)從左到右掃描第二小的牌垮刹，放在最小的牌右邊瓢喉，以此反復。選擇排序和我玩撲克時的排序特別相似纹坐。
冒泡排序在不斷地交換归斤，而簡單排序只會在找到最小值時才交換痴荐，復雜度仍然是O(n2)
Paste_Image.png
// 在無序區(qū)中選出最小的元素扼仲，然后將它和無序區(qū)的第一個元素交換位置驳棱。
// 原理跟冒泡排序一樣，算是冒泡的衍生版本
function sort7(array) {
var len = array.length,
i, j, k, tmp, result;
result = array.slice(0);
for (i = 0; i < len; i++) {
k = i;
for (j = i + 1; j < len; j++) {
if (result[j] < result[k]) k = j;
}
if (k != i) {
tmp = result[k];
result[k] = result[i];
result[i] = tmp;
}
}
return result;
}
[算法特點]
時間復雜度：需要進行1+2+3+...+(n-1)=n*(n-1)/2,復雜度為O(n^2)拴还。
該算法最大的特點就是交換移動數(shù)據(jù)次數(shù)相當少膝宁，這會節(jié)約相應的時間鸦难。分析它的時間復雜度你會發(fā)現(xiàn)，無論最好最差的情況员淫，其比較次數(shù)都是一樣的多合蔽。
簡單選擇排序的性能上還是要略優(yōu)于冒泡排序。
選擇排序是一個不穩(wěn)定的排序算法介返，比如數(shù)組：[5 6 5 1]拴事，第一輪迭代時最小的數(shù)是1，那么與第一個元素5交換位置圣蝎，這樣數(shù)字1就和數(shù)字5交換了位置刃宵，導致兩個相同的數(shù)字5排序后位置變了。
package main
import "fmt"
func SelectSort(list []int) {
n := len(list)
// 進行 N-1 輪迭代
for i := 0; i < n-1; i++ {
// 每次從第 i 位開始徘公，找到最小的元素
min := list[i] // 最小數(shù)
minIndex := i // 最小數(shù)的下標
for j := i + 1; j < n; j++ {
if list[j] < min {
// 如果找到的數(shù)比上次的還小牲证，那么最小的數(shù)變?yōu)樗? min = list[j]
minIndex = j
}
}
// 這一輪找到的最小數(shù)的下標不等于最開始的下標，交換元素
if i != minIndex {
list[i], list[minIndex] = list[minIndex], list[i]
}
}
}
func main() {
list := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
SelectSort(list)
fmt.Println(list)
}
