[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) } ```