A-A+
以关键字比较为基础的排序算法在最坏情况下的计算时间下界为O(nlogn)。下面的排序算法中
问题详情
以关键字比较为基础的排序算法在最坏情况下的计算时间下界为O(nlogn)。下面的排序算法中，最坏情况下计算时间可以达到O(nlogn)的是(59)；该算法采用的设计方法是(60)。
A．归并排序
B．插入排序
C．选择排序
D．冒泡排序
参考答案
正确答案：A
解析：直接插入排序、简单选择排序和冒泡排序最坏情况下计算时间可以达到O(n2)，而归并排序的时间最坏情况下可以达到O(nlogn)。而归并排序也是分治策略的一个典型应用。
