4、Gnome sort侏儒排序

冒泡和插入排序结合
适合大部分排序完成后再随机插入小部分的再排序

// 侏儒排序
func GnomeSort(arr []int)  {
    i := 1
    for i < len(arr) {
        if arr[i] >= arr[i-1] {
            i++
        } else {
            arr[i], arr[i-1] = arr[i-1], arr[i] // 排序不正确前后交换
            if i > 1 { // 游标大于1向后移，和前一个数对比
                i--
            }
        }
    }
}

func main()  {
    arr := []int{2, 3, 4, 5, 7, 9, 4, 10, 0}
    GnomeSort(arr)
    fmt.Println(arr)
}