CodePlayer

冒泡排序(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