题目
设被排序的结点序列共有N个结点,在该序列中的结点已十分接近排序的情况下,用直接插入法,归并法和一般的快速排序法对其排序,这些算法的时间复杂性为()
A.O(N),O(N),O(N)
B.O(N),O(N*log2N),O(N*log2N)
C.O(N),O(N*log2N),O(N2)
D.O(N2),O(N*log2N),O(N2)
设被排序的结点序列共有N个结点,在该序列中的结点已十分接近排序的情况下,用直接插入法,归并法和一般的快速排序法对其排序,这些算法的时间复杂性为()
A.O(N),O(N),O(N)
B.O(N),O(N*log2N),O(N*log2N)
C.O(N),O(N*log2N),O(N2)
D.O(N2),O(N*log2N),O(N2)
老师讲得好好啊，谢谢老师
最好情况下插入排序是O(n),归并排序最差和最好都是O(nlogn),快速排序最好是对随机序列排序，复杂度为O(nlogn)，基本有序的时间复杂度为O(n^2)。因此，推荐对长随机序列在早中期应用快速排序，后期使用插入/冒泡/选择/计数等排序。
C，归并排序时间复杂度在最好，平均，最差都一样，而插入当有序时是O（n）的复杂度
当待排序的序列为正序或者逆序时，对于快速排序来说，此时选取的枢轴偏大或偏小。即最坏的情况。