数据结构和算法-排序算法-希尔排序
2023-09-14 09:00:33 时间
################## 希尔排序 ########################
""" 希尔排序 希尔排序就是插入排序的一种改进版本, 算法的步骤 把一个序列不视为一个整体,而是视为多个子序列, 假设间隔是gap=4 alist = [54,26,93,17,77,31,44,55,20] 54,26,93,17,77,31,44,55,20 54 77 20 这是1 组,间隔是4, 26 31 这是2 组,间隔是4, 93 44 这是3 组,间隔是4, 17 55 这是4 组,间隔是4, 然后对每一组进行插入算法的排序, [54 77 20],认为54是第一个,然后后面的每一个去和前面比较,进行插入,--------[20 54 77 ] 全部都排序完成之后,再次合并成为一个序列, 然后变化间隔, 比如是gap = 2,再次进行插入算法的排序, 进行之后还是再次合并成为一个整体序列 再次调整gap,比如gap=1 ,然后再次排序,直到排序完成, """
################## 希尔排序 ########################
# 第一版: def shell_sort(alist): n=len(alist) gap = n //2 while gap > 0 : # 这个最外层的循环是控制gap的,越来越小, for j in range(gap,n): i = j while i>0: if alist[i] < alist[i - gap]: alist[i], alist[i - gap] = alist[i - gap], alist[i] i -= gap else: break # 缩短gap步长, gap //=2 # 第二版: def shell_sort2(alist): n = len(alist) # 初始步长 gap = n // 2 while gap > 0: # 按步长进行插入排序 for i in range(gap, n): j = i # 插入排序 while j>=gap and alist[j-gap] > alist[j]: alist[j-gap], alist[j] = alist[j], alist[j-gap] j -= gap # 得到新的步长 gap = gap / 2 if __name__ == '__main__': alist = [54,26,93,17,77,31,44,55,20] shell_sort(alist) print(alist)
相关文章
- java算法 -- 快速排序
- 数据结构和算法-排序算法-选择排序
- 数据结构与算法之美-5 排序算法2 [MD]
- 数据结构与算法-1 拓扑排序 Kahn DFS 有向无环图 [MD]
- 数据结构和算法-排序算法-插入排序
- 数据结构和算法13 之快速排序
- 算法常识——快速排序
- 【数据结构笔记18】数据结构之图的最短路径算法Floyd、有向无环图DAG、拓扑排序、关键路径
- 【数据结构与算法Python实践系列】5分钟学会经典排序算法-选择排序
- 【数据结构与算法Python实践系列】5分钟学会经典排序算法-插入排序
- 781. 森林中的兔子-快速排序加贪心算法
- Python编程:排序算法之冒泡排序
- [数据结构与算法] 2.快速排序 Java 实现
- 数据结构和算法设计专题之---八大内部排序
- 高速排序算法
- 452. Minimum Number of Arrows to Burst Balloons——排序+贪心算法
- 数据结构与算法之计数排序
- DSA 经典数据结构与算法 学习心得和知识总结(一) |排序 十大排序算法汇总(C++)
- DSA之十大排序算法第二种:Straight Selection Sort