2022-09-20算法00
请注意,本文编写于 634 天前,最后修改于 634 天前,其中某些信息可能已经过时。

排序面试题目总结

  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)

本文作者:前端小毛

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!