任何一个基于“比较”的内部排序算法,若对6个元素进行排序,则在最坏情况下所需的比较次数至少为(65

Question

任何一个基于“比较”的内部排序算法，若对6个元素进行排序，则在最坏情况下所需的比较次数至少为(65)。

A．10

B．11

C．21

D．36

Answer 1

正确答案：A
解析：基于关键字的比较操作排序方法，其排序过程均可以利用判定树来描述。判定树上所有叶子结点恰好表示所有排序结果，每个初始序列经过排序达到有序所需要进行的比较次数，正好等于从树根到和该序列相应的叶子结点的路径长度。由于含n个记录的序列可能出现的初始状态有n!个，则描述n个记录排序过程的判定树必须有n!个叶结点。因为，若少一个叶结点，则说明尚有两种状态没有分辨出来。由于若二叉树高度为h，则叶子结点的个数不超过2h-1个；反之，若有u个结点，则二叉树的高度至少为。因此，描述n个记录排序的判定树上必定存在一条长度为的路径。由此可知：任何一个借助比较进行排序的算法，在最坏情况下所需进行比较次数至少为。在本题中，n=6，因此，，因此，正确的答案为10次。