首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >冒泡排序的最佳情况

问冒泡排序的最佳情况
EN

Stack Overflow用户
提问于 2009-08-31 17:13:24
回答 9查看 54K关注 0票数 10

我想知道冒泡排序最好的情况是什么?例如,可能存在这样一种情况,其中可能没有对所说的最后2次传递的交换。我正在用C语言编写我的程序。假设我有一个由5个元素组成的数组,我给出的元素是1,2,5,4,3,那么在最后的2次传递中不会有任何变化?

EN

回答 9

Stack Overflow用户

发布于 2009-08-31 17:14:35

最好的情况是一次通过。列表应该已经被排序了。

无交换=完成。

票数 29
EN

Stack Overflow用户

发布于 2009-12-27 16:49:58

最好的情况:最好的情况是列表已经排序。a)会有比较,但没有交换,执行时间在O(n2) b),但如果我们跟踪每一遍中的交换,并终止程序,检查是否没有交换。那么程序将只需要一次传递和最大值。在单遍中需要(n-1)个比较,我们可以说复杂度是O(n)的数量级。

票数 26
EN

Stack Overflow用户

发布于 2009-08-31 17:15:28

请参阅Bubble sort

冒泡排序的最坏情况和平均复杂度都是О(n²),其中n是要排序的项数。存在许多排序算法,它们的最坏情况或平均复杂度为O( n )。甚至其他О(n²)排序算法,如插入排序,往往比冒泡排序具有更好的性能。因此,当n较大时,冒泡排序并不是一种实用的排序算法。

  • Worst case performance O(n²)
  • Best case performance
    • Worst case performance O(n²)
    • Best case performance O(n) O(N),O(1) case performance No
票数 12
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/1358383

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档