希尔排序算法
原创
希尔排序算法是插入排序的一种变种。只是这种算法，增加了一些随机因素。插入排序是整个数据是一组进行排序。希尔排序是把数据进行分组，进行排序，逐步减少组的数量，最后是一组，再进行一趟希尔排序。
希尔排序的关键点
- 本质上还是插入排序。
- 分组进行插入排序，按一定的间隔取数据组成一组，缩小间隔，组的数量步骤减少，最后形成一组进行插入排序。
举例说一下希尔排序， 以 6, 7, 4, 3, 8 为例
- 间隔 gap = 2 (数组长度除以2)得到， 6, 7, 4, 3, 8；分成三组（6,4）（7,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 删除。
评论
登录后参与评论
推荐阅读