JavaScript 希尔排序

🌙
手机阅读
本文目录结构

希尔排序

希尔排序的基本思想是把数组按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的元 素越来越多,当增量减至1时,整个数组恰被分成一组,算法便终止。

代码实现:

function hillSort(array) {

  let length = array.length;

  // 如果不是数组或者数组长度小于等于1,直接返回,不需要排序 
  if (!Array.isArray(array) || length <= 1) return;


  // 第一层确定增量的大小,每次增量的大小减半
  for (let gap = parseInt(length >> 1); gap >= 1; gap = parseInt(gap >> 1)) {

    // 对每个分组使用插入排序,相当于将插入排序的1换成了 n
    for (let i = gap; i < length; i++) {
      let temp = array[i];
      let j = i;

      while (j - gap >= 0 && array[j - gap] > temp) {
        array[j] = array[j - gap];
        j -= gap;
      }
      array[j] = temp;
    }
  }

  return array;
}

希尔排序是利用了插入排序对于已排序序列排序效果最好的特点,在一开始序列为无序序列时,将序列分为多个小的分组进行 基数排序,由于排序基数小,每次基数排序的效果较好,然后在逐步增大增量,将分组的大小增大,由于每一次都是基于上一 次排序后的结果,所以每一次都可以看做是一个基本排序的序列,所以能够最大化插入排序的优点。

简单来说就是,由于开始时每组只有很少整数,所以排序很快。之后每组含有的整数越来越多,但是由于这些数也越来越有序, 所以排序速度也很快。

希尔排序的时间复杂度根据选择的增量序列不同而不同,但总的来说时间复杂度是小于 O(n^2) 的。

插入排序是一个稳定排序,但是在希尔排序中,由于相同的元素可能在不同的分组中,所以可能会造成相同元素位置的变化, 所以希尔排序是一个不稳定的排序。

希尔排序的平均时间复杂度为 O(nlogn) ,最坏时间复杂度为 O(n^s) ,空间复杂度为 O(1) ,不是稳定排序。

详细资料可以参考: 《图解排序算法(二)之希尔排序》 《数据结构基础 希尔排序 之 算法复杂度浅析》

更多面试题

如果你想了解更多的前端面试题,可以查看本站的WEB前端面试题 ,这里基本包涵了市场上的所有前端方面的面试题,也有一些大公司的面试图,可以让你面试更加顺利。

面试题
HTML CSS JavaScript
jQuery Vue.js React
算法 HTTP Babel
BootStrap Electron Gulp
Node.js 前端经验相关 前端综合
Webpack 微信小程序 -

这些题库还在更新中,如果你有不错的面试题库欢迎分享给我,我整理后放上来;人人为我,我为人人,互帮互助,共同提高,祝大家都拿到心仪的Offer!

AXIHE / 精选资源

浏览全部教程

面试题

学习网站

前端培训
自己甄别

前端书籍

关于朱安邦

我叫 朱安邦,阿西河的站长,在杭州。

以前是一名平面设计师,后来开始接接触前端开发,主要研究前端技术中的JS方向。

业余时间我喜欢分享和交流自己的技术,欢迎大家关注我的 Bilibili

关注我: Github / 知乎

于2021年离开前端领域,目前重心放在研究区块链上面了

我叫朱安邦,阿西河的站长

目前在杭州从事区块链周边的开发工作,机械专业,以前从事平面设计工作。

2014年底脱产在老家自学6个月的前端技术,自学期间几乎从未出过家门,最终找到了满意的前端工作。更多>

于2021年离开前端领域,目前从事区块链方面工作了