数据结构和算法-希尔排序（增量序列 算法实现 性能分析 稳定性）

发布时间：2024年01月05日

文章目录

希尔排序

基本有序，就是存在有序的子序列
在这里插入图片描述
通过增量4得到各个子表
在这里插入图片描述
对各个子表分别进行插入排序
在这里插入图片描述
缩小增量，再除2，此时的子表
在这里插入图片描述
对各个子表插入排序
在这里插入图片描述
缩小增量，再除2
此时子表就是整个表，对整个表开始插入排序
在这里插入图片描述

过程小结

在这里插入图片描述

增量序列不是固定的

在这里插入图片描述

算法实现

对每个子表做插入排序时，开始直接从子表的第二个元素开始，此时第二个元素为d+1开始，遍历到n

然后对比，只不过都是按增量序列的差来对比对应位置。移动位置也需要按增量序列的差来移动

最后找到大于的了，需要将此时比对的元素位置加上增量
在这里插入图片描述

算法性能分析

不同增量序列，排序的趟数和每趟的比对次数不一样
最坏增量为1和插入排序一样
在这里插入图片描述

稳定性

因为需要增量d来找到元素位置，用链表实现比较麻烦，所以仅适用于顺序表
在这里插入图片描述

小结

在这里插入图片描述

文章来源:https://blog.csdn.net/llovewuzhengzi/article/details/135414743
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
最新文章