[golang]数据结构-希尔排序-创新互联

除了上篇介绍的二分插入排序，还有这次介绍的希尔排序(Shell's Sort)，也是对直接插入排序算法的优化。

创新互联建站是一家以网站建设公司、网页设计、品牌设计、软件运维、成都网站营销、小程序App开发等移动开发为一体互联网公司。已累计为成都门窗定制等众行业中小客户提供优质的互联网建站和软件开发服务。

原理
希尔排序，就是按某个增量值对数据进行分组，每组单独排序好后，再缩小这个增量，然后按新增量对数据分组后每个分组再各自排序。最终增加缩小到1的时候，排序结束。所以希尔排序又叫缩小增量排序(Diminishing Increment Sort)

关于增量
最佳增量值的选择其实是个数学难题，有兴趣的可以自己搜下相关资料。
常用的增量有 n/2(这个又叫希尔增量)、n/3、2^k-1(hibbard增量)等，实际使用中稍微改版增量也可能使排序的性能产生很大的波动。
比如使用n/2的增量，就是初始增量就是 length/2 ,第二轮分组时就再除2：length/4，直至增量值变成1

流程
假设有个数组：[8,12,6,33,12,5,4,94,63,23,75,22,43,27,46]，以n/2为增量，那么整个排序流程就是这样的：

复杂度
不同增量复杂度不同。n/2时平均的时间复杂度为O(n^2)。
相较直接插入排序，希尔排序减少了比较和交换的次数，在中小规模的排序中，性能表现较好。但随着数据量增大，希尔排序与其他更好的排序算法（快排、堆排、并归等）仍有较大差距。

代码

package main

import (
    "fmt"
    "time"
    "math/rand"
)

func main() {
    var length = 15
    var list []int

    // 以时间戳为种子生成随机数，保证每次运行数据不重复
    r := rand.New(rand.NewSource(time.Now().UnixNano()))
    for i := 0; i < length; i++ {
        list = append(list, int(r.Intn(1000)))
    }
    fmt.Println(list)

    // 这里就以n/2为增量z
    gap := 2
    step := length / gap

    for step >= 1 {
        // 这里按步长开始每个分组的排序
        for i := step; i < length; i++ {
            // 将按步长分组的子队列用直接插入排序算法进行排序
            insertionSortByStep(list, step)
        }
        // 完成一轮后再次缩小增量
        step /= gap

        // 输出每轮缩小增量各组排序后的结果
        fmt.Println(list)
    }
}

// 这里把上篇直接选择排序的算法抽出来，并将步长从1改成step
func insertionSortByStep(tree []int, step int) {
    for i := step; i < len(tree); i++ {
        for j := i; j >= step && tree[j] < tree[j-step]; j -= step {
            tree[j], tree[j-step] = tree[j-step], tree[j]
        }
    }
}

运行结果

创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。

分享标题：[golang]数据结构-希尔排序-创新互联
文章位置：http://bzwzjz.com/article/eedoe.html