Python3希尔排序

声明

本公众号所有内容，均属微信公众号: 开源优测 所有，任何媒体、网站或个人未经授权不得转载、链接、转贴或以其他方式复制发布/发表。已经本公众号协议授权的媒体、网站，在使用时必须注明"稿件来源微信公众号：开源优测"，违者本公众号将依法追究责任。

希尔排序

概述

希尔排序(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谢谢