该排序按照升序讲解。

基本思想

将所有的数据分为有未排序区域和已排序区域，每次从已排序区域中拿出一个元素将其插入到已排序区域，直到未排序区域为空，排序完成。

复杂度分析

时间复杂度

最坏: O(n²) 完全逆序
最好: O(n) 完全有序
平均: O(n²)

空间复杂度

O(1)

稳定性

相同元素均放到后边则可以保证相同元素顺序不变，所以该排序算法稳定。

参考代码

//插入排序
func insertSortAsc(value common.Value) {
    len := value.Len()
    for i := 1; i < len; i++ {
        for j := i - 1; j >= 0; j-- {
            if value.Less(j+1, j) {
                value.Swap(j+1, j)
            } else {
                break
            }
        }
    }
}

插入优与冒泡

• 冒泡移动复杂
• 冒泡比较次数较多