算法 - 插入排序

• 源码

• 代码

// 对data进行正向排序
// 1、从第一个元素开始，该元素可以认为已经被排序；
// 2、取出下一个元素，在已经排序的元素序列中从后向前扫描；
// 3、如果该元素（已排序）大于新元素，将该元素移到下一位置；
// 4、重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
// 5、将新元素插入到该位置后；
// 6、重复步骤 2~5。
// 难度系数 O(n^2)
//
func InsertSort(data []int) {
    for i := 1; i < len(data); i++ {
        tmp := data[i]
        // 从后往前扫描
        for j := i; j > 0 && tmp < data[j-1]; j-- {
            // 后和前交换值
            data[j], data[j-1] = data[j-1], tmp
        }
    }
}

• 测试

func TestInsertSort(t *testing.T) {
    data := []int{1, 0, 35, 9, 7, 8, 5, 4, 3, 33}
    fmt.Println("sort before", data)
    sort2.InsertSort(data)
    fmt.Println("sort after", data)
}

• 分析

sort before [1 0 35 9 7 8 5 4 3 33]
-----
i 1 tmp 0
i j data
1 1 [0 1 35 9 7 8 5 4 3 33]
-----
i 2 tmp 35
i j data
-----
i 3 tmp 9
i j data
3 3 [0 1 9 35 7 8 5 4 3 33]
-----
i 4 tmp 7
i j data
4 4 [0 1 9 7 35 8 5 4 3 33]
4 3 [0 1 7 9 35 8 5 4 3 33]
-----
i 5 tmp 8
i j data
5 5 [0 1 7 9 8 35 5 4 3 33]
5 4 [0 1 7 8 9 35 5 4 3 33]
-----
i 6 tmp 5
i j data
6 6 [0 1 7 8 9 5 35 4 3 33]
6 5 [0 1 7 8 5 9 35 4 3 33]
6 4 [0 1 7 5 8 9 35 4 3 33]
6 3 [0 1 5 7 8 9 35 4 3 33]
-----
i 7 tmp 4
i j data
7 7 [0 1 5 7 8 9 4 35 3 33]
7 6 [0 1 5 7 8 4 9 35 3 33]
7 5 [0 1 5 7 4 8 9 35 3 33]
7 4 [0 1 5 4 7 8 9 35 3 33]
7 3 [0 1 4 5 7 8 9 35 3 33]
-----
i 8 tmp 3
i j data
8 8 [0 1 4 5 7 8 9 3 35 33]
8 7 [0 1 4 5 7 8 3 9 35 33]
8 6 [0 1 4 5 7 3 8 9 35 33]
8 5 [0 1 4 5 3 7 8 9 35 33]
8 4 [0 1 4 3 5 7 8 9 35 33]
8 3 [0 1 3 4 5 7 8 9 35 33]
-----
i 9 tmp 33
i j data
9 9 [0 1 3 4 5 7 8 9 33 35]
sort after [0 1 3 4 5 7 8 9 33 35]