2. 考研
  3. 在下列排序方法中，平均时间复杂度为O(nlogn)的排序算法是( )。 Ⅰ．快速排序 Ⅱ．冒泡排序 Ⅲ．希尔排序 Ⅳ．选择排序

在下列排序方法中，平均时间复杂度为O(nlogn)的排序算法是( )。 Ⅰ．快速排序 Ⅱ．冒泡排序 Ⅲ．希尔排序 Ⅳ．选择排序

admin2019-08-10  36
问题 在下列排序方法中，平均时间复杂度为O(nlogn)的排序算法是(    )。
    Ⅰ．快速排序    Ⅱ．冒泡排序    Ⅲ．希尔排序    Ⅳ．选择排序
选项 A、仅Ⅰ、Ⅱ
B、仅Ⅰ、Ⅲ
C、仅Ⅰ、Ⅲ、Ⅳ
D、仅Ⅲ、Ⅳ
答案B
解析 这种题目其实就是考查考生的记忆能力，因为在考研紧张的氛围下，很少有考生在做这种选择题的时候能够分析其算法来选择答案。下面与大家分享一个记忆总结，该总结可以将内部排序所有的记忆性题目轻轻松松地拿下。由以下总结可以很轻松地得到答案B。
    稳定性、时间复杂度、空间复杂度总结：
    (1)稳定性总结：一句话解决：本人考研无聊中，那么就快(快速排序)些(些和希尔谐音，希尔排序)选(选择排序)堆(堆排序)来聊!这里面都是不稳定的，其他的就自然都是稳定的了。
    (2)时间复杂度总结：
   1)在军训的时候，教官说了一句话：快(快速排序)些(希尔排序)以nlogn的速度归(归并排序)队(堆排序)!在这句话里面包含的排序，时间复杂度都是O(nlogn)1
    2)冒泡冒得好就是O(n)，冒泡冒得不好就是O(n2)。
    3)直接插插得好就是O(n)，插得不好就是O(n2)，其中插得好、冒得好分别对应最好的时间复杂度，插得不好、冒得不好分别对应最坏时间复杂度，而平均时间复杂度对应最坏的时间复杂度。
    (3)辅助空间总结：只需记住几个特殊的就好，归并O(n)、快速O(log2n)、基数排序O(r+d)，其他的就自然全部是O(1)了。
转载请注明原文地址:https://kaotiyun.com/show/QrCi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)