python实现希尔排序算法-阿里云开发者社区

开发者社区> python之战> 正文

python实现希尔排序算法

简介: 希尔排序是插入排序的一种又称“缩小增量排序”,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
+关注继续查看

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

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至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: 
    :return: 
    """

    n = len(items)
    step = n // 2
    while step > 0:
        for cur in range(step, n):
            i = cur
            while i >= step and items[i-step] > items[i]:
                items[i - step], items[i] = items[i], items[i-step]
                i -= step
        step = step // 2


不需要大量的辅助空间,和归并排序一样容易实现。希尔排序是基于插入排序的一种算法,在此算法基础之上增加了一个新的特性,提高了效率。希尔排序没有快速排序算法快,因此中等大小规模数据排序中表现良好,对规模非常大的数据排序不是最优选择。

希尔算法在最坏的情况下和平均情况下执行效率相差不是很多,与此同时快速排序在最坏的情况下执行的效率会非常差,几乎任何排序工作在开始时都可以用希尔排序,本质上讲,希尔排序算法是直接插入排序算法的一种改进,减少了其复制的次数,速度要快很多。 

2019-04-18-23_53_09.png

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
一文详解神经网络 BP 算法原理及 Python 实现
  什么是梯度下降和链式求导法则 假设我们有一个函数 J(w),如下图所示。 梯度下降示意图 现在,我们要求当 w 等于什么的时候,J(w) 能够取到最小值。从图中我们知道最小值在初始位置的左边,也就意味着如果想要使 J(w) 最小,w的值需要减小。
2697 0
小记 用python进行排序
Linux 中可以使用 sort 进行排序,python中也一样,那么怎样实现把一个数字的 list 从小到大排序,然后写入文件,然后从文件中读取出来文件内容,然后反序,再追加到文件的下一行中呢? 思路如下: 1、取一个列表内容 2、对列表内容使用 sort 进行排序,并打...
767 0
python实现希尔排序算法
希尔排序是插入排序的一种又称“缩小增量排序”,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
1146 0
python链表冒泡排序、二叉树顺序递归遍历、顺序表的快排
一、python实现链表冒泡排序 - 冒泡排序的概念:冒泡排序是一种交换排序,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直至没有反序的记录为止。
1347 0
python实现插入排序算法
插入排序,其原理是通过构建一个初始的有序序列,然后从无需序列中抽取元素,插入到有序序列的相对排序位置,就像将一堆编号混乱的书,一本一本的放到书架上,找到上下编号之间的位置插入,最后完成整理。 python实现插入排序并不难,从第二个位置开始遍历,与它前面的元素相比较,如果比前面元素小就交换位置,实...
832 0
关于一道面试题的极其无聊的python算法实现
题目是这样的: 某科技公司两位科学家(甲、乙)去吃饭,坐在一家酒店靠近街道的窗口座位吃饭,在等待上菜的过程中,闲极无聊,甲向乙出了一道猜三个女儿年龄的题目。
1037 0
【大创_社区划分】——PageRank算法的解析与Python实现
一、什么是pagerank PageRank的Page可是认为是网页,表示网页排名,也可以认为是Larry Page(google 产品经理),因为他是这个算法的发明者之一,还是google CEO(^_^)。
1100 0
《机器学习实战》k最近邻算法(K-Nearest Neighbor,Python实现)
============================================================================================ 《机器学习实战》系列博客是博主阅读《机器学习实战》这本书的笔记,包含对其中算法的理解和算法的Pyt...
1582 0
+关注
python之战
专注python学习与应用擅长爬虫、web、全栈,专注RPA技术实施;(个人公号:Python之战)
90
文章
0
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载