单选题
对于一个长度为n的任意表进行排序，至少需要进行的比较次数是( )。
A．O(n) B．O(n
2
) C．O(10gn) D．O(nlogn)
A
B
C
D
【正确答案】
D
【答案解析】
[解析] 在排序过程中，每次比较会有两种情况出现，若整个排序过程中至少需要t次比较，则显然会有2
t
种情况，由于n个记录总共有n!种不同的排列，因而必须有n!种不同的比较路径，于是有：2
t
≥n!，即t≥log
2
(n!)。
因为log
2
(n!)≈nlog
2
n，所以t≥nlog
2
n。
提交答案
关闭