动画

实现

思想

• 先将整个待排序的记录序列分割成为若干子序列。
• 分别进行直接插入排序。
• 待整个序列中的记录基本有序时，再对全体记录进行依次直接插入排序。

  过程

1. 举个易于理解的例子：[35, 33, 42, 10, 14, 19, 27, 44]，我们采取间隔 4。创建一个位于 4 个位置间隔的所有值的虚拟子列表。下面这些值是 { 35, 14 }，{ 33, 19 }，{ 42, 27 } 和 { 10, 44 }。

1. 我们比较每个子列表中的值，并在原始数组中交换它们（如果需要）。完成此步骤后，新数组应如下所示。

1. 然后，我们采用 2 的间隔，这个间隙产生两个子列表：{ 14, 27, 35, 42 }， { 19, 10, 33, 44 }。

1. 我们比较并交换原始数组中的值（如果需要）。完成后，数组变成[14, 10, 27, 19, 35, 33, 42, 44]，图如下所示，10 与 19 的位置互换一下。

1. 最后，我们使用值间隔 1 对数组的其余部分进行排序，Shell sort 使用插入排序对数组进行排序。

代码

const array = [3, 44, 38, 5, 47, 15, 36, 26, 1, 27, 46, 4, 19, 50, 48];
const shellSort = (arr) => {
  const len = arr.length;
  // 逐步缩小间隔 gap，分组元素逐渐变多
  // group 表示每个分组的第二个元素位置的最大值。间接表示分组数
  for (let gap = len >> 1, group = len; gap >= 1; gap = gap >> 1, group >> 1) {
    // 遍历每个分组，对每个分组进行插入排序
    // i 代表每个分组的第二个元素
    for (let i = gap; i < group; i++) {
      // 按照插入排序的思路，每拿到一个新元素，与本分组之前的元素对比，比新元素大的往后排
      for (let j = i; j < len; j += gap) {
        const current = arr[j]; // 暂存新元素，第 j 项的值
        let preIndex = j - gap; // 待比较的下标，用于找出比新元素小的第一个索引
        // 把大于新元素的元素，都往后移一位
        while (preIndex >= i - gap && arr[preIndex] > current) {
          arr[preIndex + gap] = arr[preIndex]
          preIndex -= gap;
        }
        arr[preIndex + gap] = current
      }
    }
  }
}
shellSort(array);
console.log(array); // [3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

分析

• 第一，希尔排序是原地排序算法吗 ？
  希尔排序过程中，只涉及相邻数据的交换操作，只需要常量级的临时空间，空间复杂度为 O(1) 。所以，希尔排序是原地排序算法。
• 第二，希尔排序是稳定的排序算法吗 ？
  我们知道，单次直接插入排序是稳定的，它不会改变相同元素之间的相对顺序，但在多次不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，可能导致相同元素相对顺序发生变化。
  因此，希尔排序不稳定。
• 第三，希尔排序的时间复杂度是多少 ？
  最佳情况：。
  最差情况：。
  平均情况：。