比较排序的最小比较次数问题

Question

为什么用任何一个基于“比较”的排序算法对 5 个元素进行排序在最坏情况下所需的比较次数至少为 7 次？

Answer 1

先上结论：基于比较的排序每次进行关键字比较的排序的严格时间复杂度为Omega(nlog2(n))
原理在于：
基于比较能获得的信息有限，根据信息熵每次比较能获得两个数之间的关系
而对于n个元素的排序，共有n!种排列
故最坏情况需要的比较次数为log2(n!)

——————

另一类原理：
n个数的排列有n!种，
一次比较能从候选中排除一半，
最坏情况下需要log2(n!)次才能得到最终可能的结果

对于5个元素，共5!=120种排列
需要的比较次数为 log2(120) 约等于 6.9，向上取整得到7