第七节冒泡算法.doc

第七节 冒泡算法

学习目标
1、了解升序与降序排列
2、理解冒泡排序的基本思想
3、能用流程图描述冒泡排序
4、能理解冒泡排序的程序代码
*5、能编写冒泡排序程序

将一组数按从小到大（或从大到小）的次序进行排列，我们往往称为“排序”，其中按“从小到大”次序排列称为“升序”，而按“从大到小”次序排列称为“降序”。“排序”是计算机在进行信息处理时会经常遇到的问题之一。能够实现排序的方法有很多，从本节课起，我们将陆续向大家介绍几种较常见的排序算法，下面所介绍的这种方法被称为“冒泡排序法”。
以下以“升序”来说明。
冒泡排序法的主要思想是：先比较第一个与第二个数，如发现不是按升序排列，则交换两数，然后比较第二个数（可能是刚交换来的）与第三个数，如发现不是按升序排列，则交换两数，完成一轮比较后，最大的数据将“沉”到最下面；然后进行第二轮比较，也是从头至尾开始向后依次比较，第二轮结束后，次最大的数将“沉”到最后第二个位置。第三轮比较完成后，第三大的数将“沉”到最后第三个位置，依次类推，直到最后一轮剩下一个数，这个数必定是最小的数。
在排序过程中，值小的数好似水中气泡逐轮向上飘浮，值大的数好似石头沉入水底。通常把每一轮比较交换过程称为一次起泡。像这样，值较小的“气泡”慢慢地逐轮被“冒”到最上面，值较大的“石头”慢慢地逐轮被“沉”到最下面，我们形象地称之为“冒泡排序法”（有时也叫做比较交换法）。
［例1］用冒泡排序法编程实现“8，4，5，3”四个数的升序排列。
根据冒泡排序法的思想，排序过程分析如下：

⑴第一轮排序：
第一个数与第二个数比较，若第一个数大，则交换两数，这里8>4，交换两个数，此时，第一个位置变为4，第二个位置变为8，然后第二个位置数（刚交换来的）与第三位置数比较，即8与5比较，同样交换位置，此时第二个位置变为5，第三个位置变为8，同样第三位置数8与第四位置数3进行比较交换后，第三位置变为3，第四位置变为8。至此，最大数8已“沉”到最后，下次可不必参与比较了（共进行了3次比较）。
⑵第二轮排序：
第一个数4与第二个数5比较，不必交换，此时第一位置仍为4，第二位置仍为5，然后进行第二位置数5与第三位置数3比较，交换位置，此时，第一个数仍为4，第二个数变为3，第三位置变为5。至此，次最大数5也已“沉”到次最大位置了（共进行了2次比较）。
⑶第三轮排序：
第一个数4与第二个数3比较，交换位置。第一位置变为3，第二位置变为4。至此，较大的数已下“沉”，最小的数也已“浮”出来（共进行了1次比较）。
我们把每一轮排序详细过程列出一张表格：
冒
泡
过
程

变量
排序前
第一轮
第二轮
第三轮
参与比较数：8,4,5,3
参与比较数：4,5,3
参与比较数：4,3
共进行三次比较，其结果是最大数8沉到A(4)中
共进行二次比较，其结果是次最大数5沉到A(3)中
共进行一次比较，其结果是4沉到A(2)中
A（1）
8
4
4
4
4
4
3
A（2）
4
8
5
5
5
3
4
A（3）
5
5
8
3
3
5
5
A（4）
3
3
3
8
8
8
8
注：A(1)，A(2)，…，A(4)中分别存放六个数“8，4，5，3 ”
从上述排序过程可知：①共进行了3(4-1)轮，每一轮比较次数依次减少一次，每一轮将最大数置于最后位置；②对于每一轮i，从第一个数A（1）开始与它下一个数进行比较，共进行了4-i次比较。流程图如下：

开始
输入待排序数
冒泡法排序
结束
输出已排序数
i ＝ 1 → 3，＋1
对于每一轮i进行
4-i次比较

j ＝ 1 →4- i，＋1
下一个j值
A（j）,A(j+1)交换：
T=A(j) A(j)=A(j+1)
A(j+1)=T
Y
A(j) > A(j+1) ？
N
下一个i值

程序代码如下：

REM 冒泡法排序
DIM i AS INTEGER
DIM j AS INTEGER
DIM T AS INTEGER
DIM A(4) AS INTEGER
REM === 输入待排序数 ===
FOR i = 1 TO 4 STEP 1
INPUT A(i)
NEXT i
REM === 输入待排序数 ===
PRINT
REM === 冒泡法排序 ===
FOR i = 1 TO 3 STEP 1
FOR j = 1 TO 4-i STEP 1
IF A(j) > A(j+1) THEN
T=A(j)
A(j)=A(j+1)
A(j+1)=T
END if
NEXT j
NEXT i
REM === 冒泡法排序 ===
REM === 输出已排序数 ===
FOR i = 1 TO 4 STEP 1
PRINT A(i);
NEXT i
REM ====输出已排序数 ====
PRINT
END

练一练
1、对六个数“4，52，3，18，7，9”，请你用“冒泡排序法”基本思想进行手工升序排列。
2、你能否在例1参考程序中修改一些语句，使升序冒泡法改为降序冒泡法，并用数据验证。
3、如果要求将n个数按“升序”进行“冒泡”排序，请你写出相应的程序，并用六个数“4，52，3，18，7，9”对程序进行上机验证。