JavaScript 排序面试题目总结
系统自带排序实现
每个语言的排序内部实现都是不同的。
对于 JS 来说，数组长度大于 10 会采用快排，否则使用插入排序。选择插入排序是因为虽然时间复杂度很差，但是在数据 量很小的情况下和 O(N * logN) 相差无几，然而插入排序需要的常数时间很小，所以相对别的排序来说更快。
稳定性
稳定性的意思就是对于相同值来说，相对顺序不能改变。通俗的讲有两个相同的数 A 和 B，在排序之前 A 在 B 的前面， 而经过排序之后，B 跑到了 A 的前面，对于这种情况的发生，我们管他叫做排序的不稳定性。
稳定性有什么意义？个人理解对于前端来说，比如我们熟知框架中的虚拟 DOM 的比较，我们对一个<ul>列表进行渲染，
当数据改变后需要比较变化时，不稳定排序或操作将会使本身不需要变化的东西变化，导致重新渲染，带来性能的损耗。
排序面试题目总结
-
快速排序在完全无序的情况下效果最好，时间复杂度为O(nlogn)，在有序情况下效果最差，时间复杂度为O(n^2)。
-
初始数据集的排列顺序对算法的性能无影响的有堆排序，直接选择排序，归并排序，基数排序。
-
合并 m 个长度为 n 的已排序数组的时间复杂度为 O(nmlogm)。
-
外部排序常用的算法是归并排序。
-
数组元素基本有序的情况下，插入排序效果最好，因为这样只需要比较大小，不需要移动，时间复杂度趋近于O(n)。
-
如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用堆排序方法最快。
-
插入排序和优化后的冒泡在最优情况（有序）都只用比较 n-1 次。
-
对长度为 n 的线性表作快速排序，在最坏情况下，比较次数为 n(n-1)/2。
-
下标从1开始，在含有 n 个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在 [n/2]+2 位置上。 因为小根堆中最大的数一定是放在叶子节点上，堆本身是个完全二叉树，完全二叉树的叶子节点的位置大于 [n/2]。
-
拓扑排序的算法，每次都选择入度为0的结点从图中删去，并从图中删除该顶点和所有以它为起点的有向边。
-
任何一个基于"比较"的内部排序的算法，若对 n 个元素进行排序，则在最坏情况下所需的比较次数 k 满足 2^k > n!， 时间下界为 O(nlogn)
-
m 个元素 k 路归并的归并趟数 s=logk(m)，代入数据：logk(100)≦3
-
对 n 个记录的线性表进行快速排序为减少算法的递归深度，每次分区后，先处理较短的部分。
-
在用邻接表表示图时，拓扑排序算法时间复杂度为 O(n+e)
更多面试题
如果你想了解更多的前端面试题，可以查看本站的WEB前端面试题 ,这里基本包涵了市场上的所有前端方面的面试题，也有一些大公司的面试图，可以让你面试更加顺利。
| 面试题 | ||
|---|---|---|
| HTML | CSS | JavaScript |
| jQuery | Vue.js | React |
| 算法 | HTTP | Babel |
| BootStrap | Electron | Gulp |
| Node.js | 前端经验相关 | 前端综合 |
| Webpack | 微信小程序 | - |
这些题库还在更新中，如果你有不错的面试题库欢迎分享给我，我整理后放上来；人人为我，我为人人，互帮互助，共同提高，祝大家都拿到心仪的Offer！
