冒泡排序法

冒泡排序法：

冒泡排序法（Bubble Sort）是所有排序算法中最简单、最基本的一种算法，它是一种相邻数据交换的排序方法

冒泡排序法概述 冒泡排序法的基本思想如下： 

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

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

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

此排序法就像气泡在水中向上浮一样，所以也称为气泡排序法。

提示 冒泡排序法也可使较大的记录排在前面。

假设需要排序的记录有n个，其关键字保存在数组a中，使用冒泡排序法，需对数组a进行n-1次扫描，完成排序操作，具体过

程如下：

（1）将A[n]与A[n-1]进行比较，若A[n]<A[n-1]，则交换两元素的位置。

（2）修改数组下标，使需要比较的两个元素为A[n-1]和A[n-2]，重复步骤1，对这两个元素进行比较。重复这个过程，直到

对A[2]和A[1]进行比较完为止。完成第1遍扫描。

（3）经过第1遍扫描后，最小的元素已经像气泡一样“浮”到最上面，即位于元素A[1]中了。接下来重复前面的步骤，进行第 2遍扫描，只是扫描到A[3]与A[2]进行比较完为止（因为A[1]中已经是最小的数据，不用再进行比较）。 （4）通过n-1遍扫描，前n-1个数都已经排序完成，最后一个元素A[n]肯定就是最大的数了。至此，完成排序操作。

提示 在以上描述中，为了让更容易理解，假设数组元素是保存在A[1]~A[n]中的，由于c/c++语言的数组元素下标是从0开始 的，因此，需要修改数组的下标。

下面以一组待排序的数据演示冒泡排序的过程，假设有6个需要排序的数据序列如下：

 69，65，90，37，92，6 

通过冒泡排序法对这6个数据进行排序，其排序过程如图所示。

第1遍从下向上扫描，首先对最后两个元素A[5]和A[4]进行比较，因92>6，将6上浮到A[4]，92下沉到A[5]。接着将A[4]中的6 和A[3]比较，6仍然较小，继续上浮至A[3]……这样经过n-1次比较，6上浮到A[0]，完成第1遍扫描。此时A[0]中保存着当前数列 中的最小数。完成最小数的冒泡过程。 

第2遍扫描仍然从A[5]开始，至A[1]时结束，将37上浮到A[1]。 

类似的方法，在第3遍扫描时，65上浮到A[2]中，至此，所有数都已按从小到大的顺序排列，但程序还需要进行第4遍和第5 遍的扫描，因为程序并不知道后面的数据是否为有序的。