GO语言希尔排序

希尔排序
希尔排序，也称递减增量排序算法，是插入排序的一种高速而稳定的改进版本。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

1、插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率

2、但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位>

func shellshort(items []int) {
    var (
        n    = len(items)
        gaps = []int{1}
        k    = 1
    )
    for {
        gap := pow(2, k) + 1
        if gap > n-1 {
            break
        }
        gaps = append([]int{gap}, gaps...)
        k++
    }
    for _, gap := range gaps {
        for i := gap; i < n; i += gap {
            j := i
            for j > 0 {
                if items[j-gap] > items[j] {
                    items[j-gap], items[j] = items[j], items[j-gap]
                }
                j = j - gap
            }
        }
    }
}
func pow(a, b int) int {
    p := 1
    for b > 0 {
        if b&1 != 0 {
            p *= a
        }
        b >>= 1
        a *= a
    }
    return p
}