选择排序

ByWhat'sUs

选择排序

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。这样一来，当遍历完未排序区间，就意味着已经完成整个序列的排序了。

package main

import "fmt"

func selectionSort(nums []int) {
    if len(nums) <= 1 {
        return
    }
    // 已排序区间初始化为空，未排序区间初始化待排序切片
    for i := 0; i < len(nums); i++ {
        // 未排序区间最小值初始化为第一个元素
        min := i
        // 从未排序区间第二个元素开始遍历，直到找到最小值
        for j := i + 1; j < len(nums); j++ {
            if nums[j] < nums[min] {
                min = j
            }
        }
        // 将最小值与未排序区间第一个元素互换位置（等价于放到已排序区间最后一个位置）
        if min != i {
            nums[i],nums[min] = nums[min], nums[i]
        }
    }
}

func main() {
    nums := []int{4, 5, 6, 7, 8, 3, 2, 1}
    selectionSort(nums)
    fmt.Println(nums)
}

性能分析

• 很显然，选择排序的时间复杂度也是 O(n²)
• 由于不涉及额外的存储空间，所以是原地排序；
• 由于涉及非相邻元素的位置交换，所以是不稳定的排序算法。