Python – 希尔排序算法

希尔排序是一种插入排序算法，又称作缩小增量排序。是对直接插入排序算法的改进。其基本思想是：
先取一个小于 n 的整数作为第一个增量，把全部数据分成个组。所有距离为的倍数的记录放在同一个组中。
先在各组内进行直接插入排序；
然后，取第二个增量重复上述的分组和排序，直至所取的增量，即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。
1 2 3 4 5 6 7 8 9 10 11


def shellSort(unsorted_list, reversed=False):
print("raw: ", unsorted_list)
n = len(unsorted_list)/2
num = 1
while n:
for ni in range(n):
group = range(ni, len(unsorted_list), n)
for i in range(1, len(group)):
j = i-1
cmp = unsorted_list[group[i]]
while j > -1 and func(unsorted_list[group[j]], cmp, reversed):
unsorted_list[group[j+1]], unsorted_list[group[j]] = unsorted_list[group[j]], cmp
j -= 1
print("NO.%d:" % num, unsorted_list)
n /= 2
num += 1
print("last:", unsorted_list)
return unsorted_list