golang 写个插入排序

有点上瘾，再来写一个。

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置后；
6. 重复步骤2~5。

我在写插入排序的时候，一下写了 3 个版本，经测试都是可以使用，只是排序和排序之间越来越像。

func insertionSort(arr []int) {
    for i := 1; i < len(arr); i++ {
        // 无序数组
        c := arr[i]
        for j := i - 1; j >= 0; j-- {
            // 有序数组
            if arr[j] > c {
                arr[j+1], arr[j] = arr[j], arr[j+1]
                fmt.Printf("c=%d j=%d arr=%x \n", c, arr[j], arr)
            }
        }
    }
}

写完看了看其他语言的实现，觉得自己的不是插入排序，我也不知道这是啥排序反正是能排序。

func insertionSort2(arr []int) {
    for i := 1; i < len(arr); i++ {
        // 无序数组
        c := arr[i]
        minj := -1
        for j := i - 1; j >= 0; j-- {
            // 有序数组
            if arr[j] > c {
                minj = j
                arr[j+1] = arr[j]
                fmt.Printf("c=%d j=%d arr=%x \n", c, arr[j], arr)
            }
        }
        if minj != -1 {
            arr[minj] = c
        }
    }
}

写了第二个版本，发现搞出了太多变量，继续优化了一下

func insertionSort3(arr []int) {
    for i := 1; i < len(arr); i++ {
        // 无序数组
        c := arr[i]
        j := i - 1
        for (j >= 0) && (arr[j] > c) {
            // 有序数组
            arr[j+1] = arr[j]
            j--
        }
        arr[j+1] = c // 这里因为前面 -1，+1 弥补一下
    }
}

end！

2021年01月21日13:05:23
发现，第一种写法乃和算法导论中的写法不谋而和，算法导论原版

func insertionSort(arr []int) {
    for i := 1; i < len(arr); i++ {
        for j := i; j > 0 && arr[j] < arr[j-1]; j-- {
            arr[j], arr[j-1] = arr[j-1], arr[j]
        }
    }
}