golang 写个希尔排序


本文摘自网络,作者,侵删。

希尔排序非常的牛,听说是第一个打破时间复杂度我 n² 的算法,通过一个区间不断缩小,由远及近,最终达到有序状态,也可以称为加强版的分组插入排序。

算法描述

  • 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
  • 按增量序列个数k,对序列进行k 趟排序;
  • 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的
    长度。

先回顾一下插入排序

func insertionSort(arr []int) {
    for i := 1; i < len(arr); i++ {
        for j := i; j > 0 && arr[j] < arr[j-1]; j-- {
            arr[j], arr[j-1] = arr[j-1], arr[j]
        }
    }
}

希尔排序的精髓在于增量的选择,教科书上一般都是不断除以 2,最后达到1,这样做的问题是,奇数位和偶数位的数字始终不能比较。增量选择也是这个排序的魅力所在,看多很多资料给到的是 3x+1为一个合适的分组状态,所以我们先选择 3x+1 ,更多分组可以参照参考文档。

func shellSort(arr []int) {
    h := 1
    for h < len(arr)/3 { 
        h = 3*h + 1
    }

    for h >= 1 {
        for i := h; i < len(arr); i++ {
            for j := i; j >= h && arr[j] < arr[j-h]; j -= h {
                arr[j], arr[j-h] = arr[j-h], arr[j]
            }
        }
        h /= 3
    }
}

希尔排序相对于插入排序来说,外层套了一个递减变量,
希尔排序的时间复杂度为 o(n^k) (k=1.3~2.0),具体 1.3 怎么算出来的,很玄学没找到地方列出推导过程,2 是因为如果整体逆序的情况下的最差情况。

参考文档

  • 希尔排序增量序列简介
  • 知乎:希尔排序

本文来自:简书

感谢作者:追风骚年

查看原文:golang 写个希尔排序

相关阅读 >>

Go - httpclient 常用操作

Golang 语言的标准库 log 包怎么使用?

Golang如何清空map

Golang array slice操作示例 去重 插入 删除 清空

jenkins构建Go及java项目

如何实现Golang语言的多态

Golang 创建型设计模式 建造者模式

Go bool

记录Go的循环遍历使用小坑

搭建vscode Golang开发环境

更多相关阅读请进入《Go》频道 >>




打赏

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,您说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

分享从这里开始,精彩与您同在

评论

管理员已关闭评论功能...

    正在狠努力加载,请稍候...