算法原理:
將一個記錄插入到已排好序的序列中，從而得到一個新的有序序列（將序列的第一個數據看成是一個有序的子序列，然后從第二個記錄逐個向該有序的子序列進行有序的插入，直至整個序列有序）
算法實現(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)
