冒泡排序算法

冒泡排序（Bubble Sort）算法是所有排序算法中最简单、最基本的一种。冒泡排序算法的思路就是交换排序，通过相邻数据的交换来达到排序的目的。

冒泡排序算法 

冒泡排序算法通过多次比较和交换来实现排序，其排序流程如下：

⑴对数组中的各数据，依次比较相邻的两个元素的大小。

⑵如果前面的数据大于后面的数据，就交换这两个数据。经过第一轮的多次比较排序后，便可将最小的数据排好。

⑶再用同样的方法把剩下的数据逐个进行比较，最后便可按照从小到大的顺序排好数组各数据。

为了更好地理解冒泡排序算法的执行过程，下面举一个实际数据的例子一步一步地执行冒泡排序算法。对于5个整型数据118、101、105、127、112，这是一组无序的数据。对于执行冒泡排序过程，如图1所示。

冒泡排序算法的执行步骤如下：

⑴第一次排序，从数组的尾部开始向前依次比较。首先是127和112比较，由于127大于112，因此将数据112向上移了一位；同理118和101比较，将数据101向前移了一位。此时排序后的数据为101、118、105、112、127。

⑵第二次排序，从数组的尾部开始向前依次比较。105和118比较，可以将数据105向前移一位。此时排序后的数据为101、105、118、112、127。

⑶第三次排序，从数组的尾部开始向前依次比较。由于112和118比较，可以将数据118向前移一位。此时排序后的数据为101、105、112、118、127。

⑷第四次排序时，此时，各个数据已经按顺序排列好，所以无须再进行数据交换。此时，排序的结果为101、105、112、118、127。

从上面的例子可以非常直观地了解到冒泡排序算法的执行过程。整个排序过程就像水泡的浮起过程，故因此而得名。冒泡排序算法在对n个数据进行排序时，无论原数据有无顺序，都需要进行n-1步的中间排序。这种排序方法思路简单直观，但是缺点是执行的步骤稍长，效率不高。

一种改进的方法，即在每次中间排序之后，比较一下数据是否已经按照顺序排列完成。如果排列完成则退出排序过程，否则便继续进行冒泡排序。这样，对于数据比较有规则的，可以加速算法的执行过程。

冒泡排序算法的示例代码如下：

void bubbleSort(int[] a) {

int temp;

for (int i = 1; i < a.length; i++) {

for (int j = 0; j < a.length - 1; j++) {

if(a[j]>a[j+1]) {

temp = a[j];

a[j] = a[j+1];

a[j+1] = temp;

}

}

System.out.print("第" + i + "步排序结果:");

for (int k = 0; k < a.length; k++) {

System.out.print(" " + a[k]);

}

System.out.print("\n");

}

}

在上诉代码中，输入参数a一般为一个数组的首地址。待排序的原数据便保存在数组a中，程序中通过两层循环来对数据进行冒泡排序。结合前面的冒泡排序算法加深理解。为了清除排序算法的执行过程，在排序的每一步都输出了当前的排序结果。

冒泡排序算法实例

学习了前面的冒泡排序算法的基本思想和算法之后。下面通过一个完整的例子说明冒泡排序法在整型数组排序中的应用，程序示例如下：

【程序】

public class Bubble_Sort {

static final int SIZE = 10;

public static void bubbleSort(int[] a) {

int temp;

for (int i = 1; i < a.length; i++) {

for (int j = 0; j < a.length - 1; j++) {

if (a[j] > a[j + 1]) {// 将相邻两个数进行比较，较大的数往后冒泡

// 交换相邻两个数

temp = a[j];

a[j] = a[j + 1];

a[j + 1] = temp;

}

}

System.out.print("第" + i + "步排序结果:");

for (int k = 0; k < a.length; k++) {

System.out.print(" " + a[k]);

}

System.out.print("\n");

}

}

public static void main(String[] args) {

int[] shuzu = new int[SIZE];

int i;

for (i = 0; i < SIZE; i++) {

shuzu[i] = (int) (100 + Math.random() * (100 + 1));

}

System.out.print("排序前的数组为: \n");

for (i = 0; i < SIZE; i++) {

System.out.print(shuzu[i] + " ");

}

System.out.print("\n");

bubbleSort(shuzu);

System.out.print("排序后的数组为: \n");

for (i = 0; i < SIZE; i++) {

System.out.print(shuzu[i] + " ");

}

System.out.print("\n");

}

}

在上诉代码中，程序定义了符号常量SIZE，用于表征需要排序整型数组的大小。在主方法中，首先声明一个整型数组，然后对数组进行随机初始化，并输出排序前的数组内容。接着，调用冒泡排序算法的方法来对数组进行排序。最后，输出排序后的数组。

该程序的执行结果，如图2所示。图中显示了每一步排序的中间结果。从中可以看出从第7步之后便已经完成对数据的排序，但是算法仍然需要进行后续的比较步骤。我们可以根据前面介绍的思路，加入判断部分，使之能够尽早结束排序过程，从而提高程序的执行效率。

                                                                                                    -------《Java常用算法手册》

图1 图2