希尔排序

TIP

希尔排序(Shell Sort)是希尔(Donald Shell)于 1959 年提出的一种排序算法，也是第一个突破 O(N²)的排序算法。希尔排序是经过改进之后的一个更加高效的插入排序版本，它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序

算法描述

• 步骤 1：计算希尔增量序列
  1. 初始增量 gap = length / 2
  2. 缩小增量继续以 gap = gap/2 的方式
  3. 最后得到一个增量序列 {n/2, (n/2)/2 … 1}
• 步骤 2：按增量序列个数 k，对序列进行分组
• 步骤 3：对每组内部进行插入排序
• 步骤 4：最后增量序列为 1 的时候，对整体进行一次插入排序，就得到最终排序数组

静图演示

动图演示

代码编写

// 希尔排序
function shellSort(arr) {
  // 1. 获取数组长度
  var length = arr.length;

  // 2.根据长度计算增量(向下取整)
  var gap = Math.floor(length / 2);

  // 3. while 循环，让增量不断变小，进而分组，然后内部排序调整位置
  while (gap >= 1) {
    // 4. 以gap为间隔，进行分组，对分组进行插入排序
    for (var i = gap; i < length; i++) {
      // 4.1 保存临时变量
      var tmp = arr[i];
      var j = i;
      // 4.2 内层循环: 插入排序
      while (j > gap - 1 && arr[j - gap] > tmp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      // 4.3 将j的位置元素赋值tmp
      arr[j] = tmp;
    }

    // 5. 重新计算gap
    gap = Math.floor(gap / 2);
  }

  // 6. 返回数组
  return arr;
}

代码解析

文字说明

• 第一步：获取数组长度
• 第二步：计算第一次的间隔, 按照希尔提出的间隔实现(gap = length / 2)
• 第三步：增量不断变小, 大于 0 就继续改变增量
• 第四步：编写插入排序：
  1. 保存临时变量, j 位置从 i 开始, 保存该位置的值到变量 tmp 中
  2. 内层循环, j > gap - 1 并且 tmp 大于 arr[j - gap], 那么就进行复制
  3. 将 j 位置设置为变量 tmp
• 第五步：每次 while 循环后都重新计算新的间隔

图解分析

代码测试

// 测试希尔排序
var arr = [3, 6, 4, 2, 11, 10, 5];
console.log(shellSort(arr).join("-"));
// 2-3-4-5-6-10-11

排序效率

• 希尔排序的效率和增量有直接关系，即使使用原稿中的增量效率都高于简单排序
• 但是经过统计, 希尔排序使用原始增量, 最坏的情况下时间复杂度为 O(N²), 通常情况下都要好于 O(N²)