Python 实现 希尔排序， 希尔排序其实 就是 插入排序的改进版吧，希尔排序的步长选择都是从d=len/2开始，每次再减半，直到最后为1,当变为1的时候 ，可以认为就是简单的插入排序。这种缩小步长的好处，非常简单，弥补了插入排序的缺点，尽可能减少数字的移动次数。希尔思想是这样 局部看起来有序，然后局部的局部在有序，直到 步长为1，就保证了不会出现，待排序列都是逆序的情况。 这种想法非常高明，佩服希尔。
希尔排序按其设计者 希尔（Donald Shell）的名字命名，该算法由1959年公布。一些老版本教科书和参考手册把该算法命名为Shell-Metzner，即包含Marlene Metzner Norton的名字，但是根据Metzner本人的说法，“我没有为这种算法做任何事，我的名字不应该出现在算法的名字中。”
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
# coding=utf-8
'''
@author:chang
shell_sort 排序
2017-10-18 星期三
'''
def group_sort(array,length,d ,x):
'''
*group 内排序
*参数说明：
*array - - 待排序的数组
*len - - 数组的长度
*d 组的步长
*x 组的起始位置
'''
for i in range(x+d,length,d):
k = i
temp = array[k]
for j in range(i-d,-1,-d):
if array[j] > temp:
array[j+d]=array[j]
k =j
else:
break
array[k] =temp
def shell_sort(array,length):
gap = length//2
while gap >0:
for i in range(0,gap,1):
# 共gap个组，对每一组都执行直接插入排序
group_sort(array,length,gap,i)
gap = gap//2
return array
if __name__ == '__main__':
mylist=[1,34,6,21,98,31,7,4,36,16,47,67,37,25,2]
length= len(mylist)
print(shell_sort(mylist,length))
下面看看 结果：
总结： 本文主要实现用Python 实现希尔排序。
参考链接：
分享快乐，留住感动。 2017年 10月 18日 星期三 16:28:34 ---biaoge
京公网安备 11010502036488号