排序算法：直接插入排序

算法原理:

将一个记录插入到已排好序的序列中，从而得到一个新的有序序列（将序列的第一个数据看成是一个有序的子序列，然后从第二个记录逐个向该有序的子序列进行有序的插入，直至整个序列有序）

算法实现(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)