插入排序(Insertion Sort)

插入排序在生活中最经典的应用就是打扑克牌时整理牌的过程。
其原理可以概括为：将数组划分为有序区间和未排序区间，如下图所示，左侧为有序区间，右侧为未排序区间。对于未排序的数据，在有序区间中由后向前扫描，找到相应位置并插入。
插入排序是动态地往数组中添加数据，因此可以保持集合中的数据一直有序。

动画演示

分析

• 空间复杂度

由于不需要额外的存储空间，因此空间复杂度为

• 时间复杂度

• 稳定性

在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。

代码实现

func insertionSort(nums []int) {
    if len(nums) < 2 {
        return
    }
    for i := 1; i < len(nums); i++ {
        var val = nums[i]
        var j = i - 1
        for ; j >= 0; j-- {
            if nums[j] > val {
                nums[j+1] = nums[j]
            } else {
                nums[j+1] = val
                break
            }
        }
        nums[j+1] = val
    }
}