跟着动画学Go数据结构之希尔排序 #私藏项目实操分享#

简介: 跟着动画学Go数据结构之希尔排序 #私藏项目实操分享#

希尔排序

在插入排序中,在待排序序列的记录个数比较少,而且基本有序,则排序的效率较高。

1959 年,Donald Shell 从“减少记录个数” 和 “基本有序” 两个方面对直接插入排序进行了改进,提出了希尔排序算法。

希尔排序又称为“缩小增量排序”。即将待排序记录按下标的一定增量分组(减少记录个数),对每组记录使用直接插入排序算法排序(达到基本有序);随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1,整个序列基本有序,再对全部记录进行一次直接插入排序。

算法思想

Shell 排序是一种高效的排序算法,基于插入排序算法。这种算法避免了插入排序中的大量移动,如果较小的值在最右边,就必须移到最左边。较小的值在最右边,必须移到最左边。

算法步骤:

  1. 设待排序的记录存储在数组 array[1...n]  中,增量序列为 {g1, g2, ..., gt} , n>g1>g2>...>gt=1
  2. 第一趟增量 g1, 所有间隔为 g1 的记录分在一组,对每组记录进行插入排序。
  3. 第二趟取增量 g2,所有间隔为 g2 的记录分在一组,对每组记录进行插入排序。
  4. 依次进行下去,直到所取增量 gt = 1,所有记录在一组中进行插入排序。

图解算法

假设我们有一个数组: [7, 4, 3, 5, 2, 1, 6] :

第一次希尔排序间隔为3时:

image.png

第二次希尔排序间隔为2时:

image.png

第三次希尔排序间隔为1时:

image.png

Go 代码实现:

package main
import "fmt"
func swap(array []int, a int, b int) {
    array[a] = array[a] + array[b]
    array[b] = array[a] - array[b]
    array[a] = array[a] - array[b]
}
func shellSort(array []int, length int) {
    for gap := length / 2; gap > 0; gap-- {
        for i := gap; i < length; i++ {
            var j = i
            for {
                if j-gap < 0 || array[j] >= array[j-gap] {
                    break
                }
                swap(array, j, j-gap)
                j = j - gap
            }
        }
    }
}
func main() {
    nums := []int{7, 4, 3, 5, 2, 1, 6}
    length := len(nums)
    shellSort(nums, length)
    for i := 0; i < length; i++ {
        fmt.Println(nums[i])
    }
}

运行代码结果为:

[Running] go run "e:\Coding Workspaces\LearningGoTheEasiestWay\Go 数据结构\希尔排序\main.go"
1
2
3
4
5
6
7

总结

image.png

相关文章
|
2月前
|
JSON 运维 Go
Go 项目配置文件的定义和读取
Go 项目配置文件的定义和读取
|
2月前
|
JSON 中间件 Go
go语言后端开发学习(四) —— 在go项目中使用Zap日志库
本文详细介绍了如何在Go项目中集成并配置Zap日志库。首先通过`go get -u go.uber.org/zap`命令安装Zap,接着展示了`Logger`与`Sugared Logger`两种日志记录器的基本用法。随后深入探讨了Zap的高级配置,包括如何将日志输出至文件、调整时间格式、记录调用者信息以及日志分割等。最后,文章演示了如何在gin框架中集成Zap,通过自定义中间件实现了日志记录和异常恢复功能。通过这些步骤,读者可以掌握Zap在实际项目中的应用与定制方法
go语言后端开发学习(四) —— 在go项目中使用Zap日志库
|
2月前
|
API
企业项目迁移go-zero实战(二)
企业项目迁移go-zero实战(二)
|
2月前
|
搜索推荐 算法 Go
深入探索堆:Go语言中的高效数据结构
深入探索堆:Go语言中的高效数据结构
|
2月前
|
JSON 缓存 监控
go语言后端开发学习(五)——如何在项目中使用Viper来配置环境
Viper 是一个强大的 Go 语言配置管理库,适用于各类应用,包括 Twelve-Factor Apps。相比仅支持 `.ini` 格式的 `go-ini`,Viper 支持更多配置格式如 JSON、TOML、YAML
go语言后端开发学习(五)——如何在项目中使用Viper来配置环境
|
2月前
|
算法 程序员 编译器
Go deadcode:查找没意义的死代码,对于维护项目挺有用!
Go deadcode:查找没意义的死代码,对于维护项目挺有用!
|
2月前
|
缓存 JavaScript 前端开发
为开源项目 go-gin-api 增加 WebSocket 模块
为开源项目 go-gin-api 增加 WebSocket 模块
34 2
|
2月前
|
Kubernetes API Go
企业项目迁移go-zero实战(一)
企业项目迁移go-zero实战(一)
|
2月前
|
存储 Prometheus 中间件
2020最佳人气项目之Go Web框架
2020最佳人气项目之Go Web框架
|
2月前
|
Java Go API
我用go-zero开发了第一个线上项目
我用go-zero开发了第一个线上项目