手把手教媳妇-复习下插入排序算法

思路：插入排序思路是将一个无序表分为有序和无序两部分，依次将无序表中的元素放入有序表中正确的位置，从而无序部分变长，有序部分变短，直至全部有序

//插入排序法 默认第一个元素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:插入排序的思路中可以分析，一个无序列表的的有序化元素越多，效率越高