Python 希尔排序法

#希尔排序法

一、希尔排序法是一种插入排序。

它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。

二、基本思想：

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；

随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

三、基本步骤：

我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，

这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。

四、参考网址：https://www.cnblogs.com/chengxiao/p/6104371.html

五、Python代码：

#希尔排序
def shellSort(arr):
　　n=len(arr) #数列元素个数
　　gap=int(n/2) #从中间元素开始

　　while gap>0: 
　　　　for i in range(gap,n): 从中间往后依次比较
　　　　　　temp=arr[i]
　　　　　　j=i

　　　　　　while j>=gap and arr[j-gap]  > temp: #">"由小到大排序；"<"由大到小排序
　　　　　　　　arr[j]=arr[j-gap]
　　　　　　　　j-=gap
　　　　　　　　arr[j]=temp

　　　　gap=int(gap/2) #再次

#测试
arr=[12,34,54,2,3,0,10,15,11]
n=len(arr)
shellSort(arr)
print(" 排序后：")
for i in range(n):
print(arr[i])