选择排序
最后更新于：2022-04-02 04:11:13
[TOC]
## 选择排序
选择排序，一般我们指的是简单选择排序，也可以叫直接选择排序，它不像冒泡排序一样相邻地交换元素，而是通过选择最小的元素，每轮迭代只需交换一次。虽然交换次数比冒泡少很多，但效率和冒泡排序一样的糟糕。
类似于打扑克,扫一遍纸牌,选择最小的放入最左边
## 算法介绍
```
[]表示排好序
起始： 4 2 9 1 未排序数列从左扫描最小的数是 1，与第一个元素 4 交换，交换 1，4
一轮： [1] 2 9 4 未排序数列从左扫描最小的数是 2，不需要交换
二轮： [1 2] 9 4 未排序数列从左扫描最小的数是 4，与第三个元素 9 交换，交换 4，9
三轮： [1 2 4] 9 未排序数列只有 1 个数，结束
结果： [1 2 4 9]
```
比较的次数和冒泡排序一样多，因为扫描过程也是比较的过程，只不过交换的次数减少为每轮 1 次。最佳和最坏时间复杂度仍然是：`O(n^2)`
选择排序是一个不稳定的排序算法，比如数组：`[5 6 5 1]`，第一轮迭代时最小的数是`1`，那么与第一个元素`5`交换位置，这样数字`1`就和数字`5`交换了位置，导致两个相同的数字`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] // 最小数
minIndex := i // 最小数的下标
for j := i + 1; j < n; j++ {
if list[j] < min {
// 如果找到的数比上次的还小，那么最小的数变为它
min = list[j]
minIndex = j
}
}
// 这一轮找到的最小数的下标不等于最开始的下标，交换元素
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)
}
```
### 每次循环通知找最小与最大值
```
package main
import "fmt"
func SelectGoodSort(list []int) {
n := len(list)
// 只需循环一半
for i := 0; i < n/2; i++ {
minIndex := i // 最小值下标
maxIndex := i // 最大值下标
// 在这一轮迭代中要找到最大值和最小值的下标
for j := i + 1; j < n-i; j++ {
// 找到最大值下标
if list[j] > list[maxIndex] {
maxIndex = j // 这一轮这个是大的，直接 continue
continue
}
// 找到最小值下标
if list[j] < list[minIndex] {
minIndex = j
}
}
if maxIndex == i && minIndex != n-i-1 {
// 如果最大值是开头的元素，而最小值不是最尾的元素
// 先将最大值和最尾的元素交换
list[n-i-1], list[maxIndex] = list[maxIndex], list[n-i-1]
// 然后最小的元素放在最开头
list[i], list[minIndex] = list[minIndex], list[i]
} else if maxIndex == i && minIndex == n-i-1 {
// 如果最大值在开头，最小值在结尾，直接交换
list[minIndex], list[maxIndex] = list[maxIndex], list[minIndex]
} else {
// 否则先将最小值放在开头，再将最大值放在结尾
list[i], list[minIndex] = list[minIndex], list[i]
list[n-i-1], list[maxIndex] = list[maxIndex], list[n-i-1]
}
}
}
func main() {
list := []int{5}
SelectGoodSort(list)
fmt.Println(list)
list1 := []int{5, 9}
SelectGoodSort(list1)
fmt.Println(list1)
list2 := []int{5, 9, 1}
SelectGoodSort(list2)
fmt.Println(list2)
list3 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
SelectGoodSort(list3)
fmt.Println(list3)
list4 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6}
SelectGoodSort(list4)
fmt.Println(list4)
}
```
';