[数据结构与算法]选择排序（selectSort）

普通选择排序：
算法思路：
1.在未排序序列中找到最小（大）元素，存放到未排序序列的起始位置
2.从剩余未排序元素中继续寻找最小（大）元素，然后放到未排序序列的起始位置
3.以此类推，直到所有元素均排序完毕
平均时间复杂度：O(n2)
数据比较次数：(n - 1) + (n - 2) + (n - 3) + …… + 1 = 1/2n2 - 1/2n
数据交换次数：(n - 1)
总复杂度：1/2n2 + 1/2n - 1
最佳时间复杂度：O(n2)
最差时间复杂度：O(n2)
空间复杂度：O(1)
稳定性：不稳定
适合场景：少量元素
代码实现：
i : 当前正在排序的索引
index : 记录 最小（最大）元素 的位置
j：用来遍历未排序序列部分

package main

import "fmt"

func main() {
	arr := []int{1, 7, 6, 7, 98, 9, -1, 7, 89, 14, -4, -5, -657}
	selectSort(arr)
	for _, v := range arr {
		fmt.Println(v)
	}
}

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

func swap(arr []int, i, j int) {
	tem := arr[i]
	arr[i] = arr[j]
	arr[j] = tem
}

优化选择排序：
算法思路：
1.在未排序序列中同时找到最小元素与最大元素，分别存放到未排序序列的起始位置与末尾位置
2.从剩余未排序元素中继续寻找最小元素与最大元素，然后放到未排序序列的起始位置与末尾位置
3.以此类推，直到所有元素均排序完毕
平均时间复杂度：O(n2)
数据比较次数：(n - 2) + (n - 4) + (n - 6) + …… + 1 = 1/4n2 - 1/4n
数据交换次数：(n - 1)
总复杂度：1/4n2 + 3/4n - 1
最佳时间复杂度：O(n2)
最差时间复杂度：O(n2)
空间复杂度：O(1)
稳定性：不稳定
适合场景：少量元素
代码实现：
left : 数组最左侧已排序序列的右边界索引
right: 数组最右侧已排序序列的左边界索引
minIndex : 记录 未排序序列 的 最小元素 的位置
maxIndex : 记录 未排序序列 的 最大元素 的位置
i：用来遍历未排序序列部分
注意：当最小值出现在right处，之前已经交换了arr[maxIndex]与arr[right]，此时arr[maxIndex]存储着最小值，将maxIndex赋给minIndex.

package main

import "fmt"

func main() {
	arr := []int{1, 7, 6, 7, 98, 9, -1, 7, 89, 14, -4, -5, -657}
	selectSort(arr)
	for _, v := range arr {
		fmt.Println(v)
	}
}

func selectSort(arr []int) {
	left, right := 0, len(arr)-1
	for left < right {
		minIndex, maxIndex := left, right
		for i := left; i <= right; i++ {
			if arr[i] < arr[minIndex] {
				minIndex = i
			}
			if arr[i] > arr[maxIndex] {
				maxIndex = i
			}
		}
		swap(arr, maxIndex, right)
		if minIndex == right {
			minIndex = maxIndex
		}
		swap(arr, minIndex, left)
		left++
		right--
	}
}

func swap(arr []int, i, j int) {
	tem := arr[i]
	arr[i] = arr[j]
	arr[j] = tem
}