選擇排序 · PHP/Python/前端/Linux 等等學習筆記

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