select

README

选择排序

选择排序和插入排序类似，将集合分成了两部分：[有序， 无序]

• 插入排序：逐个遍历无序元素，在有序区间的合适位置插入
• 选择排序：找到无序区间的最小值，追加到有序区间

排序过程

整个排序过程十分直观，如数组 [29, 10, 14, 37, 13]

select_sort $ go run main.go
[UNSORTED]:      [29 10 14 37 13]
[DEBUG min]:     10		# 无序区间最小值为 10，此时数组为 [10 29 14 37 13]
[DEBUG min]:     13		# [10 13 14 37 29]
[DEBUG min]:     14		# [10 13 14 37 29]
[DEBUG min]:     29		# [10 13 14 29 37]
[SORTED]:        [10 13 14 29 37]

复杂度

时间复杂度

最好情况：已有序，每个元素交换 0 次

最坏情况：逆序，每个元素交换 n-1 次

平均复杂度：由于比较次数始终都是 ，复杂度为 O(N^2)

空间复杂度

原地排序：O(1)

稳定性

本例的选择排序，从无序区间中从前往后遍历选出最小值，保持了相同元素间的顺序，是稳定的。

如：[2, 1, 8, 1] 最终排序完毕是 [1, 1, 2, 8]，两个 1 的相对位置未发生改变。

使用场景

选择排序的实现未使用额外空间，直接在原地进行排序，适用于对空间复杂度要求较高的排序场景。同时它的时间复杂度并不低，和插入排序一样只适用于小数据量排序。