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

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

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

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

		// 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)

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

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

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

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我是攻城师

在Scala里面如何使用正则处理数据

3195
来自专栏Bingo的深度学习杂货店

Q189 Rotate Array

Rotate an array of n elements to the right by k steps. For example, with n = 7 a...

3657
来自专栏技术小站

c++(二)

算数运算符:+,-,*,/,%,++,--  进行算数运算时,如果存在溢出,则把溢出的部分拿掉(浮点型的难以预测),如 int i=0xffffffff,j;j...

1041
来自专栏开发与安全

从零开始学C++之从C到C++(一):const与#define、结构体对齐、函数重载name mangling、new/delete 等

一、bool 类型 逻辑型也称布尔型,其取值为true(逻辑真)和false(逻辑假),存储字节数在不同编译系统中可能有所不同,VC++中为1个字节。 声明方式...

1920
来自专栏编程坑太多

Python 字典

1094
来自专栏用户2442861的专栏

Python之逻辑运算和缩进和选择if

作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢!

681
来自专栏一枝花算不算浪漫

[C#基础]基础知识一: 面向对象的基本知识.

42617
来自专栏前端学习心得

ES6核心特性(二)

1623
来自专栏我是攻城师

Scala中的case match语法

2613
来自专栏IT可乐

Java数据结构和算法(九)——高级排序

  春晚好看吗?不存在的!!!   在Java数据结构和算法(三)——冒泡、选择、插入排序算法中我们介绍了三种简单的排序算法,它们的时间复杂度大O表示法都是O(...

3926

扫码关注云+社区

领取腾讯云代金券