go插入排序

插入排序思想：

1. 第一个元素认为已有序,i=0 有序
2. 从第二个元素开始排序，i=1 无序
3. 将i的值保存到临时变量里,则会空出一格可替换的位置,current 当前要排序的位置的值
4. 每次i与前一个索引 before元素比较大小，如果i的值current 小于 before的值arr[before] ，则将before后移一位,arr[before+1]=arr[before],第一次移动会占用i的位置,before的空出一个位置
5. 直到没有比cureent的小的元素，替换before+1(+1原因:因为before不比current小,需要把current放在before+1位置)的位置值为
   current

charu.png

package main

import(
    "fmt"
)

func main() {
  arr := []int{999,432,5,4326,2,27,7,72,4,2564}
  sortArr := insertAsort(arr)
  fmt.Println(sortArr)
}

func insertAsort(arr []int) []int {
    if len(arr)<=1 {
        return arr
    }
    //第0个认为是有序的无须排序,从第一个开始比较
    for i := 1; i < len(arr); i++ {//需要循环比较的排序的每个值,拿出来比较一次
        current := arr[i] //当前要排序的元素
        before := i-1
        for before>=0&&current<arr[before] {//拿出第i个与前面的n个元素分别比较大小,
            arr[before+1] = arr[before]
            before--
        }
    arr[before+1] = current  // 直到没有比cureent的小的元素，替换before+1(+1原因:因为before不比current小,需要把current放在before+1位置)的位置值为current
    }
    return arr
}