3.15 选择排序

1. 选择排序

遍历的时候寻找最大的值，完成遍历后把他放在合适的位置。 相对于冒泡排序来说减少了交换的次数

2. 特点

• 稳定性：不稳定
• 原地排序
• 时间复杂度：O（n²）
• 空间复杂度：O（1）

3. 过程

4. 实现

//O(N²)
func SelectionSort(data []model.Comparable) {
	//data[0...i)是有序的；data[i...n)是无序的
	//每经过一次外层循环，data[i]这个元素就是排好序的以后都不会边
	for i := 0; i < len(data); i++ {
		minIndex := i
		//内层循环是在arr[i...n)中找到最小值
		for j := i + 1; j < len(data); j++ {
			if data[j].CompareTo(data[minIndex]) < 0 {
				minIndex = j
			}
		}
		util.Swap(data, minIndex, i)
	}
}

4.1. 测试

func TestSelectionSort(t *testing.T) {
	e1 := model.NewElement(1)
	e2 := model.NewElement(2)
	e3 := model.NewElement(3)
	data := []model.Comparable{e2, e1, e3}
	fmt.Println(data)

	SelectionSort(data)
	fmt.Println(data)
}

5. 参考

• 排序算法稳定性_百度百科