原理
希尔排序, 就是按某个增量值对数据进行分组, 每组单独排序好后, 再缩小这个增量, 然后按新增量对数据分组后每个分组再各自排序. 最终增加缩小到 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]
- }
- }
- }
运行结果
[golang] 数据结构 - 希尔排序
来源: http://www.bubuko.com/infodetail-2703180.html