选择排序

选择排序的思想是：双重循环遍历数组，每经过一轮比较，找到最小元素的下标，将其交换至首位。

package main

import "fmt"

func main() {
	values1 := []int{4, 93, 84, 85, 80, 37, 81, 93, 27, 12}
	fmt.Println(values1) // [4 93 84 85 80 37 81 93 27 12]
	SelectSort(values1)
	fmt.Println(values1) // [4 12 27 37 80 81 84 85 93 93]

	values2 := []int{4, 93, 84, 85, 80, 37, 81, 93, 27, 12}
	fmt.Println(values2) // [4 93 84 85 80 37 81 93 27 12]
	SelectSort(values2)
	fmt.Println(values2) // [4 12 27 37 80 81 84 85 93 93]
}

func SelectSort(values []int) {
	for i := 0; i < len(values); i++ {
		min := i
		for j := len(values) - 1; j > i; j-- {
			if values[j] < values[min] {
				min = j
			}
		}
		values[i], values[min] = values[min], values[i]
	}
}

func SelectSort2(values []int) {
	var minIndex int
	var maxIndex int
	// i 只需要遍历一半
	for i := 0; i < len(values) / 2; i++ {
		minIndex = i
		maxIndex = i
		for j := i + 1; j < len(values) -1; j++ {
			if values[minIndex] > values[j] {
				// 记录最小值的下标
				minIndex = j
			}
			if values[maxIndex] < values[j] {
				// 记录最大值的下标
				maxIndex = j
			}
		}
		// 如果 minIndex 和 maxIndex 都相等，那么他们必定都等于 i，且后面的所有数字都与 arr[i] 相等，此时已经排序完成
		if minIndex == maxIndex {
			break;
		}
		// 将最小元素交换至首位
		values[minIndex], values[i] = values[i], values[minIndex]
		// 如果最大值的下标刚好是 i，由于 arr[i] 和 arr[minIndex] 已经交换了，所以这里要更新 maxIndex 的值。
		if maxIndex == i {
			maxIndex = minIndex
		}
		// 将最大元素交换至末尾
		lastIndex := len(values) -1 - i;
		values[maxIndex], values[lastIndex] = values[lastIndex], values[maxIndex]
	}
}