当前位置: 首页 > 技术随笔 > 冒泡排序入门详解

冒泡排序入门详解

冒泡排序(Bubble Sort)是计算机编程开发技术中一种较为简单的排序方法。

为了更好地理解其算法原理,我们先来看这样一个例子:
在操场上从左到右一字排开地站着A(181)、B(169)、C(187)、D(172)、E(163) 5名运动员(括号内为该运动员的身高cm数)。现在教练希望让他们从左到右、从低到高依次排列。

头脑稍微「转」得快的读者,可能一眼就看出来了该如何排列。显然,我们这里仅仅列举了5名运动员,所以很快地指出结果也不是什么困难的事情。但是,如果需要排序的运动员不是5,而是五百个、五千个甚至五万个,你还敢说自己拥有「火眼金睛」吗?

当然,我们使用冒泡排序算法编写好程序后,交由计算机处理,上面的问题都将不是问题。现在,我们就使用冒泡排序法,对五名运动员进行排序。

现在,教练让他们从左到右依次让相邻的两个人比较身高,如果左边的比右边的高,就交换位置。

首先,第1位的A(181)和第2位的B(169)比较身高,由于A(181)比较高,因此A和B交换位置:
B(169)、A(181)、C(187)、D(172)、E(163)
接着,第2位的A(181)和第3位的C(187)比较身高,由于C(187)比较高,因此不用交换位置:
B(169)、A(181)、C(187)、D(172)、E(163)
然后,第3位的C(187)和第4位的D(172)比较身高,由于C(187)比较高,因此C和D交换位置:
B(169)、A(181)、D(172)、C(187)、E(163)
最后,第4位的C(187)和第5位的E(163)比较身高,由于C(187)比较高,因此C和E交换位置:
B(169)、A(181)、D(172)、E(163)、C(187)

现在大家应该发现了,五名运动员中身高最高的C(187)已经按照我们的排序要求排在了最右边,他的位置可以固定不动了,也不用再参加排序了。

现在我们继续用这种排序方法,对前面4名运动员进行排序:

现在,第1位的B(169)和A(181)的继续比较身高,由于A(181)比较高,因此不用交换位置:
B(169)、A(181)、D(172)、E(163)、C(187)
接着,第2位的A(181)和第3位的D(172)比较身高,由于A(181)比较高,因此A和D交换位置:
B(169)、D(172)、A(181)、E(163)、C(187)
然后,第3位的A(181)和第4位的E(163)比较身高,由于A(181)比较高,因此A和E交换位置:
B(169)、D(172)、E(163)、A(181)、C(187)

由于C(187)在第一轮排序中就已经知道是所有人当中最高的了,因此第4位的A(181)不用再和C(187)比较。现在,我们有发现,除了最高的C(187)外,剩下4名运动员最高的、也是5名运动员中第二高的A(181)已经按照我们的排序要求排在右起第二个位置了。

同样的,如果剩下的3名运动员继续下一轮的比较,可以得出身高第三的D(172),并且在比较身高和交换位置之后,他会站在右起第三个位置。

剩下的2名运动员继续下一轮比较,于是身高第四的B(169)和身高第五的E(163)都按照我们的排序要求站好了位置。回过头来看,我们就会发现所有的运动员都已经按照从左到右、从低到高的顺序排列好了。

上面的这个排序过程,实际上就是冒泡排序法的排序过程。

冒泡排序,其实就是将所有的元素按照顺序依次让相邻的两个元素进行比较,如果两者之间的排序不符合要求,就相互交换位置。每一轮比较都可以确定某个极限元素(本轮参与比较的元素中最大或最小的元素)的正确位置,一旦确定后,该元素就不再参与下一轮的比较。经过多轮次的重复比较,直到只剩下一个元素无法比较为止,那么我们使用冒泡排序就已经将所有的元素都按照要求排列好了。

下面,我们使用Java来编写上述例子中使用冒泡排序法对运动员进行排序的代码:

// =====使用冒泡排序对表示5名运动员身高的数组heights进行从低到高的排序=====

// A(181)、B(169)、C(187)、D(172)、E(163)
int[] heights = { 181, 169, 187, 172, 163 };
int count = heights.length; // 参与排序的运动员总人数
// 外层循环控制比较身高的轮次数
for (int i = 0; i < count; i++) {
/*
 * comparedCount表示本轮需要参与比较的人数
 * 5个人进行第1轮比较只需要比较4次,所以第1轮参与比较的人数为count-1
 * 此外,每过一轮,都会确定一个人的位置,因此第i轮参与比较的人数为count-1-i
 */
	int comparedCount = count - 1 - i;
	//内层循环进行本轮身高的比较,并按照规则顺序交换位置
	for (int j = 0; j < comparedCount; j++) {
		int nextIndex = j + 1;
		if (heights[j] > heights[nextIndex]) {
			// 如果相邻两人左边的比右边的高,则交换位置
			int temp = heights[nextIndex];
			heights[nextIndex] = heights[j];
			heights[j] = temp;
		}
	}
}
// =====冒泡排序完成=====

// 输出排序结果:
for (int height : heights) {
	System.out.println(height);
}

上述Java代码输出如下:

163
169
172
181
187
10 0
我们认为: 用户的主要目的,是为了获取有用的信息,而不是来点击广告的。因此本站将竭力做好内容,并将广告和内容进行分离,确保所有广告不会影响到用户的正常阅读体验。用户仅凭个人意愿和兴趣爱好点击广告。
我们坚信:只有给用户带来价值,用户才会给我们以回报。
CodePlayer技术交流群1CodePlayer技术交流群1

帮朋友打一个硬广告:

P2P网贷系统(Java版本) 新年低价大促销,多年P2P技术积累,系统功能完善(可按需定制,可支持第三方存管、银行存管),架构稳定灵活、性能优异、二次开发快速简单。 另可提供二次开发、安装部署、售后维护、安全培训等一条龙服务。

外行看热闹,内行看门道。可以自信地认为,在系统设计上,比市面上的晓风、迪蒙、方维、绿麻雀、国融信、金和盛等P2P系统要好。
深圳地区支持自带技术人员现场考察源代码、了解主要技术架构,货比三家,再决定是否购买。

也可推荐他人购买,一旦完全成交,推荐人可获得实际售价 10% 的返现。
有意向者,详情请 点击这里 联系,工作时间立即回复。