希尔排序

问题

实现希尔排序算法。

解答

希尔排序是插入排序的改进版，通过设置间隔（gap）将数组分组，对每组进行插入排序，逐步缩小间隔直到为 1。

function shellSort(arr) {
  const len = arr.length;
  
  // 初始间隔为数组长度的一半，每次减半
  for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
    // 从 gap 位置开始，对每个元素进行插入排序
    for (let i = gap; i < len; i++) {
      const 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;
}

// 测试
console.log(shellSort([8, 9, 1, 7, 2, 3, 5, 4, 6, 0]));
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

执行过程示例

以 [8, 9, 1, 7, 2, 3, 5, 4, 6, 0] 为例：

// gap = 5: 分成 5 组
// [8, 3], [9, 5], [1, 4], [7, 6], [2, 0]
// 排序后: [3, 5, 1, 6, 0, 8, 9, 4, 7, 2]

// gap = 2: 分成 2 组
// [3, 1, 0, 9, 7], [5, 6, 8, 4, 2]
// 排序后: [0, 2, 1, 4, 3, 5, 7, 6, 9, 8]

// gap = 1: 标准插入排序
// 排序后: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

使用 Knuth 序列优化

function shellSortKnuth(arr) {
  const len = arr.length;
  
  // 计算初始 gap：1, 4, 13, 40, 121...
  let gap = 1;
  while (gap < len / 3) {
    gap = gap * 3 + 1;
  }
  
  while (gap > 0) {
    for (let i = gap; i < len; i++) {
      const temp = arr[i];
      let j = i;
      
      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      
      arr[j] = temp;
    }
    
    // 缩小 gap
    gap = Math.floor(gap / 3);
  }
  
  return arr;
}

关键点

• 希尔排序是插入排序的优化，通过分组减少元素移动次数
• gap 序列的选择影响性能，常用 n/2 或 Knuth 序列 (3^k - 1) / 2
• 时间复杂度：O(n log n) ~ O(n²)，取决于 gap 序列
• 空间复杂度：O(1)，原地排序
• 不稳定排序，相同元素可能改变相对顺序