选择排序

实现原理

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的实现过程: 在不断未排序的区间中找到最小的元素，将其放入已排序区间的尾部。
选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。这样一来，当遍历完未排序区间，就意味着已经完成整个序列的排序了。图示如下：

动图演示

选择排序算法的原理如下：

• 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
• 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
• 重复第二步，直到所有元素均排序完毕。

示例代码

选择排序的实现逻辑非常简单，对应的 Go 实现代码如下：

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

由于传递到 selectionSort 函数的参数是 []int 类型的切片，而切片是引用类型，所以其实不必定义返回值，运行上述代码，打印结果如下：

表明排序算法可以正常工作。

性能分析

接下来，我们来看看选择排序的性能和稳定性：

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

综合比较前面介绍的三种排序算法，时间复杂度都是一样的，也都是原地排序，但是选择排序是不稳定的排序算法，此外，插入排序和冒泡排序相比较的话，插入排序只需要执行一条语句，而冒泡排序需要三条，因此在同等条件下，或者数据量很大的情况下，插入排序性能是要略优于冒泡排序的，所以综合比较下来，三者的优先级是插入排序 > 冒泡排序 >> 选择排序。
不过三者的时间复杂度都是 $O(n^2)$，在数据量很大的情况下性能表现其实都不理想，还可以进一步进行优化，这就是我们接下来要介绍的归并排序和快速排序算法。

选择排序与插入排序的区别

插入排序和选择排序都有两层循环，外循环遍历整个数组，内循环稍有区别：

• 选择排序的内循环是遍历一组未排过序的数组
• 插入排序的内循环是遍历一组已排过序的数组

选择排序原理：主要在选择上，每一次从无序队列中选择出最小值，然后将其放置在有序队列的末尾，然后在无序队列中将其删除。
插入排序原理：默认第一个元素为有序，后面的逐个向有序中插入，特点就是不断的移动数据，一直到排出序列。