排序算法之选择排序(go语言实现)

1、选择排序原理

选择排序（Selection sort）是一种简单直观的排序算法。它每次在待排序列表中选出最大（最小）元素，放到有序（已排序）列表的末尾，直到待排序列表中所有的元素全部放到有序列表为止。

2、go代码实现

package sort

/*
	选择排序
*/
import "algorithms/util"

/*
	常规选择排序（从左端开始建立有序列表进行最大或最小值排序）
*/
func SelectionSort(arr []int) []int {
	len := len(arr)
	for i := 0; i < len-1; i++ {
		//取待排序列表中第一个元素的位置，并认为其是最大或最小值
		minIndex := i
		for j := i + 1; j < len; j++ {
			//依次与待排序列表中剩余的元素进行比较，找出最大值或最小值的位置并赋值给minIndex
			if arr[j] < arr[minIndex] {
				minIndex = j
			}
		}
		//把最小值放到左端有序列表末尾（i的位置）
		util.Swap(arr, i, minIndex)
	}

	return arr
}

/*
	优化选择排序（从两端开始建立有序列表进行最大和最小值排序，左端依次放最小值，右端依次放最大值）
*/
func SelectionSort2(arr []int) []int {
	len := len(arr)
	//因为该算法是从两端同时排序，所以外层循环只取一半元素即可
	for i := 0; i < len/2; i++ {
		//取待排序列表中第一个元素的位置，并认为其是最大和最小值
		minIndex := i
		maxIndex := i
		//依次与待排序列表中剩余的元素进行比较，找出最大值和最小值的位置并赋值给maxIndex，minIndex
		for j := i + 1; j < len-i; j++ {
			if arr[j] < arr[minIndex] {
				minIndex = j
			}
			if arr[j] > arr[maxIndex] {
				maxIndex = j
			}
		}
		//把最小值放到左端有序列表末尾（i的位置）
		util.Swap(arr, i, minIndex)
		//由于i和minIndex的值进行了交换，所以如果maxIndex为i的话，它要去minIndex取值
		if maxIndex == i {
			maxIndex = minIndex
		}
		//把最大值放到右端有序列表的开头（len-1-i的位置）
		util.Swap(arr, len-1-i, maxIndex)
	}

	return arr
}

package util

// 交换两个值
func Swap(arr []int, a, b int) {
	arr[a], arr[b] = arr[b], arr[a]
}

3、时间复杂度和空间复杂度

选择排序的平均时间复杂度也是 O(n^2)，空间复杂度为常数阶 O(1)。

由于每个元素归位都需要和待排序列表中的元素比较，最坏情况下需要进行n(n?1)/2次比较，因此时间复杂度为O(n2)。

空间复杂度方面，选择排序是一个原地排序算法，其空间复杂度为O(1)；这意味着插入排序在排序过程中，除了输入数据本身所需的存储空间外，不会使用额外的存储空间。

4、选择排序的稳定性

由于每次交换元素可能会导致相同元素之前位置发生变化，所以选择排序是一种不稳定的排序算法。?