搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > MissKein > 排序算法系列1-冒泡排序

排序算法系列1-冒泡排序

MissKein 2020-06-30

  • 属于 比较算法 [1]
  • 英文简写:BUB

关注、评论、转发


定义

给定一个N个元素的数组,冒泡法排序将:

  1. 如果元素大小关系不正确,交换这两个数(在本例中为a> b),
  2. 比较一对相邻元素(a,b),
  3. 重复步骤1和2,直到我们到达数组的末尾(最后一对是第(N-2)和(N-1)项,因为我们的数组从零开始)
  4. 到目前为止,最大的元素将在最后的位置。然后我们将N减少1,并重复步骤1,直到N = 1。

举个例子🌰:[29,10,14,37,14]
第一次冒泡:[10,14,29,14,37]
第二次冒泡:[10,14,14,29,37]

时间复杂度

(标准)Bubble Sort中有两个嵌套循环。外循环正好运行N次迭代。但内部循环运行变得越来越短:

  1. 当 i = 0,(N-1)次迭代(比较和可能交换)时。
  2. 当 i = 1,(N-2)次迭代时,...
  3. 当 i =(N-2)时,1次迭代,
  4. 当 i=(N-1),0迭代. 因此,总迭代次数=(N-1)+(N-2)+ ... + 1 + 0 = N *(N-1)/ 2

总时间= c * N *(N-1)/ 2 = O(N^2)

分析

冒泡排序实际上是低效的,它的 时间复杂度为 O(N^2) 。

想象一下,我们有 N = 106 个数字。即使我们的计算机速度超快,并且可以在1秒内计算108次操作,但冒泡排序仍需要大约100秒才能完成。但是,它可以提前终止,例如, 尝试Bubble Sort上面显示的小型升序示例[3,6,11,25,39],它在O(N)时间结束。改进的思路很简单:如果我们通过内部循环完全不交换,这意味着数组已经排序,我们可以在这个点上停止冒泡排序。

讨论:虽然它使冒泡排序在一般情况下运行得更快,但这种改进的想法并没有改变冒泡排序的 O(N^2) 时间复杂性…为什么?

参考资料

[1]

什么是比较算法: 是指基于比较而比较,因为它们比较数组的元素并决定是否交换它们。


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《排序算法系列1-冒泡排序》的版权归原作者「MissKein」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注MissKein微信公众号

MissKein微信公众号:gh_388bc669893e

MissKein

手机扫描上方二维码即可关注MissKein微信公众号

MissKein最新文章

精品公众号随机推荐