核心思路:
将数组分成已排序和待排序两部分,将一个元素从待排序插入到有序数组的适当位置,直到所有待排序都插入完成
把第一个元素作为已排序数组,将后面的元素依次与已排序元素从后往前进行比较,如果当前元素小于有序数组元素,有序数组元素往后挪1位,直到大于了就插入到有序数组元素后面
//插入排序
func InsertionSort(arr *[]int){
for i:=1;i<len(*arr);i++{
curKey:=(*arr)[i]
j:=i-1
for curKey<(*arr)[j]{
(*arr)[j+1]=(*arr)[j]
j--
if j<0 {
break
}
}
(*arr)[j+1]=curKey
}
}