插入排序代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func InsertionSort(array []int64) time.Duration {
start := time.Now()
// 从第二个数开始往前逐个比对
for j := 1; j < len(array); j++ {
// 如[i]小于[i-1]时将两者位置互换
// 注意: for循环中增加的array[i] < array[i-1]判断目是因为
// 经过插入排序后,[i-1]位置之前的数值都变为有序
// [i] > [i-1]即代表[i]大于[:i]中的所有数值
// 所以[i]只需要比对一次即可退出此次循环,使内部循环实现O(1)
// 因此数组在正序状态下时间复杂度为O(n),即最优时间复杂度
for i := j; i > 0 && array[i] < array[i-1]; i-- {
array[i], array[i-1] = array[i-1], array[i]
}
}
end := time.Now()
during := end.Sub(start)
return during
}

插入排序算法平均时间复杂度O(n2),最好时间复杂度为O(n),最差时间复杂度为O(n2)
空间复杂度O(1),稳定性为稳定
性能在简单排序中处于最优,花费时间大概是冒泡排序的一半,略快于选择排序