Algorithm - 选择排序

说明

首先，找到数组中最小的那个元素，其次，将它和数组的第 一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。再次，在剩下的元素中 找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法 叫做选择排序，因为它在不断地选择剩余元素之中的最小者。

特点

• 运行时间和输入无关.

  为了找出最小的元素而扫描一遍数组并不能为下一遍扫描提供什么信息。 这种性质在某些情况下是缺点，因为使用选择排序的人可能会惊讶地发现，一个已经有序的数组或 是主键全部相等的数组和一个元素随机排列的数组所用的排序时间竟然一样长!

• 数据移动是最少的。

  每次交换都会改变两个数组元素的值，因此选择排序用了 N 次交换——交 换次数和数组的大小是线性关系。

Code

这里是改变的原slice,并没有额外开辟内存

package main

import (
	"fmt"
)

func main() {
	arr := []int{1, 6, 8, 3, 23, 454, 15, 334, 8, 6, 35}

	selection(arr[:])
	fmt.Println(arr)
}

func selection(arr []int) {
	for i := 0; i < len(arr); i++ {
		min := i
		for j := i + 1; j < len(arr); j++ {
			if less(arr[j], arr[min]) {
				min = j
			}
		}
		exch(arr[:], i, min)
	}
}

func less(a, b int) bool {
	return a < b
}
func exch(arr []int, i, min int) {
	arr[i], arr[min] = arr[min], arr[i]
}