希尔排序算法是插入排序的一种变种。只是这种算法,增加了一些随机因素。插入排序是整个数据是一组进行排序。希尔排序是把数据进行分组,进行排序,逐步减少组的数量,最后是一组,再进行一趟希尔排序。
希尔排序的关键点
举例说一下希尔排序, 以 6, 7, 4, 3, 8 为例
2. 三组数据进行插入排序得到,4, 7, 6, 3, 8
3 . 缩小间隔 gap = gap / 2 = 1 , 这个时候就是一组数据(4, 7, 6, 3, 8)进行插入排序
以下是python代码实现的希尔排序
def shell_sort(elements):
n = len(elements)
gap = int(n / 2)
while gap > 0:
print(gap)
insert_sort(elements, gap)
gap = int(gap / 2)
def insert_sort(elements, gap):
n = len(elements)
for i in range(gap, n, gap):
tmp = elements[i]
k = i
for j in range(i - gap, -1, -gap):
if tmp < elements[j]:
elements[j + gap] = elements[j]
k = j
if k != i:
elements[k] = tmp
if __name__ == '__main__':
arr = [6, 7, 4, 3, 8]
shell_sort(arr)
print(arr)
运行结果如下:
[3, 4, 6, 7, 8]
更多内容请关注公众号:IT技术漫漫谈
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。