1.3 插入排序

努力学习算法 Let's go

概念

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

动图演示

执行代码

package main

import (
    "fmt"
)

func insertionSort(arr []int) []int {
    for i := range arr {  //遍历切片
        preIndex := i - 1 //从第二个数开始
        current := arr[i]
        for preIndex >= 0 && arr[preIndex] > current {
            arr[preIndex+1] = arr[preIndex]// 数字大往后移动
            preIndex -= 1
        }
        arr[preIndex+1] = current // 数字小往前移动
    }
    return arr
}

func main() {
    arr := []int{99,1,5,7,9,23,4,78,88,66,54,10,12}
    insertionSort := insertionSort(arr)
    fmt.Println("insertionSort:",insertionSort)
}

执行结果

insertionSort: [1 4 5 7 9 10 12 23 54 66 78 88 99]

参考LeetCode 与 《代码随想录》及网上资料，code已测试，有问题可评论。保持好的状态，坚持学习，滴水穿石！