package main

import "fmt"

func main() {
	arr := []int{10, 2, 6, 8, 7, 5, 3, 4, 1, 9}
	insertSort(arr)
	fmt.Println(arr)
}

func insertSort(arr []int) {
	for i := 1; i < len(arr); i++ { // 控制循环的次数
		tmp, j := arr[i], i //记录当前数据
		if arr[j-1] > tmp {
			//寻找前面的小于当前，都移到后面
			for j >= 1 && arr[j-1] > tmp {
				arr[j] = arr[j-1]
				j--
			}
		}
		arr[j] = tmp
	}

}