希尔排序算法的思路
希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法由DL.Shell于1959年提出而得名。 希尔排序把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
# Filename : lean001.py # author by : www.py40.com #python希尔排序算法 def shell_sort(alist): length=len(alist) inc=0 while inc<=length/3: inc=inc*3+1 print(inc) while inc>=1: for i in range(inc,length): tmp=alist[i] for j in range(i,0,-inc): if tmp<alist[j-inc]: alist[j]=alist[j-inc] else: j+=inc break alist[j-inc]=tmp inc//=3 print(alist) a = [1,15,12,3,56,42,1,44,32,25,6,7,32] shell_sort(a) print("result:"+str(a)) |
执行结果
1 2 3 4 5 6 |
C:\Users\Administrator>E:\python\learn\lean001.py 13 [1, 15, 12, 3, 56, 42, 1, 44, 32, 25, 6, 7, 32] [1, 15, 6, 32, 1, 25, 7, 3, 32, 42, 12, 44, 56] [1, 1, 3, 6, 7, 12, 15, 25, 32, 32, 42, 44, 56] result:[1, 1, 3, 6, 7, 12, 15, 25, 32, 32, 42, 44, 56] |
未经允许不得转载:Python在线学习 » python-希尔排序