KN郑某某

Appearance

简介 ​

三大 “民工”(意为连毫无闲暇时间的民工一族都耳熟能详) 排序算法

1. 选择排序 ​

  • 算法实现
func SelectionSort(list []int) {
	length, idx := len(list), 0
	for left := 0; left < length; left++ {
		idx = left
		for right := left + 1; right < length; right++ {
			// 找到最小值所在的位置
			if list[right] < list[idx] {
				idx = right
			}
		}
		if idx != left {
			// 最小值所在的位置不是当前位置相同，交换
			list[left], list[idx] = list[idx], list[left]
		}
	}
}
  • 测试代码
func main() {
	list := []int{8, 4, 2, 9, 10, -3, 3, 20, 15, -1}
	SelectionSort(list)
	fmt.Println(list)
}
  • 排序结果

[-3 -1 2 3 4 8 9 10 15 20]

  • 时间复杂度

O(n^2)

2. 冒泡排序 ​

  • 算法实现
func BubbleSort(list []int) {
	length := len(list)
	for left := 0; left < length; left++ {
		for right := left + 1; right < length; right++ {
			if list[left] > list[right] {
				list[left], list[right] = list[right], list[left]
			}
		}
	}
}
  • 测试代码
func main() {
	list := []int{8, 4, 2, 9, 10, -3, 3, 20, 15, -1}
	BubbleSort(list)
	fmt.Println(list)
}
  • 排序结果

[-3 -1 2 3 4 8 9 10 15 20]

  • 时间复杂度

O(n^2)

3. 插入排序 ​

  • 算法实现
func InsertionSort(list []int) {
	length := len(list)
	for left := 0; left < length-1; left++ {
		for right := left + 1; right > 0; right-- {
			// 逐步与前面的比较
			if list[right-1] > list[right] {
				list[right-1], list[right] = list[right], list[right-1]
			} else {
				break
			}
		}
	}
}
  • 测试代码
func main() {
	list := []int{8, 4, 2, 9, 10, -3, 3, 20, 15, -1}
	InsertionSort(list)
	fmt.Println(list)
}
  • 排序结果

[-3 -1 2 3 4 8 9 10 15 20]

  • 时间复杂度

O(n^2)