Question

排序算法比较次数与初始化顺序的关系

Answer 1

一般用统计概率做分析。
对产生相同比较次数的初始化顺序数量做个统计，计算出对应概率，列表作图，横轴为比较次数（某类初始化顺序），纵轴为概率，就得到了一个比较次数的概率分布图。这图能解释很多问题。
从图中能得到最理想的比较次数，和最悲观的比较次数。这个表的数学期望（逐项比较次数X概率后累加），就是这个算法的平均比较次数，它反映了你这个算法的综合性能。
需要注意的是，这种分析是基于任一初始化顺序的出现是同概率的假设，如果实际需要处理的初始化顺序的分布不是同概率的，只需在计算对应概率时做些调整，也不麻烦。
一般不去建立单一初始化顺序与比较次数的关系，而是分类聚合，理由就是问题域不需要这样的粒度，那样分析反而会看不清楚二者的关系。