100种算法【Python版】第51篇——希尔排序
本文目录
- 1 算法步骤
- 2 算法示例
- 3 python代码
-
- 3.1 代码说明
- 3.2 复杂度分析
- 4 算法优化
-
- 4.1 Shell 原始增量序列
- 4.2 Hibbard 增量序列
- 4.3 Knuth 增量序列
- 4.4 Sedgewick 增量序列
- 4.5 Tokuda 增量序列
- 4.6 Pratt 增量序列
- 5 不同的增量序列的效率对比
希尔排序（Shell Sort）是插入排序的改进版。它通过比较距离较远的元素来提前进行部分排序，从而减少了后期插入排序的移动次数。希尔排序的主要思想是逐步减少元素之间的间隔（称为增量或步长），直到步长为 1，最终转变为标准的插入排序。
1 算法步骤
（1）选择增量序列：
初始增量 gap 通常设为数组长度的一半（n//2），然后逐渐减小，直到 gap 为 1。
（2）分组排序：
对每一个 gap，将数组分成若干个子序列（每个子序列由相隔 gap 的元素组成），对每个子序列进行插入排序。
（3）减少增量：
每次减小增量 gap，重复分组排序，直到 gap 为 1。在最后一次排序时，整个数组实际上是进行了插入排序。
（4）最终排序：
当 gap 为 1 时，进行一次标准的插入排序，确保数组完全有序。
2 算法示例
假设有一个数