希尔排序
希尔排序是插入排序的一种,又称“缩小增量排序”(Diminishing Increment Sort),是插入排序的一种更高效的改进版本。 希尔排序实际上就是分组的插入排序,希尔排序以步长为分组,然后不断减少步长。当步长为1时,数组就是有序的了,先看一下希尔排序的过程,图中各色彩线的两端为不同分组。
- [9,2,5,4,7,1,3,6,8,0]*是待排序的数组,第一次遍历时步长为 5,所以待排序的数组分为[9,1],[2,3],[5,6],[4,8],[7,0]五个子数组,将五个子数组进行插入排序,得到[1,9],[2,3],[5,6],[4,8],[0,7]。然后不断减小步长,当步长为1 时,即完成了数组的希尔排序。
代码实现
通过三层循环实现希尔排序:
Array.prototype.shellSort = function(){
//step 分组步长,通过for不断减小步长,直到步长为1
for (let step = Math.floor(arr.length / 2); step > 0; step = Math.floor(step / 2)) {
for (let i = step; i < arr.length; i++) {
for (let j = i - step; j >= 0 && arr[j] > arr[step + j]; j -= step) {
[ arr[j], arr[step + j] ] = [ arr[step + j], arr[j] ]
}
}
}
}
const arr = [9,2,5,4,7,1,3,6,8,0]
arr.shellSort()
console.log('完成希尔排序:' + arr)
控制台输出:
控制台输出符合预期,我们再回头来看看代码,这三层循环有点复杂,我们把step,j 以及数组打印出来,看看这三层循环都干了什么事情。
看完输出结果,问题就清晰多了。
- 第一层循环的作用就是不断减小步长;
- 第二层循环的作用遍历不同步长下的数组元素;
- 第三层循环的作用是进行插入排序;
时间复杂度和稳定性
- 希尔排序的平均时间复杂度n*log2n
- 希尔排序是不稳定的排序算法