第七节冒泡算法.doc

第七节 冒泡算法学习目标1、了解升序与降序排列2、理解冒泡排序的基本思想3、能用流程图描述冒泡排序4、能理解冒泡排序的程序代码*5、能编写冒泡排序程序 将一组数按从小到大（或从大到小）的次序进行排列，我们往往称为“排序”，其中按“从小到大”次序排列称为“升序”，而按“从大到小”次序排列称为“降序”。“排序”是计算机在进行信息处理时会经常遇到的问题之一。能够实现排序的方法有很多，从本节课起，我们将陆续向大家介绍几种较常见的排序算法，下面所介绍的这种方法被称为“冒泡排序法”。 以下以“升序”来说明。 冒泡排序法的主要思想是：先比较第一个与第二个数，如发现不是按升序排列，则交换两数，然后比较第二个数（可能是刚交换来的）与第三个数，如发现不是按升序排列，则交换两数，完成一轮比较后，最大的数据将“沉”到最下面；然后进行第二轮比较，也是从头至尾开始向后依次比较，第二轮结束后，次最大的数将“沉”到最后第二个位置。第三轮比较完成后，第三大的数将“沉”到最后第三个位置，依次类推，直到最后一轮剩下一个数，这个数必定是最小的数。在排序过程中，值小的数好似水中气泡逐轮向上飘浮，值大的数好似石头沉入水底。通常把每一轮比较交换过程称为一次起泡。像这样，值较小的“气泡”慢慢地逐轮被“冒”到最上面，值较大的“石头”慢慢地逐轮被“沉”到最下面，我们形象地称之为“冒泡排序法”（有时也叫做比较交换法）。例1用冒泡排序法编程实现“8，4，5，3”四个数的升序排列。根据冒泡排序法的思想，排序过程分析如下：第一轮排序：第一个数与第二个数比较，若第一个数大，则交换两数，这里84，交换两个数，此时，第一个位置变为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）8444443A（2）4855534A（3）5583355A（4）3338888 注：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)=TYA(j) A(j+1) ？N下一个i值程序代码如下：REM 冒泡法排序DIM i AS INTEGERDIM j AS INTEGERDIM T AS INTEGERDIM A(4) AS INTEGERREM = 输入待排序数 =FOR i = 1 TO 4 STEP 1INPUT A(i)NEXT iREM = 输入待排序数 =PRINTREM = 冒泡法排序 =FOR i = 1 TO 3 STEP 1FOR j = 1 TO 4-i STEP 1IF A(j) A(j+1) THEN T=A(j) A(j)=A(j+1) A(j+1)=T END ifNEXT jNEXT iREM = 冒泡法排序 =REM = 输出已排序数 =FOR i = 1 TO 4 STEP 1PRINT A(i);NEXT iREM =输出已排序数 =PRINTEND练一练1、对六个数“4，52，3，18，7，9”，请你用“冒泡排序法”基本思想进行手工升序排列。2、你能否在例1参考程序中修改一些语句，使升序冒泡法改为降序冒泡法，并用数据验证。3、如果要求将n个数按“升序”进行“冒泡”排序，请你写出相应的程序，并用六个数“4，52，3，18，7，9”对程序进行上机验证。