文章/答案/技术大牛

发布

社区首页 >问答首页 >一种确定比较数量的公式？

问一种确定比较数量的公式？
EN

Stack Overflow用户

提问于 2018-12-05 03:09:26

回答 1查看 1.3K关注 0票数 0

我很好奇是否有公式/规则来查找排序算法中的比较总数，特别是合并排序、选择排序和插入排序。我非常肯定，对于选择排序，规则是n(n-1)/2，其中n是被排序的元素的数量。我认为插入排序的情况也是如此，但根据我参加的实践Java测试，情况显然并非如此(根据答案键，插入排序列出了6个条目，进行了14次比较，与选择的排序进行了15次比较)。所以我现在很困惑。

sorting

merge

selection

insertion

java

回答 1

Stack Overflow用户

回答已采纳

发布于 2018-12-05 03:19:23

一般来说，由于以下几个原因，没有精确的公式：

在实现各种排序算法时，有足够的变化空间，使得同一算法的不同实现之间可能存在很小的差异。
在某些算法中，比较的次数取决于元素及其初始阶数。

当然，不存在“一刀切”的公式，它涵盖了(比如说)相同复杂性类中的所有算法。

一条线索:如果排序算法的最佳或最坏情况复杂度与其平均复杂度不同，则比较次数或移动次数取决于输入。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/53624602

复制

相似问题

问一种确定比较数量的公式？
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问一种确定比较数量的公式？EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问一种确定比较数量的公式？
EN