golang 写个插入排序

追风骚年 · · 374 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

有点上瘾，再来写一个。

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤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！

有疑问加站长微信联系（非本文作者）