文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Go语言数据结构之希尔排序示例详解

2024-04-02 19:55

关注

希尔排序

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

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

希尔排序又称为“缩小增量排序”。即将待排序记录按下标的一定增量分组(减少记录个数),对每组记录使用直接插入排序算法排序(达到基本有序);

随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1,整个序列基本有序,再对全部记录进行一次直接插入排序。

算法思想

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

算法步骤:

图解算法

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

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

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

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

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 = 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"
1
2
3
4
5
6
7

总结

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

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

以上就是Go语言数据结构之希尔排序示例详解的详细内容,更多关于Go 数据结构希尔排序的资料请关注编程网其它相关文章!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