复杂度

O(n*n)

package main

import "fmt"

func main() {
	arr := []int{9,8,7,6,5,4,3,2,1}
	arr = selectionSort(arr)
	fmt.Println(arr)
}

//https://stackoverflow.com/questions/37334119/how-to-delete-an-element-from-array-in-golang/37335777
func remove(s []int, i int) []int {
	s[i] = s[len(s)-1]
	// We do not need to put s[i] at the end, as it will be discarded anyway
	return s[:len(s)-1]
}

func findSmallest(arr []int) int {
	smallest := arr[0]
	smallestIndex := 0
	for i, v := range arr {
		if v < smallest {
			smallest = v
			smallestIndex = i
		}
	}
	return smallestIndex
}

func selectionSort(arr []int) []int {
	newArr := make([]int, len(arr))
	l := len(arr)
	for i:=0; i<l;i++ {
		index := findSmallest(arr)
		newArr[i] = arr[index]
		arr = remove(arr, index)
	}
	return newArr
}