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谢谢

  • 发表于:
  • 原文链接:http://kuaibao.qq.com/s/20180124A0329200?refer=cp_1026

同媒体快讯

  • Python3冒泡排序

    2018-10-24
  • PyCharm常用技巧集合

    2018-10-24
  • Python3插入排序

    2018-10-24
  • SQL常用的基础语法

    2018-10-24
  • Selenium3+Python3环境部署

    2018-10-24
  • Python3选择排序

    2018-10-24

相关快讯

扫码关注云+社区