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