前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >经典算法巡礼(一) -- 排序之冒泡排序

经典算法巡礼(一) -- 排序之冒泡排序

原创
作者头像
jiezhu
修改于 2018-09-17 03:54:50
修改于 2018-09-17 03:54:50
3500
举报
文章被收录于专栏:codingforevercodingforever

冒泡排序是一种简单的排序算法,相信绝大多数人学会的第一种排序算法就是她了。

事实上,她重复地遍历需要排序的元素,一次比较相邻的两个元素,如果不满足预先定义的比较条件,则交换;否则继续下一组元素比较,直至遍历完成需要排序的所有元素。当然,遍历需要排序的元素需要重复进行,直到没有需要排序的元素为止。遍历需要排序的元素时,每一次交换不满足顺序条件的元素就如同气泡一样,从元素序列的一端慢慢“上升”到序列的另一端,此现象如同水中冒气泡一样,此排序算法以此得名。

具体实现也较为简单,用golang表示如下:

代码语言:txt
AI代码解释
复制
		// Sort方法从数组头开始冒泡,将最小元素位置上升到最后,直到数组排序完成为止
		// Sort中参数类型Comparable为统一的可比较接口,若为整数数组排序,则Comparable为int即可
		// Sort中参数类型Compare为配合Comparable接口的比较方法,若为整数数组排序,则Compare即满足a int < a int即可
		func (this *BubbleSort) Sort(a []Comparable, compare Compare) {
			for i := 0; i < len(a); i++ {
				for j := 1; j < len(a)-i; j++ {
					if this.less(a[j], a[j-1], compare) {
						this.exch(a, j-1, j)
					}
				}
			}
		}

那么,冒泡排序的效率如何呢?事实上,她不咋滴。且看上述代码中的两重循环吧,这可是复杂度的恶梦啊。当然,很明显,她的时间复杂度O(N^2)

为了方便,我们以一次比较作为一次时间复杂度操作。根据冒泡排序的实现的思路,对长度为N的数组进行排序所需要的比较次数为N-1 + N-2 + ... + 1 + 0,即(N-1)/2*N = (N^2-N)/2 ~ N^2。可见,通用简单的数学计算,冒泡排序的时间复杂度确实就是O(N^2)

