选择排序

排序

说明

每轮选出剩余元素中的最小值；时间 O(n²)，交换次数 O(n)。

分析

在未排序部分找到最小元素，与当前位置交换，然后缩小待处理范围。它始终需要二次方级比较，却只进行线性次数的交换。

图解推演

[3,1,2] 第一轮在整个后缀找最小值 1，与首位 3 交换；第二轮在 [3,2] 找 2，再交换。找到更小值时只更新最小下标，整轮结束才交换。即使输入已排序，也仍需检查所有后缀，比较次数 n(n−1)/2。

查看图表代码

适用前提与边界

交换会改变相等元素的相对顺序，因此这个基本版本不稳定。

示例输入与调用

a := []int{3, 1, 2}
	SelectionSort(a)
	fmt.Println(a)

运行输出

[1 2 3]

完整 Go 示例

package main

import "fmt"

func SelectionSort(a []int) {
	for i := range a {
		m := i
		for j := i + 1; j < len(a); j++ {
			if a[j] < a[m] {
				m = j
			}
		}
		a[i], a[m] = a[m], a[i]
	}
}

func main() {
	a := []int{3, 1, 2}
	SelectionSort(a)
	fmt.Println(a)
}