题4

题4

题目

Q:对任意 7 个关键字进行基于比较的排序, 至少要进行 ( ) 次关键字之间的两两比较.
A. 13
B. 14
C. 15
D. 6

分析

A:排序的比较次数用公式
代入n=7得到
向上取13

解

A
对于任意序列进行基于比较的排序,求至少的比较次数应考虑最坏情况。
对任意 个关键字排序的比较次数至少为 。将 代入公式,答案为 13 。
上述公式的证明: 在基于比较的排序算法中, 每次比较两个关键字后, 仅出现两种可能的转移。
假设整个排序过程至少要做 次比较,显然会有 种情况。
由于 个记录共有 种不同的排列,因此有 !种不同的比较路径,于是有 !,即 。
考虑到 为整数,所以比较次数为 。