写点什么

跟着动画学 Go 数据结构之希尔排序

作者:宇宙之一粟
  • 2021 年 12 月 19 日
  • 本文字数:1184 字

    阅读完需:约 4 分钟

跟着动画学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 时:

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

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

Go 代码实现:

package mainimport "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 = gap / 2 {        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"1234567
复制代码

总结

时间复杂度:希尔排序的时间复杂度和增量序列有关,不同的增量序列其时间复杂度不同。当 n 处于某个特定的范围内,希尔排序的时间复杂度为 ,希尔排序复杂度的下界是 ,最坏情况下的时间复杂度为 ,但是,希尔排序还是没有快速排序快。

空间复杂度:希尔排序在分组进行插入排序时使用了一个辅助空间 j,空间复杂度为 

稳定性:希尔排序的分组导致不同组间的相同数字可能会调换位置,所以希尔排序是不稳定的排序算法。

发布于: 3 小时前阅读数: 6
用户头像

宇宙古今无有穷期,一生不过须臾,当思奋争 2020.05.07 加入

混迹于江湖,江湖却没有我的影子 热爱技术,专注于后端全栈,轻易不换岗 拒绝内卷,工作于软件工程师,弹性不加班 热衷分享,执着于阅读写作,佛系不水文 各大平台同名 CSDN、51CTO、掘金、知乎、公众号、简书。。。

评论

发布
暂无评论
跟着动画学Go数据结构之希尔排序