34冒泡排序算法及程序实现.ppt

1．冒泡排序算法的基本思想冒泡排序是在一列数据中把较小(大)的数据逐次向上推移的一种排序技术。该算法的基本思想是把待排序的n个元素的数组看成是垂直堆放的一列数据，从最下面的一个元素起，自下而上地比较相邻的两个元素中的数据，将较小(大)的数据换到上面的一个元素中。重复这一过程，直到处理完最后两个元素中的数据，称为一趟加工。当第一趟加工完成时，最小(大)的数据已经上升到第一个元素的位置。然后对余下的n－1个元素重复上述处理过程，直至最后余下两个数据的比较和交换。由于每一趟加工都是将本趟最小(大)的数元素像气泡一样浮至本趟的顶端位置，所以称作冒泡排序。但冒泡也有变式，即将数组元素进行两两比较，若相邻两个元素中的数据不符合排序，就交换位置。某数组c共由4个元素构成，每个元素的值如下表所示：采用冒泡排序思想进行升序排序，从最下面的一个元素起，自下而上的比较相邻两个元素中的数据，整个排序过程如下所示：①第一趟加工处理过程：②第二趟加工处理过程：③第三趟加工处理过程：2．冒泡排序算法的程序实现冒泡排序程序的实现可用双重For循环来实现，外层For循环控制是第几遍加工，内层For循环控制进行排序的数组元素下标的变化范围。由于每趟加工完成后，进行排序的范围会发生变化(每趟减少一个)，故内层For循环变量的下界由外层循环变量决定。现有n个数据，分别存放在数组变量a(1Ton)当中，用冒泡排序算法表示结构如下：用冒泡排序算法程序实现的片段如下：Fori＝1Ton－1Forj＝nToi＋1Step－1Ifa(j)<a(j－1)Thent＝a(j)：a(j)＝a(j－1)：a(j－1)＝tEndIfNextjNexti当外循环变量i取1时，即第1趟加工时，内循环变量j的下界为i＋1(值为2)，即从a(n)开始自下而上的比较相邻的两个元素中的数，如果下面的数比上面的小，则相互交换，直到a(2)与a(1)的比较为止，这样第1趟加工后将最小的数放到了a(1)中；第2趟加工，内循环变量j的下界为3，直到a(3)和a(2)的比较为止，把最小的数放到了a(2)中；这样，经过n－1趟加工后，就完成了数组从小到大的排序。中间的If语句，完成相邻的两个元素的比较过程，如果下面的数a(j)比上面的数a(j－1)小，则交换a(j)与a(j－1)的值。用语句t＝a(j)：a(j)＝a(j－1)：a(j－1)＝t来实现。3．读程序时，判断冒泡排序的结果是从小到大还是从大到小，方法就是分析内循环中的条件判断语句，如果交换数据的条件是前面元素小于后面元素，如a(j)<a(j＋1)、a(j)>a(j－1)，则排序结果是从大到小。反之，如果交换数据的条件是前面元素大于后面元素，如a(j)>a(j＋1)、a(j)<a(j－1)，则排序结果是从小到大。注意：以下代码也可实现对数组h(共n个元素)进行冒泡排序：Fori＝1Ton－1Forj＝i＋1TonIfh(i)>h(j)Thent＝h(i):h(i)＝h(j):h(j)＝tEndIfNextjNexti本节课学习要理解冒泡排序算法的基本思想，能根据冒泡排序的思想，对一组数据进行冒泡排序。掌握冒泡排序算法的程序实现，能根据给出的题目自行编写冒泡程序。考查方式为选择题与填空题。数组元素从a(1)到a(6)的数据依次为“3、7、2、5、8、9”，经过该程序“加工”后，文本框Text1中显示的是()A．987B．235C．372D．732新学年开学安排坐位，需要先根据学生身高排好队。以下VB程序为排队程序，其中变量s为学生总数，数组n存储学生姓名，数组h存储学生身高(单位：厘米)。程序界面如下图所示。程序运行时，自动加载学生姓名与身高数据，点击“排队”按钮，按学生身高从低到高进行排序。实现该功能的程序代码如下：Dimn(1To60)AsStringDimh(1To60)AsIntegerConsts＝60PrivateSubCommand1_Click()DimiAsInteger,jAsIntegerDimtAsIntegerDimkAs①List1.ClearFori＝1Tos－1Forj＝i＋1TosIf②Thent＝h(i):h(i)＝h(j):h(j)＝t③EndIfNextjNextiFori＝1TosList1.AddItemn(i)&“:”&Str(h(i))NextiEndSub