思路：插入排序思路是将一个无序表分为有序和无序两部分，依次将无序表中的元素放入有序表中正确的位置，从而无序部分变长，有序部分变短，直至全部有序
//插入排序法 默认第一个元素array[0]为有序部分，后面的是无序部分
func InsertSort(array []int) {
//i 循环遍历无序部分中的元素
for i := 1; i < len(array); i++ {
//tmp 标识无序部分的第一个元素
tmp := array[i]
//j 标识有序部分的最后一个位置
j := i - 1
//从后向前遍历有序部分，依次与tmp比较，
//比tmp大的则向后依次移动，直到满足 array[j]比tmp小，则退出循环
for j >= 0 && array[j] > tmp {
array[j+1] = array[j]
j--
}
// (由小到大排列)此时j位置的元素比 tmp 小，tmp应该处于j+1的位置
array[j+1] = tmp
}
}
测试
// 插入排序法
func TestInsertSort(t *testing.T) {
la := []int{72, 6, 57, 88, 60, 42, 83, 73, 48, 85}
InsertSort(la)
}
结果
1.png
ps:插入排序的思路中可以分析，一个无序列表的的有序化元素越多，效率越高
