Payload Website Template

希尔排序（Shell Sort），简单来说就是插入排序的高级改良版（也叫“缩小增量排序”）。

传统插入排序在处理基本有序的数据时速度极快（接近 $O(n)$），但遇到完全无序、特别是小元素靠后的情况时，需要一步步挨个移动，效率就很低。希尔排序的核心思路就是：先让数组“局部有序”，最后再做一次整体的插入排序。

核心工作原理

希尔排序引入了一个概念叫 增量（Gap）：

分组：选择一个增量 $gap$（例如数组长度的一半），把距离为 $gap$ 的元素归为一组。
组内排序：对每个分组分别进行插入排序。
缩小增量：逐渐减小 $gap$（比如 $gap = gap / 2$），重复上述过程。
终局：当 $gap = 1$ 时，整个数组已经“基本有序”，做最后一次标准的插入排序完成收尾。

如上图所示，当 $gap = 3$ 时，算法将数组按下标间隔为 3 拆分为多组（例如 17, 44, 54 组），在组内进行排序后，大元素迅速挪到了右侧，小元素挪到了左侧。

复杂度与特性对比

特性	说明
平均时间复杂度	依赖于增量序列的选择，常见序列（如 Shell 增量 $N/2^k$）约为 $O(n^{1.3})$ ~ $O(n^{1.5})$
最坏时间复杂度	$O(n^2)$（使用原始 Shell 增量）/ $O(n^{1.5})$（使用 Hibbard 等优化的增量序列）
空间复杂度	$O(1)$，属于原地排序（In-place Sort）
稳定性	不稳定（相同值的元素在跨步跳跃排序时，相对顺序可能会改变）

JavaScript 实现示例

JavaScript

function shellSort(arr) {
  let n = arr.length;

  // 初始增量设置为数组长度的一半，每次循环折半
  for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
    // 从第 gap 个元素开始，对其所在组进行直接插入排序
    for (let i = gap; i < n; i++) {
      let temp = arr[i];
      let j = i;

      // 跨步检查并移动元素
      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      arr[j] = temp;
    }
  }
  return arr;
}