介绍
选择排序（Selection Sort）是一种简单的排序算法，其基本思想是每次从未排序的部分选择最小（或最大）的元素，并将其放置在已排序部分的末尾。
以下是选择排序算法的步骤：
- 定义一个待排序序列。
- 遍历序列，从第一个元素开始。
- 在未排序部分中找到最小（或最大）的元素。
- 将找到的最小（或最大）元素与当前位置的元素进行交换。
- 将当前位置后移一位，继续进行步骤 3 和 4，直到遍历完整个序列。
- 完成排序后，待排序序列变成有序序列。
代码实现
package main
import "fmt"
func selectionSort(a []int) {
for i := 0; i < len(a)-1; i++ {
minIndex := i
for j := i + 1; j < len(a); j++ {
if a[j] < a[minIndex] {
minIndex = j
}
}
a[i], a[minIndex] = a[minIndex], a[i]
fmt.Println(a)
}
fmt.Println(a)
}
func main() {
selectionSort([]int{3, 5, 2, 1, 4})
}
[1 5 2 3 4]
[1 2 5 3 4]
[1 2 3 5 4]
[1 2 3 4 5]
[1 2 3 4 5]
代码解释
外层循环用于迭代整个数组，而内层循环用于查找未排序部分中的最小元素。
外层循环变量i表示当前已排序部分的末尾位置，范围是从0到len(a)-1，其中len(a)是序列的长度。
内层循环变量j表示未排序部分的索引，范围是从i+1到 len(a)-1。在每一轮内层循环中，找到未排序部分中的最小元素的索引minIndex。
然后，将最小元素与当前位置i进行交换，将找到的最小元素放到已排序部分的末尾。
复杂度
选择排序的最好、最坏和平均时间复杂度都为 O(n^2)，空间复杂度为 O(1)
-
最坏情况下，当输入数组是完全逆序排列时，内层循环每次都需要遍历未排序部分的所有元素来找到最小元素。外层循环需要执行 n-1 次，其中 n 是数组的长度。内层循环的迭代次数依次为 n-1、n-2、n-3、…、2、1。(n-1) + (n-2) + (n-3) + … + 2 + 1，这个求和公式可以简化为 (n^2 – n) / 2。因此，选择排序算法的总体时间复杂度可以表示为 O(n^2)。
-
最好情况下：在最好的情况下，输入数组已经是有序的。尽管输入数组有序，但选择排序算法仍然需要遍历整个未排序部分来找到最小元素，并进行交换。因此，无论输入是否有序，选择排序的时间复杂度都是 O(n^2)。
-
平均情况下：在平均情况下，选择排序的时间复杂度仍然是 O(n^2)。这是因为选择排序的每一轮都需要遍历未排序部分来查找最小元素，而未排序部分的长度随着每一轮的迭代而递减。虽然在平均情况下，内层循环的迭代次数会随着轮次的减少而减少，但这并不足以改变算法的总体时间复杂度。
-
在选择排序中，我们只需要维护少量变量，包括迭代变量、最小值索引和交换操作时的临时变量。这些变量的数量与输入数组的大小无关，无论输入数组的规模如何增大，选择排序算法所使用的额外空间是恒定的，与输入规模无关。因此，选择排序的空间复杂度是 O(1)。
和冒泡排序的区别
- 比较次数：选择排序每轮只进行一次比较，而冒泡排序每轮都要进行多次比较和交换。
- 交换次数：选择排序每轮只进行一次交换，而冒泡排序每次比较都可能进行交换。
- 时间复杂度：选择排序的最好、最坏和平均时间复杂度都为 O(n^2)，而冒泡排序的最好时间复杂度为 O(n)，最坏和平均时间复杂度也是 O(n^2)。
- 空间复杂度：两种排序算法的空间复杂度都为 O(1)，即不需要额外的空间。