希尔排序

排序算法

希尔排序是插入排序的改进版本,通过比较相距一定间隔的元素来工作,逐步减小间隔直到只比较相邻元素。

时间复杂度:最佳 O(n log n) | 平均 O(n log² n) | 最差 O(n²)
空间复杂度:O(1)
稳定性:不稳定

应用场景/前提条件

  • 插入排序的改进版
  • 适用于中等规模数据

算法讲解

介绍

希尔排序(Shell Sort)是插入排序的一种改进版本,它是最早突破O(n²)的排序算法之一,核心思想是利用步长序列对数据进行分组,在每个分组内使用插入排序,逐步减小步长直到为1,完成最终排序。

希尔排序时元素会大跨度移动,解决了插入排序在处理大规模乱序数组效率低下的问题,让元素更快移动到正确位置。虽然说后来出现了更高效的排序算法,但是希尔排序凭借其简单性和在中等规模数据上的良好表现,仍然是实际应用中的重要排序算法。

算法步骤

  1. 选择一个步长序列,建议初始步长 n/2,每次减半直到步长为1
  2. 对每个步长,对数组进行分组,对应位置相隔为步长的元素视为一组
  3. 对每一组使用插入排序进行排序
  4. 减小步长,重复步骤2和3,直到步长减少到1
  5. 当步长为1时,相当于对整个数组做一次插入排序,此时数组已基本有序,所需的比较和移动次数大大减少

为了帮助大家更好的理解,我们以初始数组 [8, 9, 1, 7, 2, 6, 3, 5, 4] 为例,查看每一步的详细流程:

1)第一轮排序

  • 选择间隔 (Gap): 4 (数组长度9除以2取整)
  • 分组: 按照间隔4将数组分为4个子序列。
    • 第1组 (下标0, 4, 8): [8, 2, 4]
    • 第2组 (下标1, 5): [9, 6]

...