Golang面试宝典——Go语言实现排序算法之选择排序

关于Golang面试宝典

最近几年，Go的热度持续飙升，国内外很多大公司都在大规模的使用Go。Google是Go语言诞生的地方，其他公司如Facebook、腾讯、阿里、字节跳动、百度、京东、小米等都在拥抱和转向Go。Go语言的开源项目也非常多，如kubernetes、docker、etcd。

随着市场对Go语言人才需求的增长，很多开发者都投入了Go语言的怀抱。本系列文章将以第一视角与大家一同开始Golang的面试之路，希望大家能够有所收获，拿下心仪的offer。

Go语言实现选择排序（SelectionSort）

思想

每一次从待排序的数组中选出最小（或最大）的一个元素，存放在起始位置

复杂度分析

时间复杂度

需要双重循环遍历数组，所以时间复杂度为O(n^2)

空间复杂度

因为在原数组进行修改，所以空间复杂度为O(1)

稳定性

不稳定，当数组中包含多个相等的元素时，选择排序有可能打乱它们原有的顺序

代码实现

func SelectionSort(arr []int) {
	for i := 0; i < len(arr)-1; i++ {
		minIndex := i
		for j := i + 1; j < len(arr); j++ {
			if arr[j] < arr[minIndex] {
				minIndex = j
			}
		}
		arr[i], arr[minIndex] = arr[minIndex], arr[i]
	}
}