算法原理:
將一個(gè)記錄插入到已排好序的序列中，從而得到一個(gè)新的有序序列（將序列的第一個(gè)數(shù)據(jù)看成是一個(gè)有序的子序列，然后從第二個(gè)記錄逐個(gè)向該有序的子序列進(jìn)行有序的插入，直至整個(gè)序列有序）
算法實(shí)現(xiàn)(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-- {
//因?yàn)槭怯行虻模萾mp小，所以tmp要直接放在最后
if input[j] <= tmp {
break
}
//tmp大,在tmp后的都要后移一位
if input[j] > tmp {
input[j+1] = input[j]
}
}
input[j + 1] = tmp
}
return input
}
復(fù)雜度
時(shí)間復(fù)雜度： 兩層循環(huán)，外層循環(huán)n-1次。第2層循環(huán)次數(shù)依賴于在第i個(gè)記錄前的元素中小于第i個(gè)記錄元素的個(gè)數(shù)。
最差情況:每個(gè)元素都要移動(dòng)到最前面(逆序的情況),時(shí)間復(fù)雜度為O(n^2)
最好情況:第2層循環(huán)直接break(已經(jīng)正序的情況),時(shí)間復(fù)雜度為O(n)
空間復(fù)雜度：沒有利用新的數(shù)組來幫助完成排序算法，所以空間復(fù)雜度為O(1)
