Java冒泡排序入门详解

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


未经允许请勿转载:程序喵 » Java冒泡排序入门详解

点  赞 (0) 打  赏
分享到: