插入排序原理

插入排序又叫扑克牌排序，我个人觉得扑克牌排序(PorkerSort)要比InsertionSort这个名字更让人理解这个排序的过程。即每次将未排序数据元素比较插入到已排序的数据组中的合适的位置。

算法效率

时间复杂度O(n^2)，空间复杂度O(1)
排序时间与输入有关：输入的元素个数；元素已排序的程度。
最佳情况，输入数组是已经排好序的数组，运行时间是n的线性函数； 最坏情况，输入数组是逆序，运行时间是n的二次函数。

稳定性

直接插入排序是稳定排序算法

插入排序的Go语言实现代码

package main

import "fmt"
import "time"
import "math/rand"

// 插入排序
func main(){
    rand.Seed(time.Now().UnixNano())

    numArr := make([]int,10)

    for i := 0; i < 10; i++ {
        numArr[i] = rand.Intn(100)
        // numArr = append(numArr,rand.Intn(100))
    }

    fmt.Println(numArr)

    for i := 1; i < len(numArr); i++ {

        tmp := numArr[i]
        j := i-1
        // go没有while和do while，只能用for
        // 此处不能用 numArr[i]和numArr[j]比较，因为原i位置在第一次修改后，值已改变
        for j >= 0 && tmp > numArr[j] {
            numArr[j+1] = numArr[j]
            j--
        }
        numArr[j+1] = tmp
    }
    fmt.Println(numArr)
}