使用Python实现希尔排序算法

希尔排序是插入排序的改进版，通过分组缩小元素间隔，先“粗排”再“精排”提升效率。核心是选择初始增量（如数组长度的一半），将数组分为若干组，组内元素间隔为增量，对每组用插入排序；随后增量减半，重复分组排序，直至增量为1时完成“精排”。 其关键逻辑是通过分组减少元素移动次数：初始分组大（元素间隔大），先让数组基本有序；逐步缩小增量，最终以插入排序收尾。时间复杂度平均为O(n log n)，最坏O(n²)，空间复杂度O(1)，适用于中等规模、元素分布不均的数组，是原地排序的高效算法。