python算法(六)希尔排序
希称排序
问题: 将一组乱序的数列,按从小到大(从大到小)的顺序重新排列.
方法:
- 设定一个初始增量, 对原始数列进行分组:
- 对每一个分组进行排序
- 设置一个更小的增量
- 对第一轮排序后的数列再按增量重新分组
- 对每一个分组进行排序
- 以此,直到增量为1, 再排序
- 结果为我们想要的结果
对分组进行排序用的是插入排序算法.因此,希尔排序是插入排序的一种优化的算法
图示
在这里插入图片描述
代码实现
# coding: utf-8
# 作者:爱编程的章老师
# 创建:2021/2/3 8:07 下午
# 邮箱:slxxf000@163.com
# 微信:slxxfl
# 微信公众号:A卫隆少儿编程
# 格言:给自己的生活增加一份向上的力，每都进步一点点
from random import shuffle
# 希尔排序
def shell(num_list):
n = len(num_list)
d = n // 2
while d >= 1:
# 对分组排序
for i in range(d, n):
temp = num_list[i]
j = i - d
while j >= 0 and num_list[j] > temp:
num_list[j + d] = num_list[j]
j = j - d
num_list[j + d] = temp
# 每一次排序后重新定义增量,直到增量为1排序结束, 增量为0退出排序
d //= 2
return num_list
# 测试
num_list_demo = [x for x in range(100)]
shuffle(num_list_demo)
print(num_list_demo)
shell(num_list_demo)
print(num_list_demo)
一个好的希尔排序,对增量的设置会有一定的需求.
傻瓜式的增量设置,不一定是最优的增量设置,也不一定是最快的算法.
这里给出的粗暴的增量倍缩式递减只是一种算法的演示.
