我们比较并交换原始数组中的值（如果需要）。完成此步骤后，数组变成：[14, 10, 27, 19, 35, 33, 42, 44]，图如下所示，10 与 19 的位置互换一下。
最后，我们使用值间隔 1 对数组的其余部分进行排序，Shell sort 使用插入排序对数组进行排序。
实现
const shellSort = arr => { let len = arr.length, temp, gap = 1; console.time('希尔排序耗时'); while (gap < len / 3) { //动态定义间隔序列 gap = gap * 3 + 1; } for (gap; gap > 0; gap = Math.floor(gap / 3)) { for (let i = gap; i < len; i++) { temp = arr[i]; let j = i - gap; for (; j >= 0 && arr[j] > temp; j -= gap) { arr[j + gap] = arr[j]; } arr[j + gap] = temp; console.log('arr :', arr); } } console.timeEnd('希尔排序耗时'); return arr; };测试
// 测试 const array = [35, 33, 42, 10, 14, 19, 27, 44]; console.log('原始array:', array); const newArr = shellSort(array); console.log('newArr:', newArr); // 原始 array: [35, 33, 42, 10, 14, 19, 27, 44] // arr : [14, 33, 42, 10, 35, 19, 27, 44] // arr : [14, 19, 42, 10, 35, 33, 27, 44] // arr : [14, 19, 27, 10, 35, 33, 42, 44] // arr : [14, 19, 27, 10, 35, 33, 42, 44] // arr : [14, 19, 27, 10, 35, 33, 42, 44] // arr : [14, 19, 27, 10, 35, 33, 42, 44] // arr : [10, 14, 19, 27, 35, 33, 42, 44] // arr : [10, 14, 19, 27, 35, 33, 42, 44] // arr : [10, 14, 19, 27, 33, 35, 42, 44] // arr : [10, 14, 19, 27, 33, 35, 42, 44] // arr : [10, 14, 19, 27, 33, 35, 42, 44] // 希尔排序耗时: 3.592041015625ms // newArr: [10, 14, 19, 27, 33, 35, 42, 44]分析
第一，希尔排序是原地排序算法吗 ？
希尔排序过程中，只涉及相邻数据的交换操作，只需要常量级的临时空间，空间复杂度为 O(1) 。所以，希尔排序是原地排序算法。
第二，希尔排序是稳定的排序算法吗 ？
我们知道，单次直接插入排序是稳定的，它不会改变相同元素之间的相对顺序，但在多次不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，可能导致相同元素相对顺序发生变化。
因此，希尔排序不稳定。
第三，希尔排序的时间复杂度是多少 ？
最佳情况：T(n) = O(n log n)。
最差情况：T(n) = O(n log2 n)。
平均情况：T(n) = O(n log2 n)。
动画
堆的定义
堆其实是一种特殊的树。只要满足这两点，它就是一个堆。
堆是一个完全二叉树。
完全二叉树：除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。
堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。
也可以说：堆中每个节点的值都大于等于（或者小于等于）其左右子节点的值。这两种表述是等价的。
对于每个节点的值都大于等于子树中每个节点值的堆，我们叫作大顶堆。
对于每个节点的值都小于等于子树中每个节点值的堆，我们叫作小顶堆。
其中图 1 和 图 2 是大顶堆，图 3 是小顶堆，图 4 不是堆。除此之外，从图中还可以看出来，对于同一组数据，我们可以构建多种不同形态的堆。
思想
将初始待排序关键字序列 (R1, R2 .... Rn) 构建成大顶堆，此堆为初始的无序区；
将堆顶元素 R[1] 与最后一个元素 R[n] 交换，此时得到新的无序区 (R1, R2, ..... Rn-1) 和新的有序区 (Rn) ，且满足 R[1, 2 ... n-1] <= R[n]。