希尔排序，我真的领悟了

之前文章我们讲到过 冒泡排序、选择排序、插入排序 都是原地的，并且时间复杂度都为O(n^2) 的排序算法。那么今天我们来讲一下希尔排序，它的时间复杂度为O(n*logn)。那这个算法是怎么做到的呢？我们这回一次看个透。

首先再回顾一下 冒泡、选择、插入这3个排序。这三个排序都有一个共同的特点，就是每次比较都会得到当前的最大值或者最小值。有人会说这是屁话，但你细品，为什么很多人都会去刻意背10大排序算法，本质就是因为自己的思想被困住了（什么每轮比较得出最大值的就是冒泡，得出最小值的就是选择等等），假设你从没有接触过排序算法，我还真不相信你不会排序，最差的情况就是做不出原地呗，时间复杂度最差也是N^2，就像下面这样：

let data = [30, 20, 55, 10, 90];

for (let index = 0; index < data.length; index++){
    for (let y = 0; y < data.length - index; y++){
        if(data[y] > data[y+1]){
            [ data[y], data[y+1] ] = [ data[y+1], data[y] ];
        }
    }
}

data的长度是5，就循环5次，每轮比较中都要得出当前轮次的最大值。那么在每一轮中，如何得出最大值呢？那就再来一次遍历。

上述思想我们会发现，它在时间复杂度上是突破不了 O(n^2) 的限制的。原因在于你是两两比较（一次只能在两个数中得到最大值，一次只能给两个数排序）。

如何突破限制呢？那就一次比较多个，就像下面这样：

let data = [30, 20, 55, 10, 90];

// 1、我们对data数组进行拆分，拆分规则：步长为2的数据放到一个集合里。
// 2、根据上面的拆分规则，我们可以将data数组拆成2个子数组。分别是：[30, 55, 90]、[20, 10]
// 3、分别对这2个子数组进行排序，排序后的子数组分别是：[30, 55, 90]、[10, 20]
// 4、将上面的子数组合并为一个新的数组data1：[30, 10, 55, 20, 90]
// 5、修改拆分规则，对修改后的data1数组进行拆分，步长为1。
// 6、因为步长为1，所以相当于对data1数组进行整体排序。

那么如何用代码表示呢？请继续阅读。

第一步、确定步长

这里我们以不断均分，直到均分结果大于0为原则来确定步长：

let data = [30, 20, 55, 10, 90];

// 维护步长集合
let gapArr = [];

let temp = Math.floor(data / 2);

while(temp > 0){
    gap.push(temp);
    temp = Math.floor(temp / 2);
}

第二步、得到间隔相等的元素

这一步其实本质上就是将间隔相等的元素放在一起进行比较。

这意味着我们不用分割数组，只要保证原地对间隔相同的元素进行排序即可。

let data = [30, 20, 55, 10, 90];

let gapArr = [2, 1];

for (let gapIndex = 0; gapIndex < gapArr.length; gapIndex++){
    // 当前步长
    let curGap = gapArr[gapIndex];
    // 从当前索引项为步长的地方开始进行比较
    for(let index = curGap; index < data.length; index++){
        let curValue = data[index]; // 当前的值
        let prevIndex = index - curGap; // 间隔为gap的前一项索引
        while(prevIndex >= 0 && curValue < data[prevIndex]){
            // 这里面的while就代表着gap相等的数据项之间的比较...
            prevIndex = prevIndex - curGap;
        }
    }
}

第二层的for循环、最里面的while循环需要我们好好理解一下。

就以上面的数据为例，我们先不考虑数据交换的问题，只考虑上面的写法是如何把gap相等的元素联系到一块的，现在我们来推演一下：

从上图我们看到，第一次while循环因为不满足条件，导致没有被触发。紧接着index++，我们来推演一下这种状态下的数据：

继续index++，此时我们来推演一下这种状态下的数据：

经过我们一轮间隔（gap）的分析，我们发现这种 for + while 的方法能够满足我们对间隔相等的元素进行排序。因为我们通过这种方式可以获取到间隔相等的元素。

此时，我们终于可以进入到了最后一步，那就是对间隔相等的元素进行排序。

第三步、对间隔相等的元素进行排序

在上一步的基础上，我们来完成相应元素的排序。

// 其它代码都不变......
for(let index = curGap; index < data.length; index++){
    let curValue = data[index]; // 当前的值
    let prevIndex = index - curGap; // 间隔为gap的前一项索引
    while(prevIndex >= 0 && curValue < data[prevIndex]){
        // 新增代码 ++++++
        data[prevIndex + curGap] = data[prevIndex];
        prevIndex = prevIndex - curGap;
    }
    // 新增代码 ++++++
    data[prevIndex + curGap] = curValue;
}

现在我们来对排序的过程进行一下数据推演：

注意，这里我们只演示 curGap === 2 && index === data.length - 1 && data === [30, 20, 55, 10, 9] 的情况。

读到这里大家可能会发现我们突然换了数据源，因为原先的数据源的最后一项正好是最大值，不方便看到数据比较的全貌，所以在这里我们将最后一项改为了最小值。

开启while循环如下：

紧接上图，第二次进入while循环如下：

第二次循环结束后，此时的prevIndex < 0，因为未能进入到第三次的while循环：

至此，我们完成了本轮的数据推演。

在本轮数据推演中，我们会发现它跟之前的两两相比，区别在于它一次可能会比较很多个元素，更具体的说就是，它的一次for循环里，可以比较多个元素对，并将这些元素对进行排序。

第四步、源码展示

function hillSort(arr){
    let newData = Array.from(arr);
    // 增量序列集合
    let incrementSequenceArr = [];
    // 数组总长度
    let allLength = newData.length;
    // 获取增量序列
    while(incrementSequenceArr[incrementSequenceArr.length - 1] != 1){
        let increTemp = Math.floor(allLength / 2);
        incrementSequenceArr.push(increTemp);
        allLength = increTemp;
    }
    for (let gapIndex = 0; gapIndex < incrementSequenceArr.length; gapIndex++){
        // 遍历间隔
        let gap = incrementSequenceArr[gapIndex]; // 获取当前gap
        for (let currentIndex = gap; currentIndex < newData.length; currentIndex++){
            let preIndex = currentIndex - gap; // 前一个gap对应的索引
            let curValue = newData[currentIndex];
            while(preIndex >= 0 && curValue < newData[preIndex]){
                newData[preIndex + gap] = newData[preIndex];
                preIndex = preIndex - gap;
            }
            newData[preIndex + gap] = curValue;
        }
    }
    return newData;
}

最后

又到分别的时刻啦，在上述过程中如果有讲的不透彻的地方，欢迎小伙伴里评论留言，希望我说的对你有启发，我们下期再见啦～～