python实现希尔排序算法

  1. 云栖社区>
  2. python技术进阶>
  3. 博客>
  4. 正文

python实现希尔排序算法

python之战 2019-04-18 23:53:35 浏览709
展开阅读全文

希尔排序是插入排序的一种又称“缩小增量排序”,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

希尔排序的核心是对步长的理解,步长是进行相对比较的两个元素之间的距离,随着步长的减小,相对元素的大小会逐步区分出来并向两端聚拢,当步长为1的时候,就完成最后一次比较,那么序列顺序就出来了。

2019-04-18-23_53_09.png

如上面实例:第一次排序步长为5,那么需要比较的元素对为:9-4 1-8 2-6 5-3 7-5,只需要将这几组元素比比较并交换位置;然后开始第二轮的比较。

def shell_sort(items):
    """
    希尔排序
    :param items: 
 

网友评论

登录后评论
0/500
评论
python之战
+ 关注
所属云栖号: python技术进阶