换种通俗的方式来说,冒泡排序的时间复杂度是平方级别的。因此,她只适合对少量元素进行排序,而无法用于大规模数据的排序,可谓是中看不中用啊。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
经典算法巡礼(二) -- 排序之选择排序
选择排序,如冒泡排序一样,从名字中即可大概猜测其排序的原理。其工作原理就是从未排序的数组中选出最大(小)的元素,将其放置至数组的首(尾)部,重复此过程直至没有未排序的子数组。
jiezhu
2018/09/02
4560
经典算法巡礼(三) -- 排序之插入排序
插入排序,与之前的冒泡排序和选择排序一样,其名称就说明了她的原理。所谓插入排序,就是对于数组中未排序的元素,依次遍历寻找合适的位置并插入到已排序的子数组中。当数组中没有未排序的元素时,插入排序即完成。
jiezhu
2018/09/02
3280
经典算法巡礼(六) -- 排序之快速排序
快速排序正如她的名字,她是一种排序效率相当高的算法,而且可能是应用最广泛的排序算法了。快速排序流行的原因是她实现简单,适用于各种不同的输入数据且在一般应用中比其他排序算法都要快。不仅如此,她与归并排序不同,她只需要很小的辅助空间就可以进行排序。
jiezhu
2018/09/02
4090
经典算法巡礼(四) -- 排序之希尔排序
希尔排序与之前的排序算法不同,她是以她的发明者Donald Shell来命名的。她是插入排序的一种改进版本。
jiezhu
2018/09/02
4300
经典算法巡礼(五) -- 排序之归并排序
归并排序是创建在归并操作上的一种有效排序算法。所谓归并操作,指的是将两个已经排序的序列合并成一个序列的操作。归并排序是分治思想的典型示范。
jiezhu
2018/09/02
3100
java编写冒泡排序源代码,用java实现冒泡排序算法,java冒泡算法
交换排序的基本思想是:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。
用户7886150
2021/04/28
3.9K0
排序之简单排序
在元素之间进行比较,而Java提供了一个接口Comparable就是用来定义排序规则的。
Rochester
2020/09/01
4280
排序之简单排序
经典算法学习之------冒泡排序
以下为经典教材《Introduction.to.Algorithms》开篇中的内容。
默 语
2024/11/20
620
经典算法学习之------冒泡排序
经典算法——冒泡排序
任何被明确定义的计算过程都可以称作 算法 ,它将某个值或一组值作为输入,并产生某个值或一组值作为输出。所以 算法可以被称作将输入转为输出的一系列的计算步骤 。
鱼找水需要时间
2023/02/16
5680
经典算法——冒泡排序
7.3.1 交换排序之冒泡排序
冒泡排序算法的基本思想是:假设待排序表长为n,从后往前(或从前往后)两两比较相邻元素的值。若为逆序(即A[i-1]>A[i]),则交换它们,直到序列比较完。我们称它为一趟冒泡。结果将最小的元素交换到待排序的第一个位置(关键字最小的元素如气泡一般逐渐往上漂浮,直到水面,这就是冒泡排序名字的由来)。下一趟冒泡时,前一趟确定的最小元素不再参与比较,待排序序列减少一个元素,每趟冒泡的结果把序列中的最小元素放到了序列的最终位置……,这样最多做n-1趟冒泡就把所有元素排好序。
week
2018/08/24
4550
算法之冒泡排序
冒泡排序算法需要遍历几次数组。每次遍历都要比较连续相邻的元素,如果某一对相邻元素是降序,则互换它们的值,否则,保持不变。由于较小的值像“气泡”一样逐渐浮想顶部,而较大的值沉向底部,所以叫冒泡排序。 冒
xiangzhihong
2018/02/01
7500
算法之冒泡排序
经典算法巡礼(七) -- 排序之堆排序
很多时候,我们需要处理有序的元素,但不一定要求它们全部有序,或是不一定要一次就将它们排序。比如你可能启动了若干个定时器,那么下一次处理定时器事件只需要考虑距离现在时间最近的定时器即可,定时器触发时间无须全部有序,只需要处理优化级最高的定时器即可。
jiezhu
2018/09/02
5040
Java数组全套深入探究——进阶知识阶段2、冒泡排序
总篇链接:https://laoshifu.blog.csdn.net/article/details/134906408
红目香薰
2023/12/11
2150
Java数组全套深入探究——进阶知识阶段2、冒泡排序
冒泡排序算法(Bubble Sort)—经典排序算法
冒泡排序是最基本、最简单的排序算法之一,它通过多次遍历待排序的数组或列表,依次比较相邻的元素并交换位置,使得较大(或较小)的元素逐渐“浮”到数组的一端。
一条晒干的咸鱼
2024/11/19
2620
冒泡排序算法(Bubble Sort)—经典排序算法
常用的排序算法之冒泡排序(Bubble Sort)
冒泡排序(Bubble Sort)是一种简单的排序算法,其名字来源于越小的元素会经由交换慢慢“浮”到数列的顶端(或越大的元素“沉”到底端),就如同气泡从水底冒到水面一样。虽然这个算法不是最高效的,但由于其实现简单直观,常常用于教学目的。
jack.yang
2025/04/05
1530
【数据结构】排序算法---冒泡排序(动图演示)
冒泡排序(英语:Bubble sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
Crossoads
2024/10/22
3820
【数据结构】排序算法---冒泡排序(动图演示)
简单而经典:Java中的冒泡排序算法详解
当谈到简单的排序算法时,冒泡排序(Bubble Sort)通常是其中之一。虽然它不是最高效的排序算法之一,但它的简单性和易于理解使它成为学习排序算法的良好起点。在本文中,我们将详细介绍Java中的冒泡排序。
修己xj
2023/09/25
14.4K0
简单而经典:Java中的冒泡排序算法详解
Python-排序-冒泡排序-优化
这是我通过极客专栏《数据结构与算法之美》学习后的思考,分享一下,希望对你有所帮助。上一篇文章 工作后,为什么还要学习数据结构与算法 的思维导图展现了这个专栏的内容。
somenzz
2020/12/10
6820
动图解析面试常见排序算法(上)
冒泡排序是一种非常简单的初级排序算法,它每次比较相邻的两个元素,如果顺序错误就进行交换.由于最小的元素是经由不断交换慢慢浮到顶端的,所以叫做冒泡排序.
周三不加班
2019/06/04
4670
动图解析面试常见排序算法(上)
Java基础(冒泡排序算法)
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,是不会再交换的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法
是阿超
2022/05/05
9000
Java基础(冒泡排序算法)
相关推荐
经典算法巡礼(二) -- 排序之选择排序
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档