排序面试题目总结

快速排序在完全无序的情况下效果最好，时间复杂度为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)