插入排序

排序简介

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从右向左扫描
3. 如果被扫描的元素（已排序）大于新元素，将该元素右移一位
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

复杂度

• 最佳情况：T(n) = O(n)
• 最坏情况：T(n) = O(n2)
• 平均情况：T(n) = O(n2)
• 空间复杂度：O(1)
• 稳定性：稳定
• 排序方式：In-place

golang实现

package main

import "fmt"

//插入排序
func InsertionSort(arr []int) {
    for i := 1; i < len(arr); i++ {
        temp := arr[i]
        j := i
        for ; j > 0; j-- {
            if arr[j-1] > temp {
                arr[j] = arr[j-1]
            }else {
                break
            }
        }
        arr[j] = temp
        fmt.Println(arr)
    }
}

func main()  {
    arr := []int{33,11,55,7,44,1}
    InsertionSort(arr)
}