《算法导论》的Go实现 2.1 插入排序

我们首先介绍插入排序，对于少量元素的排序，它是一个有效的算法。插入排序的工作方式像是对一手扑克牌做排序。开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌正确的位置，我们需要从右到左地将这张牌与已在手中的每张牌进行比较。注意，如此操作会使得拿在手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌。

代码：

package main

import "fmt"

func insertionSort(slice []int) {
    for i := 1; i < len(slice); i++ {
        key := slice[i]
        j := i - 1
        for ; j >= 0; j-- {
            if slice[j] > key {
                slice[j+1] = slice[j]
            } else {
                break
            }
        }
        slice[j+1] = key
    }
}

func main() {
    slice := []int{5, 2, 4, 6, 1, 3}
    fmt.Println(slice)
    insertionSort(slice)
    fmt.Println(slice)
}

输出：

[5 2 4 6 1 3]
[1 2 3 4 5 6]