前端需要掌握的算法之——希尔排序（Shell sort）

Bad programmers worry about the code. Good programmers worry about data structures and their relationships. —— Linus Torvalds

希尔排序（Shell sort） 也称递减增量排序算法，是插入排序的一种更高效的改进版本。插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能，这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

步长的选择是希尔排序的重要部分。比较在希尔排序中是最主要的操作，而不是交换。

上代码：

// 随机生成一个乱序数组
let arr = Array.from(new Array(10), () => ~~(Math.random() * 100))

console.log('Source array is [ %s ]\n', arr.join(', '))

// 希尔排序
function shellSort(arr) {
    const len = arr.length
    let step = 1
    let gap = len >> 1
    let temp
    for (; gap > 0; gap >>= 1) {
        console.log('Gap is %d:', gap)
        let log = ''
        arr.forEach((v, i) => {
            log += `${v}\t${(i + 1) % gap === 0 ? '\n' : ''}`
        })
        console.log('Initial: \n%s', log)

        for (let i = gap, j; i < len; i++) {
            temp = arr[i]
            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
                arr[j + gap] = arr[j]
            }
            arr[j + gap] = temp

            log = ''
            arr.forEach((v, i) => {
                log += `${v}\t${(i + 1) % gap === 0 ? '\n' : ''}`
            })
            console.log('Step %d: \n%s', step++, log)
        }
    }
    console.log('\nSorted array is [ %s ]', arr.join(', '))
}

shellSort(arr)

结果：

Source array is [ 38, 46, 96, 16, 70, 19, 53, 21, 27, 74 ]

Gap is 5:
Initial: 
38  46  96  16  70  
19  53  21  27  74  

Step 1: 
19  46  96  16  70  
38  53  21  27  74  

Step 2: 
19  46  96  16  70  
38  53  21  27  74  

Step 3: 
19  46  21  16  70  
38  53  96  27  74  

Step 4: 
19  46  21  16  70  
38  53  96  27  74  

Step 5: 
19  46  21  16  70  
38  53  96  27  74  

Gap is 2:
Initial: 
19  46  
21  16  
70  38  
53  96  
27  74  

Step 6: 
19  46  
21  16  
70  38  
53  96  
27  74  

Step 7: 
19  16  
21  46  
70  38  
53  96  
27  74  

Step 8: 
19  16  
21  46  
70  38  
53  96  
27  74  

Step 9: 
19  16  
21  38  
70  46  
53  96  
27  74  

Step 10: 
19  16  
21  38  
53  46  
70  96  
27  74  

Step 11: 
19  16  
21  38  
53  46  
70  96  
27  74  

Step 12: 
19  16  
21  38  
27  46  
53  96  
70  74  

Step 13: 
19  16  
21  38  
27  46  
53  74  
70  96  

Gap is 1:
Initial: 
19  
16  
21  
38  
27  
46  
53  
74  
70  
96  

Step 14: 
16  
19  
21  
38  
27  
46  
53  
74  
70  
96  

Step 15: 
16  
19  
21  
38  
27  
46  
53  
74  
70  
96  

Step 16: 
16  
19  
21  
38  
27  
46  
53  
74  
70  
96  

Step 17: 
16  
19  
21  
27  
38  
46  
53  
74  
70  
96  

Step 18: 
16  
19  
21  
27  
38  
46  
53  
74  
70  
96  

Step 19: 
16  
19  
21  
27  
38  
46  
53  
74  
70  
96  

Step 20: 
16  
19  
21  
27  
38  
46  
53  
74  
70  
96  

Step 21: 
16  
19  
21  
27  
38  
46  
53  
70  
74  
96  

Step 22: 
16  
19  
21  
27  
38  
46  
53  
70  
74  
96  


Sorted array is [ 16, 19, 21, 27, 38, 46, 53, 70, 74, 96 ]

注意：这里根据步长分割后是纵向排序，不是横向。