当前位置：首页 > 编程日记 > 正文

用python写希尔排序_python希尔排序介绍（实例）

编程日记 2025-01-19 18:20:00

希尔排序介绍

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本,该方法的基本思想是：先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序(增量足够小)时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下(接近最好情况)，效率是很高的，因此希尔排序在时间效率比直接插入排序有较大提高。

首先要明确一下增量的取法：第一次增量的取法为： d=count/2;

第二次增量的取法为: d=(count/2)/2;

最后一直到: d=1; 看上图观测的现象为： d=3时：将40跟50比，因50大，不交换。

将20跟30比，因30大，不交换。

将80跟60比，因60小，交换。

d=2时：将40跟60比，不交换，拿60跟30比交换，此时交换后的30又比前面的40小，又要将40和30交换，如上图。

将20跟50比，不交换，继续将50跟80比，不交换。

d=1时：这时就是前面讲的插入排序了，不过此时的序列已经差不多有序了，所以给插入排序带来了很大的性能提高。

代码实例：

import time,random

#source = [8, 6, 4, 9, 7, 3, 2, -4, 0, -100, 99]

#source = [92, 77, 8,67, 6, 84, 55, 85, 43, 67]

source = [ random.randrange(10000+i) for i in range(10000)]

#print(source)

step = int(len(source)/2) #分组步长

t_start = time.time()

while step >0:

print("---step ---", step)

#对分组数据进行插入排序

for index in range(0,len(source)):

if index + step < len(source):

current_val = source[index] #先记下来每次大循环走到的第几个元素的值

if current_val > source[index+step]: #switch

source[index], source[index+step] = source[index+step], source[index]

step = int(step/2)

else: #把基本排序好的数据再进行一次插入排序就好了

for index in range(1, len(source)):

current_val = source[index] # 先记下来每次大循环走到的第几个元素的值

position = index

while position > 0 and source[

position - 1] > current_val: # 当前元素的左边的紧靠的元素比它大,要把左边的元素一个一个的往右移一位,给当前这个值插入到左边挪一个位置出来

source[position] = source[position - 1] # 把左边的一个元素往右移一位

position -= 1 # 只一次左移只能把当前元素一个位置 ,还得继续左移只到此元素放到排序好的列表的适当位置为止

source[position] = current_val # 已经找到了左边排序好的列表里不小于current_val的元素的位置,把current_val放在这里

print(source)

t_end = time.time() - t_start

print("cost:",t_end)

希望与广大网友互动？？

点此进行留言吧！

https://www.dkcj.cn/info/37006.html

用python写希尔排序_python希尔排序介绍（实例）

相关文章：

【No.5 类型转换导致的错误】

小学AI教材终于来了，下一步是AI胎教吗？

快过年了，博客园里的文章也变少了

字符串多模式精确匹配（脏字/敏感词汇/关键字过滤算法）——TTMP算法之实战F模式...

深入java_深入Java Final

盛会再临，2018中国大数据技术大会（BDTC）首曝日程及议题

Linux下修改MAC地址总结

hadoop 2 java hdfs_Hadoop2.6.0学习笔记（二）HDFS访问

知乎如何洞察你的真实喜好？首页信息流技术揭秘

[Web开发] 微软的RSS协议扩展 - FeedSync 介绍 (4)

weblogic 修改控制台密码

WPF框架的内存泄漏BUG

java map深拷贝_java 实现Map的深复制

出门问问工程副总裁黄美玉入选IEEE Fellow，曾担任微软Cortana首席NLP科学家

Windows2003服务器不支持FLV视频的解决方法

mpi并行 java_【并行计算】用MPI进行分布式内存编程（一）

JQuery——选择器分类

3月6日工作日志-88250

专注文本处理，达观数据完成B轮融资，累计融资超2亿元

Asp.Net Core写个共享磁盘文件Web查看器

ImageNet时代将终结？何恺明新作：Rethinking ImageNet Pre-training

java 序列化缓存_java_缓冲流、转换流、序列化流

QQ2007去广告教程（本地vip）

java instanceof 报错_java instanceof方法

grep的常用命令语法

千呼万唤始出来！OpenCV 4.0正式发布！

ORA-01031: insufficient privileges的解决方法

java 线程通讯_java多线程（五）线程通讯

合并排序（C语言实现)

工程实践也能拿KDD最佳论文？解读Embeddings at Airbnb