希尔排序（Shell Sort） 题目描述： 给定一个整数数组，使用希尔排序算法将其按升序排列。希尔排序是插入排序的改进版，通过将数组元素按间隔分组进行插入排序，逐渐缩小间隔直至为1，最终完成排序。 解题步骤 核心思想 希尔排序通过定义增量序列（即间隔序列），将数组划分为多个子序列，对每个子序列进行插入排序。随着增量逐渐减小，数组整体趋于有序，最后当增量为1时，整个数组只需少量调整即可完成排序。 选择增量序列 常用的增量序列是希尔原始序列：初始间隔为 gap = n/2 ，后续每次将间隔减半（ gap = gap/2 ），直到 gap = 1 。例如数组长度为8，则增量序列为4、2、1。 分组插入排序 对每个间隔 gap ，将数组划分为 gap 个子序列，每个子序列包含间隔为 gap 的元素（例如下标为0、gap、2gap...的元素为一组）。 对每个子序列进行插入排序：从每个子序列的第二个元素开始，向前比较并交换，确保子序列有序。 逐步缩小间隔 重复步骤3，每次将间隔减半，直到间隔为1。当间隔为1时，整个数组被视为一个子序列，进行最后一次插入排序，此时数组已基本有序，插入排序效率很高。 示例演示 数组： [5, 2, 9, 1, 5, 6] ，长度 n=6 第一轮 gap=3 ： 分组： [5,1] 、 [2,5] 、 [9,6] 各组插入排序后： [1,2,6,5,5,9] 第二轮 gap=1 ： 对整个数组插入排序：比较并交换相邻无序元素，最终得到 [1,2,5,5,6,9] 。 关键点 希尔排序的时间复杂度取决于增量序列，最坏情况为O(n²)，但优于普通插入排序。 增量序列的选择影响效率，如Hibbard序列可优化至O(n^(3/2))。 空间复杂度为O(1)，是原地排序算法。