cc128b01cc0a031743b5cd9aec7f0468.md

选择排序

选择排序是最简单直观的一种算法，基本思想为每一趟从待排序的数据元素中选择最小(或最大)的一个元素作为首元素，直到所有元素排完为止，选择排序是不稳定排序。

在算法实现时，每一趟确定最小元素的时候会通过不断比较交换来首位置为当前最小，交换是一个比较耗时的操作。在未完全确定当前最小元素之前，这些交换都是无意义的。我们可以通过设置一个变量min，每一次比较仅存储较小元素的数组下标，当轮循环结束后，这个变量存储的就是当前最小元素的下标，此时再执行交换操作即可

选择排序经过上述优化后，无论数组原始排列如何，比较次数是不变的，对于交换操作，在最好的情况下也就是数组完全有序的情况，无需任何交换移动，在最差情况下，也就是数组倒序的时候，交换次数为n-1次，综合下来时间复杂度为O(n^2)

package main

import (
	"fmt"
)

//选择排序
func SelectSort (a []int) []int {
	length := len(a)
	minIndex := 0
	for i := 0; i < length; i++ {
		minIndex = i
		for j := i; j < length; j++ {
			if a[minIndex] > a[j] {
				minIndex = j
			}
		}
		if minIndex != i {
			a[minIndex], a[i] = a[i], a[minIndex]
		}
	}
	return a
}

func main() {
	beforeSortSet := []int {10, 22, 33, 21, 56, 32, 81, 73, 69, 83}
	fmt.Println("Before Sort:", beforeSortSet)
	afterSortSet := SelectSort(beforeSortSet)
	fmt.Println("After Sort:", afterSortSet)
}