数据结构排序，无论用什么排序方法，所用比较次数至少得是逆序对的个数，对不对，怎么说明？

数据结构排序，无论用什么排序方法，所用比较次数至少得是逆序对的个数，对不对，怎么说明？

这问法挺不科学的 因为有的排序方法不是基于比较的.............例如基数排序

如果问的是基于比较的排序方法中 目测也是错的 参照归并排序.......
如　
设有数列{6，202，100，301，38，8，1}
初始状态：6,202,100,301,38,8，1
第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
总的比较次数为：3+4+4=11,；
逆序数为14；追问对于任何一个只要是基于比较的排序算法，肯定存在一种比较糟糕的输入情况，使得至少需要logn！次比较，为什的？追答n个数有n!个可能的排列情况
也就是说基于比较的排序算法的判定树有n!个叶子结点
比较次数至少为log2(n!)=O(nlog2n)(斯特林公式)
清华那本数据结构书上有具体的分析，你可以看一下

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息