网站首页 > 精选教程 正文

算法实现(go语言):

func insertSort(input []int) []int{

length := len(input)

if length <= 0 {

return input

}

for i:= 1 ;i < length; i++{

tmp := input[i]

var j int

for j= i-1; j >= 0 ; j-- {

//因为是有序的，比tmp小，所以tmp要直接放在最后

if input[j] <= tmp {

break

}

//tmp大,在tmp后的都要后移一位

if input[j] > tmp {

input[j+1] = input[j]

}

}

input[j + 1] = tmp

}

return input

}

复杂度

时间复杂度： 两层循环，外层循环n-1次。第2层循环次数依赖于在第i个记录前的元素中小于第i个记录元素的个数。

最差情况:每个元素都要移动到最前面(逆序的情况),时间复杂度为O(n^2)

最好情况:第2层循环直接break(已经正序的情况),时间复杂度为O(n)

空间复杂度：没有利用新的数组来帮助完成排序算法，所以空间复杂度为O(1)