阿西河

所有教程

公众号
🌙
阿西河前端的公众号

我的收藏

    最近访问  (文章)

      教程列表

      抓包专区
      测试专区

      JavaScript 排序面试题目总结

      系统自带排序实现

      每个语言的排序内部实现都是不同的。

      对于 JS 来说,数组长度大于 10 会采用快排,否则使用插入排序。选择插入排序是因为虽然时间复杂度很差,但是在数据 量很小的情况下和 O(N * logN) 相差无几,然而插入排序需要的常数时间很小,所以相对别的排序来说更快。

      稳定性

      稳定性的意思就是对于相同值来说,相对顺序不能改变。通俗的讲有两个相同的数 A 和 B,在排序之前 A 在 B 的前面, 而经过排序之后,B 跑到了 A 的前面,对于这种情况的发生,我们管他叫做排序的不稳定性。

      稳定性有什么意义?个人理解对于前端来说,比如我们熟知框架中的虚拟 DOM 的比较,我们对一个<ul>列表进行渲染, 当数据改变后需要比较变化时,不稳定排序或操作将会使本身不需要变化的东西变化,导致重新渲染,带来性能的损耗。

      排序面试题目总结

      1. 快速排序在完全无序的情况下效果最好,时间复杂度为O(nlogn),在有序情况下效果最差,时间复杂度为O(n^2)。

      2. 初始数据集的排列顺序对算法的性能无影响的有堆排序,直接选择排序,归并排序,基数排序。

      3. 合并 m 个长度为 n 的已排序数组的时间复杂度为 O(nmlogm)。

      4. 外部排序常用的算法是归并排序。

      5. 数组元素基本有序的情况下,插入排序效果最好,因为这样只需要比较大小,不需要移动,时间复杂度趋近于O(n)。

      6. 如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列,用堆排序方法最快。

      7. 插入排序和优化后的冒泡在最优情况(有序)都只用比较 n-1 次。

      8. 对长度为 n 的线性表作快速排序,在最坏情况下,比较次数为 n(n-1)/2。

      9. 下标从1开始,在含有 n 个关键字的小根堆(堆顶元素最小)中,关键字最大的记录有可能存储在 [n/2]+2 位置上。 因为小根堆中最大的数一定是放在叶子节点上,堆本身是个完全二叉树,完全二叉树的叶子节点的位置大于 [n/2]。

      10. 拓扑排序的算法,每次都选择入度为0的结点从图中删去,并从图中删除该顶点和所有以它为起点的有向边。

      11. 任何一个基于"比较"的内部排序的算法,若对 n 个元素进行排序,则在最坏情况下所需的比较次数 k 满足 2^k > n!, 时间下界为 O(nlogn)

      12. m 个元素 k 路归并的归并趟数 s=logk(m),代入数据:logk(100)≦3

      13. 对 n 个记录的线性表进行快速排序为减少算法的递归深度,每次分区后,先处理较短的部分。

      14. 在用邻接表表示图时,拓扑排序算法时间复杂度为 O(n+e)

      更多面试题

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

      面试题
      HTMLCSSJavaScript
      jQueryVue.jsReact
      算法HTTPBabel
      BootStrapElectronGulp
      Node.js前端经验相关前端综合
      Webpack微信小程序-

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

      目录
      目录