插入排序

编码

go

func InsertionSort(data []int) {
	// 遍历待插入元素
	for i, l:=1, len(data); i<l; i++ {
		// 比较,移位
		for k:=i-1; k>=0; k-- {
			// 移动
			if data[k] > data[k+1] {
				data[k+1], data[k] = data[k], data[k+1]
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

分析

  • 平均时间复杂度为O(n^2), 最好时间复杂度为 O(n),最坏为O(n^2)。
  • 空间复杂度为O(1)
  • 稳定排序