声明
本公众号所有内容,均属微信公众号: 开源优测 所有,任何媒体、网站或个人未经授权不得转载、链接、转贴或以其他方式复制发布/发表。已经本公众号协议授权的媒体、网站,在使用时必须注明"稿件来源微信公众号:开源优测",违者本公众号将依法追究责任。
希尔排序
概述
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminshing Increment Sort),是直接插入排序算法的一种更高效的改进版本。
希尔排序是非稳定排序算法。
该方法因D.L.Shell于1959年提出而得名。
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;
随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
基本过程
希尔排序属于插入类排序,是将整个有序序列分割成若干小的子序列分别进行插入排序。
排序过程:
先取一个正整数d1
然后取d2
直至di=1,即所有记录放进一个组中排序为止。
时间成本
希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;
当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。
所以,希尔排序的时间复杂度会比o(n^2)好一些。
代码
# -*- coding:utf-8 -*-
__author__="苦叶子"
importrandom
'''公众号:开源优测'''
# 随机生成1-10之间无序序列整数数据
defgenerator():random_data=[]foriinrange(,10):random_data.append(random.randint(1,1000))returnrandom_data
# 希尔排序
defshell_sort(data_list):# 序列长度length=len(data_list)# 步长,这个数据大家可以修改下,查看排序过程step=2# 分组group=int(length/step)print("gourp: ",group)whilegroup>:# 遍历分组,对所有分组进行排序foriinrange(,group):j=i+group
# 对分组进行排序whilej=:ifdata_list[k]>key:data_list[k+group]=data_list[k]data_list[k]=key k=k-group j=j+group group=int(group/step)returndata_list
if__name__=="__main__":print("开源优测-积微速成计划基本功")# 生成随机无序数据random_data=generator()# 打印无序数据print(random_data)# 排序length=len(random_data)sorted_data=shell_sort(random_data)# 打印排序结果print(sorted_data)
总计175篇 2017年度文章精选,欢迎大家分享到朋友圈,O(∩_∩)O谢谢
领取专属 10元无门槛券
私享最新 技术干货