单选题
23.
已知待排序的n个元素可分为n／k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。
A、
O(nlog
2
n)
B、
O(nlog
2
k)
C、
O(klog
2
n)
D、
O(klog
2
k)
【正确答案】
B
【答案解析】
此题考查的知识点是分块排序的思想。因组与组之间已有序，故将n/k个组分别排序即可，基于比较的排序方法每组的时间下界为O(klog
2
k)。可以用二叉树分治形式描述，最好的情况是树的高度为log
2
k。全部时间下界为O(nlog
2
k)。应选B。
提交答案
关闭