希尔排序,我真的领悟了

之前文章我们讲到过 冒泡排序选择排序插入排序 都是原地的,并且时间复杂度都为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;
}

最后

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

原文链接:https://juejin.cn/post/7258180488359018557 作者:小九九的爸爸

(0)
上一篇 2023年7月21日 上午10:05
下一篇 2023年7月23日 上午10:01

相关推荐

发表回复

登录后才能评论