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

1冒泡排序算法的基本思想冒泡排序算法的基本思想冒泡排序是在一列数据中把较小冒泡排序是在一列数据中把较小(大大)的数据逐次向上推移的数据逐次向上推移的一种排序技术。该算法的基本思想是把待排序的的一种排序技术。该算法的基本思想是把待排序的n个元素的数个元素的数组看成是垂直堆放的一列数据，从最下面的一个元素起，自下组看成是垂直堆放的一列数据，从最下面的一个元素起，自下而上地比较相邻的两个元素中的数据，将较小而上地比较相邻的两个元素中的数据，将较小(大大)的数据换到的数据换到上面的一个元素中。重复这一过程，直到处理完最后两个元素上面的一个元素中。重复这一过程，直到处理完最后两个元素中的数据，称为一趟加工。当第一趟加工完成时，最小中的数据，称为一趟加工。当第一趟加工完成时，最小(大大)的的数据已经上升到第一个元素的位置。然后对余下的数据已经上升到第一个元素的位置。然后对余下的n1个元素个元素重复上述处理过程，直至最后余下两个数据的比较和交换。重复上述处理过程，直至最后余下两个数据的比较和交换。34 冒泡排序算法及程序实现冒泡排序算法及程序实现由于每一趟加工都是将本趟最小由于每一趟加工都是将本趟最小(大大)的数元素像气泡一的数元素像气泡一样浮至本趟的顶端位置，所以称作冒泡排序。但冒泡也有变样浮至本趟的顶端位置，所以称作冒泡排序。但冒泡也有变式，即将数组元素进行两两比较，若相邻两个元素中的数据式，即将数组元素进行两两比较，若相邻两个元素中的数据不符合排序，就交换位置。不符合排序，就交换位置。某数组某数组c共由共由4个元素构成，每个元素的值如下表所示：个元素构成，每个元素的值如下表所示：数组元素数组元素c(1)c(2)c(3)c(4)值值23383015采用冒泡排序思想进行升序排序，从最下面的一个元素采用冒泡排序思想进行升序排序，从最下面的一个元素起，自下而上的比较相邻两个元素中的数据，整个排序过程起，自下而上的比较相邻两个元素中的数据，整个排序过程如下所示：如下所示：第一趟加工处理过程：第一趟加工处理过程：第一趟加工共比较第一趟加工共比较3次，处理完成后，最小的元素次，处理完成后，最小的元素15存储存储在了在了c(1)中。中。第二趟加工处理过程：第二趟加工处理过程：第二趟加工共比较第二趟加工共比较2次，处理完成后，第次，处理完成后，第2个最小的元素个最小的元素23存储在了存储在了c(2)中。中。第三趟加工处理过程：第三趟加工处理过程：第三趟加工共比较第三趟加工共比较1次，处理完成后，第次，处理完成后，第3个小的元素个小的元素32存储在了存储在了c(3)中。中。4个元素共需进行个元素共需进行3趟加工处理，总的比较次数为趟加工处理，总的比较次数为3216次。次。对对n个元素的数组，用冒泡法进行排序时，共需比较个元素的数组，用冒泡法进行排序时，共需比较n(n1)/2次。次。2冒泡排序算法的程序实现冒泡排序算法的程序实现冒泡排序程序的实现可用双重冒泡排序程序的实现可用双重For循环来实现，外层循环来实现，外层For循环控制是第几遍加工，内层循环控制是第几遍加工，内层For循环控制进行排序的循环控制进行排序的数组元素下标的变化范围。由于每趟加工完成后，进行排数组元素下标的变化范围。由于每趟加工完成后，进行排序的范围会发生变化序的范围会发生变化(每趟减少一个每趟减少一个)，故内层，故内层For循环变量循环变量的下界由外层循环变量决定。的下界由外层循环变量决定。现有现有n个数据，分别存放在数组变量个数据，分别存放在数组变量a(1Ton)当中，用当中，用冒泡排序算法表示结构如下：冒泡排序算法表示结构如下：用冒泡排序算法程序实现的片段如下：用冒泡排序算法程序实现的片段如下：Fori1Ton1ForjnToi1Step1Ifa(j)a(j1)Thenta(j)：a(j)a(j1)：a(j1)tEndIfNextjNexti当外循环变量当外循环变量i取取1时，即第时，即第1趟加工时，内循环变量趟加工时，内循环变量j的下界为的下界为i1(值为值为2)，即从，即从a(n)开始自下而上的比较相邻的两个元素中的数，如果下开始自下而上的比较相邻的两个元素中的数，如果下面的数比上面的小，则相互交换，直到面的数比上面的小，则相互交换，直到a(2)与与a(1)的比较为止，这样第的比较为止，这样第1趟加工后将最小的数放到了趟加工后将最小的数放到了a(1)中；第中；第2趟加工，内循环变量趟加工，内循环变量j的下界为的下界为3，直到，直到a(3)和和a(2)的比较为止，把最小的数放到了的比较为止，把最小的数放到了a(2)中；这样，经过中；这样，经过n1趟加工后，就完成了数组从小到大的排序。趟加工后，就完成了数组从小到大的排序。中间的中间的If语句，完成相邻的两个元素的比较过程，如果语句，完成相邻的两个元素的比较过程，如果下面的数下面的数a(j)比上面的数比上面的数a(j1)小，则交换小，则交换a(j)与与a(j1)的的值。用语句值。用语句ta(j)：a(j)a(j1)：a(j1)t来实现。来实现。3读程序时，判断冒泡排序的结果是从小到大还是从读程序时，判断冒泡排序的结果是从小到大还是从大到小，方法就是分析内循环中的条件判断语句，如果交大到小，方法就是分析内循环中的条件判断语句，如果交换数据的条件是前面元素小于后面元素，如换数据的条件是前面元素小于后面元素，如a(j)a(j1)，则排序结果是从大到小。反之，如果交换数据的条，则排序结果是从大到小。反之，如果交换数据的条件是前面元素大于后面元素，如件是前面元素大于后面元素，如a(j)a(j1)、a(j)h(j)Thenth(i):h(i)h(j):h(j)tEndIfNextjNexti本节课学习要理解冒泡排序算法的基本思想，能根本节课学习要理解冒泡排序算法的基本思想，能根据冒泡排序的思想，对一组数据进行冒泡排序。掌握冒据冒泡排序的思想，对一组数据进行冒泡排序。掌握冒泡排序算法的程序实现，能根据给出的题目自行编写冒泡排序算法的程序实现，能根据给出的题目自行编写冒泡程序。考查方式为选择题与填空题。泡程序。考查方式为选择题与填空题。1.某书店在某书店在5所学校流动售书量所学校流动售书量(单位：本单位：本)分别是分别是82、113、46、69、35。采用冒泡排序对其进行排序，若。采用冒泡排序对其进行排序，若完成第一遍时的结果是完成第一遍时的结果是35、82、113、46、69，则完，则完成第二遍时的结果是成第二遍时的结果是()A35、82、113、46、69B35、46、82、69、113C35、46、82、113、69D35、46、69、82、113C C 2下表记录了下表记录了6个数据的排序过程。分析表中数据可知，个数据的排序过程。分析表中数据可知，该排序采用的算法与排序方式分别为该排序采用的算法与排序方式分别为()原始数据原始数据635759424571第第1遍遍426357594571第第2遍遍424563575971第第3遍遍424557635971A.冒泡排序，降序冒泡排序，降序B.选择排序，降序选择排序，降序C.冒泡排序，升序冒泡排序，升序D.选择排序，升序选择排序，升序C C 3实现某排序算法的部分实现某排序算法的部分VB程序如下：程序如下：Fori1To4Forj5Toi1Step1Ifa(j)a(j1)Thenta(j)：a(j)a(j1)：a(j1)tNextjNexti在经过某一遍排序在经过某一遍排序“加工加工”后，数组元素后，数组元素a(l)到到a(5)的数据依次的数据依次为为“25、77、51、59、32”。则。则下一遍排序下一遍排序“加工加工”后数组元后数组元素素a(l)到到a(5)的数据应该是的数据应该是()A25、32、77、51、59B25、32、51、59、77C25、32、59、51、77D25、32、51、7、59A A 4有一组原始数据：有一组原始数据：23、25、18、63、84、77、65、9、33、17。利用冒泡排序算法进行从小到大排序，最多需。利用冒泡排序算法进行从小到大排序，最多需要进行要进行()次加工，才可以完成整个数据的排序。次加工，才可以完成整个数据的排序。A5B6C8D9D D 5.书籍将数据书籍将数据3、6、9、5、8、1进行一趟冒泡排序进行一趟冒泡排序后得到的数据刚好是小杨的银行卡密码，那么小后得到的数据刚好是小杨的银行卡密码，那么小杨的银行卡密码是杨的银行卡密码是()A369581B136958C135698D316958B B 6.在某年市机器人投蓝比赛决赛中，共有在某年市机器人投蓝比赛决赛中，共有5支队伍参支队伍参加，各队的最终成绩如下：加，各队的最终成绩如下：82、74、66、95、70(单位：个单位：个/分钟分钟)，现用冒泡排序算法来实现这，现用冒泡排序算法来实现这些数据的排序操作：些数据的排序操作：原始数据原始数据8274669570第第1遍遍6682747095第第2遍遍第第3遍遍6670748295第第4遍遍6670748295则在第则在第2遍加工的操作中，共需要交换数据的次数遍加工的操作中，共需要交换数据的次数是是()A.1次次B.2次次C.3次次D.4次次B B 7.有如下有如下VB程序段：程序段：s“”Fori1To3Forj6Toi1Step1Ifa(j)a(j-1)10.新学年开学安排坐位，需要先根据学生身高排好队。以新学年开学安排坐位，需要先根据学生身高排好队。以下下VB程序为排队程序，其中变量程序为排队程序，其中变量s为学生总数，数组为学生总数，数组n存储学生姓名，数组存储学生姓名，数组h存储学生身高存储学生身高(单位：厘米单位：厘米)。程。程序界面如下图所示。程序运行时，自动加载学生姓名与序界面如下图所示。程序运行时，自动加载学生姓名与身高数据，点击身高数据，点击“排队排队”按钮，按学生身高从低到高进按钮，按学生身高从低到高进行排序。行排序。实现该功能的程序代码如下：实现该功能的程序代码如下：Dimn(1To60)AsStringDimh(1To60)AsIntegerConsts60PrivateSubCommand1_Click()DimiAsInteger,jAsIntegerDimtAsIntegerDimkAsList1.ClearFori1Tos1Forji1TosIfThenth(i):h(i)h(j):h(j)tEndIfNextjNextiFori1TosList1.AddItemn(i)&“:”&Str(h(i)NextiEndSubPrivateSubForm_Load()学生姓名数据学生姓名数据n赋值语句，此处省略赋值语句，此处省略学生身高数据学生身高数据h赋值语句，此处省略赋值语句，此处省略Fori1TosList1.AddItemn(i)&“：”&Str(h(i)在在列表框显示学生姓名与身高原始数据列表框显示学生姓名与身高原始数据NextiEndSub为使程序完整，请在划线处填上合适的语句。为使程序完整，请在划线处填上合适的语句。(1)划线划线处应填入处应填入_。(2)划线划线处应填入处应填入_。(3)划线划线处应填入处应填入_。Stringh(i)h(j)k=n(i):n(i)=n(j):n(j)=k11.叶锦平和同学们去农科院开展研究性学习，大家都收获叶锦平和同学们去农科院开展研究性学习，大家都收获很大，锦平设计了一个很大，锦平设计了一个VB程序，他把同学们收集到的水程序，他把同学们收集到的水稻亩产量和同学姓名已分别保存在数组稻亩产量和同学姓名已分别保存在数组a和数组和数组b中，第中，第i个同学收集的亩产量保存在个同学收集的亩产量保存在a(i)中，对应的同学姓名保中，对应的同学姓名保存在存在b(i)中，最后按亩产量从高到低进行排序。中，最后按亩产量从高到低进行排序。程序界面如图所示，左边列表框程序界面如图所示，左边列表框List1中显示的是所有同中显示的是所有同学收集到的原始数据，单击学收集到的原始数据，单击”排序排序”按钮按钮(Command1)后，在右边的列表框后，在右边的列表框List2中显示排序完成后的结果中显示排序完成后的结果(按按亩产量从高到低排列亩产量从高到低排列)。解决此问题的算法流程图如图所示，相应的排序部分程序如下：解决此问题的算法流程图如图所示，相应的排序部分程序如下：Dima(1Ton)AsSingleDimb(1Ton)AsStringPrivateSubCommand1_Click()DimiAsInteger,jAsInteger,cAsSingle,tAsStringList2.ClearFori1Ton1设共有设共有n名同学名同学ForjIfThenca(j1)a(j1)a(j)a(j)ctb(j1)b(j1)b(j)b(j)tEndIfNextjNextiFori1TonList2.AddItemStr(a(i)“”b(i)NextiEndSubPrivateSubForm_Load()此过程用于对数组此过程用于对数组a和数组和数组b进行初始赋值，代码略进行初始赋值，代码略List1.AddItemStr(a(i)“”b(i)在列表框在列表框List1中显示原始数据中显示原始数据EndSub(1)解决此问题的算法是解决此问题的算法是_。在程序在程序和和划线处填入适当的语句或表达式，将划线处填入适当的语句或表达式，将程序补充完整：程序补充完整：(2)程序中程序中划线处应填入划线处应填入_。(3)程序中程序中划线处应填入划线处应填入_。注：该示例程序在素材文件夹下注：该示例程序在素材文件夹下vb25文件夹中。文件夹中。冒泡排序算法冒泡排序算法ntoi+1Step-1a(j)a(j-1)