六虎

Go 实现希尔排序算法及图解

Go 实现希尔排序算法及图解

作者：

小综哥

在

敞开成长之旅！这是我参加「日新计划 12 月更文挑战」的第20天，点击检查活动概况

耐性和持久胜过剧烈和疯狂。

哈喽大家好，我是陈明勇，今天共享的内容是运用 Go 完成希尔排序算法。假如本文对你有协助，无妨点个赞，假如你是 Go 语言初学者，无妨点个重视，一同成长一同进步，假如本文有过错的地方，欢迎指出！

前语

前篇文章 Go 完成插入排序算法及优化 对插入排序进行了简略的介绍，然后运用 Go 完成插入排序的算法。而本文要介绍的是根据插入排序算法优化之后的高效版——希尔排序。

希尔排序

希尔排序是根据直接插入排序改善的一种高效的版本，也称“缩小增量排序”。它的基本思想是 把记录按下标的一定增量分组，对每组运用直接插入排序算法排序；随着增量逐步减少，每组包括的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

图文解释

Go 实现希尔排序算法及图解

  • 1、增量值 d 为 ⌊数组长度 / 2⌋ = ⌊9 / 2⌋ = 4
    • 分成三组：[6, 4, 2]、[5, 8]、[1, 9]、[7, 3]
      • [6, 4, 2] 经过直接插入排序算法进行排序，最终的成果为：[2, 4, 6]
      • [5, 8] 经过直接插入排序算法进行排序，最终的成果为：[5, 8]
      • [1,9] 经过直接插入排序算法进行排序，最终的成果为：[1, 9]
      • [7, 3] 经过直接插入排序算法进行排序，最终的成果为：[3, 7]
    • 最终的成果为 [2, 5, 1, 3, 4, 8, 9, 7, 6]

Go 实现希尔排序算法及图解

  • 2、增量值 d 为 ⌊d / 2⌋ = ⌊4 / 2⌋ = 2
    • 分成两组：[2, 1, 4, 9, 6]、[5, 3, 8, 7]
      • [2, 1, 4, 9, 6] 经过直接插入排序算法进行排序，最终的成果为：[1, 2, 4, 6, 9]
      • [5, 3, 8, 7] 经过直接插入排序算法进行排序，最终的成果为：[3, 5, 7, 8]
    • 最终的成果为：[1, 3, 2, 5, 4, 7, 6, 8, 9]

Go 实现希尔排序算法及图解

  • 3、增量值 d 为 ⌊d / 2⌋ = ⌊2 / 2⌋ = 1
    • 分成一组：[1, 3, 2, 5, 4, 7, 6, 8, 9]
      • [1, 3, 2, 5, 4, 7, 6, 8, 9] 经过直接插入排序算法进行排序，最终成果为：[1, 2, 3, 4, 5, 6, 7, 8, 9]
    • 最终的成果为：[1, 2, 3, 4, 5, 6, 7, 8, 9]

代码完成

import (
    "fmt"
)
func main() {
    nums := [9]int{6, 5, 1, 7, 4, 8, 9, 3, 2}
    fmt.Println("原数组：", nums)
    fmt.Println("--------------------------------")
    ShellSort(nums)
}
func ShellSort(nums [9]int) {
    for d := len(nums) / 2; d > 0; d /= 2 {
        for i := d; i < len(nums); i++ {
            for j := i; j >= d && nums[j-d] > nums[j]; j -= d {
                nums[j], nums[j-d] = nums[j-d], nums[j]
            }
        }
        fmt.Println(nums)
    }
    fmt.Println("--------------------------------")
    fmt.Println("排序后的数组：", nums)
}

执行成果：

原数组： [6 5 1 7 4 8 9 3 2]
--------------------------------
[2 5 1 3 4 8 9 7 6]
[1 3 2 5 4 7 6 8 9]
[1 2 3 4 5 6 7 8 9]
--------------------------------
排序后的数组： [1 2 3 4 5 6 7 8 9]
  • 第一层循环负责对增量 d 的进行修正
  • 第二层循环和第三层循环相当于对数组进行分组，然后运用直接插入排序算法对每组进行排序

小结

本文对希尔排序进行简略的介绍，然后经过图解演示希尔排序的整个排序进程，最终运用 Go 语言完成希尔排序算法。对于希尔排序里的增量，本文初次去数组长度的一般作为增量值，然后依次折半，直到等于 1；除了这种取值方式，还可以运用 Knuth序列算法去核算增量的值。

更多文章