【答案解析】假定待排序的记录有n个。由于含n个记录的序列可能出现的状态有n!个，则描述n个记录排序过程的判定树必须有n!个叶子结点。因为若少一个叶子，则说明尚有两种状态没有分辨出来。我们知道，若二叉树高度是h，则叶子结点个数最多为2 ^h-1 ；反之，若有u个叶子结点，则二叉树的高度至少为(log ₂ u)+1。这就是说，描述n个记录排序的判定树必定存在一条长度为log ₂ (n!)的路径。即任何一个借助“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少是log ₂ (n!)。根据斯特林公式，有log ₂ (n!)=O(nlog ₂ n)。即借助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为 此题考查的知识点是基于比较的排序算法效率。