JavaScript实现希尔排序算法_高效排序方法详解

在JavaScript中实现希尔排序的步骤如下：

实现代码

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; // 用于定位插入位置
      // 在子序列中进行插入排序（元素间隔为gap）
      for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
        arr[j] = arr[j - gap]; // 将较大的元素后移
      }
      arr[j] = temp; // 插入到正确位置
    }
  }
  return arr;
}

// 示例用法
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(shellSort(arr)); // 输出: [11, 12, 22, 25, 34, 64, 90]

关键点解析

1. 间隔序列 (Gap Sequence)
   使用动态缩小的间隔（初始为 n/2，每次循环减半），逐步将数组分割成多个子序列进行插入排序。

2. 插入排序的变种
   每个子序列的排序本质是插入排序，但元素间隔为 gap，允许元素一次移动多个位置，减少总移动次数。

3. 时间复杂度

   • 平均复杂度：取决于间隔序列，一般为 O(n log n) 到 O(n²)
   • 优于简单插入排序的 O(n²)，尤其适合中等规模数组。

执行流程示例

以数组 [5, 3, 8, 4, 2] 为例：

1. Gap=2：比较并排序子序列 [5,8,2] 和 [3,4]
   → 子序列变为 [2,3,5,4,8]
2. Gap=1：进行标准插入排序
   → 最终结果 [2,3,4,5,8]

通过分阶段缩小间隔，希尔排序有效减少了直接插入排序中的大量位移操作。