document.write('希尔排序也称为“缩小增量排序”。它的基本原理是：首先将待排序的元素分成多个子序列，使得每个子序列的元素个数相对较少，对各个子序列分别进行直接插入排序，待整个待排序序列“基本有序后”，再对所有元素进行一次直接插入排序。
具体步骤如下：
(1)选择一个步长序列t1，t2，…，tk，满足ti＞tj(i＜j)，tk=1。
(2)按步长序列个数k，对待排序序列进行k趟排序。
(3)每趟排序，根据对应的步长ti，将待排序列分割成ti个子序列，分别对各个子序列进行直接插入排序。
需要注意的是，当步长因子为1时，所有元素作为一个序列来处理，其长度为n。以数组{26，53，67，48，57，13，48，32，60，50}(假设要求为升序排列)，步长序列{5，3，1}为例。具体步骤如下：
http://www.yfzxmn.cn/newyfB12/tu/1904/j/cm/pytfz1.199E6A1.jpg
示例代码如下：
def shell_sort(lists):
#希尔排序
count=len(lists)
step=2
group=count/step
while group＞0:
for i in range(0,group):
j=i+group
while j＜count:
k=j-group
key=lists[j]
while k＞=0:
if lists[k]＞key:
lists[k+group]=lists[k]
lists[k]=key
k-=group
j+=group
group/=step
return lists
if __name__=="__main__":
lists=[3,4,2,8,9,5,1]
print \'排序前序列为:\',
for i in (lists):
prmt i,
print \'\\n排序后结果为:\',
for i in (shell_sort(lists)):
print i,
程序的运行结果为：
排序前序列为：3 4 2 8 9 5 1
排序后结果为：1 2 3 4 5 8 9
希尔排序的关键并不是随便地分组后各自排序，而是将相隔某个“增量”的记录组成一个子序列，实现跳跃式的移动，使得排序的效率提高。希尔排序是一种不稳定的排序方法，平均时间复杂度为O(nlogn)，最差情况下的时间复杂度为O(ns)(1＜s＜2)，空间复杂度为O(1)。
');