先按某个步长（step）分组，每组进行插入排序；接着缩小步长并分组，继续按分组进行插入排序；持续这个过程，直到步长为 0。

举个例子

举个例子，对于这个数组 4 0 0 8 1 2 3 1 2 3 ，使用如下步长序列

先按步长 10 / 2 = 5 分组，那么有如下分组
[4, 2] [0, 3] [0, 1] [8, 2] [1, 3]
各自排序后得到
2 0 0 2 1 4 3 1 8 3
接着减小步长，5 / 2 = 2 分组，那么有
[2, 0, 1, 3, 8] [0, 2, 4, 1, 3]
各自排序后得到
0 0 1 1 2 2 3 3 8 4
继续减小步长，按 1 分组，那么得到排序数组
0 0 1 1 2 2 3 3 4 8
成功～～～

步长序列

• = 1, 2, 4, 8, 16, …
• = 1, 5, 19, 41, 109, …

实现

function shell_sort(arr) {
    for (let gap = arr.length >> 1; gap > 0; gap >>= 1) {
        for (let i = gap; i < arr.length; i++) {
            let temp = arr[i];
            for (let j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
                arr[j + gap] = arr[j];
            }
            arr[j + gap] = temp;
        }
    }
    return arr;
};

参考

• [1] 希尔排序