希尔排序

基本概念

希尔排序是一种插入排序的算法，它是对简单的插入排序进行改进后，更高效的版本。

特点是利用增量，将数组分成一组组子序列，然后对子序列进行插入排序。

由于增量是从大到小，逐次递减，所以也称为缩小增量排序。

具体步骤

初始数据为arr = [8,9,1,7,2,3,5,4,6,0];
初始增量设置为数组长度的一半，即flag = arr.length/2 = 5;
每次增量减少一半，直到小于1结束。

以5为增量：

• 第一步 下标为0 {8,3}
• 第二步 下标为1 {9,5}
• 第三步 下标为2 {1,4}
• 第四步 下标为3 {7,6}
• 第五步 下标为4 {2,0}

总共得到 五组{8,3} {9,5} {1,4} {7,6} {2,0}
对每一组进行直接插入排序，得到{3,8} {5,9} {1,4} {6,7} {0,2}
最终结果为 [3,5,1,6,0,8,9,4,7,2]

以2位增量：

• 第一步 下标为0 {3,1,0,9,7}
• 第二步 下标为1 {5,6,8,4,2}

总共得到 两组{3,1,0,9,7},{5,6,8,4,2}
对每一组进行直接插入排序，得到{0,1,3,7,9},{2,4,5,6,8}
最终结果为 [0,2,1,4,3,5,7,6,9,8]

以1为增量：

• 第一步{0,2,1,4,3,5,7,6,9,8}
• 进行直接插入排序[0,1,2,3,4,5,6,7,8,9]
• 下次增量为0结束。

代码实现

/**
 * 希尔排序
 */
function shellSort(arr) {
    // 用gap值对数组进行分组，然后对分组进行插入排序，直到gap值=1
    // 首次gap值为Math.floor(arr.length / 2)
    // 后面gap值为Math.floor(gap / 2)
    let gap = Math.floor(arr.length / 2)
    while (gap >= 1) {
        // 通过gap分组
        for (let k = 0; k < gap; k++) {
            // 遍历每一组，并进行插入排序
            // 插入排序的原理是，假设第一个数已经排好序，从第二个数开始
            // 第一个数是k,第二个数是k+gap
            for (let i = k + gap; i < arr.length; i = i + gap) {
                let cur = i
                // 注意不是j--哦，因为已经通过gap分组
                for (let j = i - gap; j >= 0; j = j - gap) {
                    // 如果前一个数比当前数大，就交换位置，否则就插入
                    if (arr[j] > arr[cur]) {
                        let temp = arr[j]
                        arr[j] = arr[cur]
                        arr[cur] = temp
                        cur = j
                    } else {
                        // 插入就不继续循环了
                        break
                    }
                }
            }
        }
        // 继续缩小gap
        gap = Math.floor(gap / 2)
    }
    return arr
}

console.log(shellSort([4, 5, 2, 3, 1, 0, -10, -3, -2]))