冒泡排序算法及程序实现ppt课件

1、1冒泡排序算法的基本思想 冒泡排序是在一列数据中把较小(大)的数据逐次向上推移的一种排序技术。该算法的基本思想是把待排序的n个元素的数组看成是垂直堆放的一列数据，从最下面的一个元素起，自下而上地比较相邻的两个元素中的数据，将较小(大)的数据换到上面的一个元素中。重复这一过程，直到处理完最后两个元素中的数据，称为一趟加工。当第一趟加工完成时，最小(大)的数据已经上升到第一个元素的位置。然后对余下的n1个元素重复上述处理过程，直至最后余下两个数据的比较和交换,34 冒泡排序算法及程序实现,由于每一趟加工都是将本趟最小(大)的数元素像气泡一样浮至本趟的顶端位置，所以称作冒泡排序。但冒泡也有变式，即将

2、数组元素进行两两比较，若相邻两个元素中的数据不符合排序，就交换位置。 某数组c共由4个元素构成，每个元素的值如下表所示,采用冒泡排序思想进行升序排序，从最下面的一个元素起，自下而上的比较相邻两个元素中的数据，整个排序过程如下所示： 第一趟加工处理过程,第一趟加工共比较3次，处理完成后，最小的元素15存储在了c(1)中,第二趟加工处理过程,第二趟加工共比较2次，处理完成后，第2个最小的元素23存储在了c(2)中,第三趟加工处理过程,第三趟加工共比较1次，处理完成后，第3个小的元素32存储在了c(3)中。 4个元素共需进行3趟加工处理，总的比较次数为3216次。 对n个元素的数组，用冒泡法进行排序

3、时，共需比较n(n1)/2次,2冒泡排序算法的程序实现 冒泡排序程序的实现可用双重For循环来实现，外层For循环控制是第几遍加工，内层For循环控制进行排序的数组元素下标的变化范围。由于每趟加工完成后，进行排序的范围会发生变化(每趟减少一个)，故内层For循环变量的下界由外层循环变量决定,现有n个数据，分别存放在数组变量a(1 To n)当中，用冒泡排序算法表示结构如下,用冒泡排序算法程序实现的片段如下： For i1 To n1 For jn To i1 Step 1 If a(j)a(j1) Then ta(j)：a(j)a(j1)：a(j1)t End If Next j Next i

4、 当外循环变量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读程序时，判断冒泡排序的

5、结果是从小到大还是从大到小，方法就是分析内循环中的条件判断语句，如果交换数据的条件是前面元素小于后面元素，如a(j)a(j1)，则排序结果是从大到小。反之，如果交换数据的条件是前面元素大于后面元素，如a(j)a(j1)、a(j)a(j1)，则排序结果是从小到大,注意：以下代码也可实现对数组h(共n个元素)进行冒泡排序： For i 1 To n 1 For j i 1 To n If h(i) h(j) Then t h(i): h(i) h(j): h(j) t End If Next j Next i,本节课学习要理解冒泡排序算法的基本思想，能根据冒泡排序的思想，对一组数据进行冒泡排序。掌

6、握冒泡排序算法的程序实现，能根据给出的题目自行编写冒泡程序。考查方式为选择题与填空题,某书店在5所学校流动售书量(单位：本)分别是82、113、46、69、35。采用冒泡排序对其进行排序，若完成第一遍时的结果是35、82、113、46、69，则完成第二遍时的结果是() A35、82、113、46、69 B35、46、82、69、113 C35、46、82、113、69 D35、46、69、82、113,C,2下表记录了6个数据的排序过程。分析表中数据可知，该排序采用的算法与排序方式分别为 (,冒泡排序，降序 选择排序，降序 冒泡排序，升序 选择排序，升序,C,3实现某排序算法的部分VB程序如下

7、： For i 1 To 4 For j 5 To i 1 Step 1 If a(j)a(j1) Then ta(j)：a(j)a(j1)：a(j1)t Next j Next i 在经过某一遍排序“加工”后，数组元素a(l)到a(5)的数据依次为“25、77、51、59、32”。则 下一遍排序“加工”后数组元素a(l)到a(5)的数据应该是 () A25、32、77、51、59 B25、32、51、59、77 C25、32、59、51、77 D25、32、51、7、59,A,4有一组原始数据：23、25、18、63、84、77、65、9、33、17。利用冒泡排序算法进行从小到大排序，最多需

8、要进行()次加工，才可以完成整个数据的排序。 A5B6C8D9,D,书籍将数据3、6、9、5、8、1进行一趟冒泡排序后得到的数据刚好是小杨的银行卡密码，那么小杨的银行卡密码是() A369581B136958 C135698D316958,B,在某年市机器人投蓝比赛决赛中，共有5支队伍参加，各队的最终成绩如下：82、74、66、95、70(单位：个/分钟)，现用冒泡排序算法来实现这些数据的排序操作,则在第2遍加工的操作中，共需要交换数据的次数是() A. 1次B. 2次C. 3次D. 4次,B,有如下VB程序段： s“ ” For i 1 To 3 For j 6 To i 1 Step 1

9、If a(j)a(j1) Then ka(j)：a(j)a(j1)：a(j1)k End If Next j s s str(a(i) Next i Text1.Textstr(s,数组元素从a(1)到a(6)的数据依次为“3、7、2、5、8、9”，经过该程序“加工”后，文本框Text1中显示的是() A9 8 7 B2 3 5 C3 7 2 D7 3 2,B,有一组原始数据：13、15、8、65、14、33。若采用冒泡法进行排序，则共需比较的次数为 () A21B15C10D28,B,设计一个VB程序，点击“随机产生15个整数”按钮，程序自动在列表框List1中产生15个1000以内的随机非

10、负数，点击“冒泡排序”按钮，对这些数据按冒泡算法进行从大到小排序。程序运行时界面如图91所示,图91,1)(1)设计应用程序界面时，为添加“冒泡排序”按钮，应使用如图92所示的“控件工具箱”中的_(填写相应编号)，并在图93所示的“属性”窗口中，将_属性值设置为“冒泡排序,4,Caption,图92,图93,2)从左至右的两个列表框的名称分别是List1和List2，“随机产生15个整数”按钮的名称是Command1，“冒泡排序”按钮的名称是Command2。请根据题意将下列程序补充完整。 Dim a(1 To 15) As Integer Dim n As Integer Private S

11、ub Command1_Click() n 15 Randomize List1.Clear List2.Clear For i 1 To 15 List1.AddItem Str(i) & “：” & Str(a(i) Next i End Sub,Private Sub Command2_Click() Dim t As Integer List2.Clear For i 1 To n 1 For j n To i 1 Step 1 If Then t a(j): a(j) a(j 1): a(j 1) t End If Next j Next i For i 1 To n List2.A

12、ddItem Str(i) & “:” & Str(a(i) Next i End Sub,1)程序中划线处应填入_。 (2)程序中划线处应填入_。 注：该示例程序在素材文件夹下vb23文件夹中,a(i)=Int(Rnd()*1001,a(j)a(j-1,新学年开学安排坐位，需要先根据学生身高排好队。以下VB程序为排队程序，其中变量s为学生总数，数组n存储学生姓名，数组h存储学生身高(单位：厘米)。程序界面如下图所示。程序运行时，自动加载学生姓名与身高数据，点击“排队”按钮，按学生身高从低到高进行排序,实现该功能的程序代码如下： Dim n(1 To 60) As String Dim h(1

13、 To 60) As Integer Const s 60 Private Sub Command1_Click() Dim i As Integer, j As Integer Dim t As Integer Dim k As List1.Clear For i 1 To s 1 For j i 1 To s If Then t h(i): h(i) h(j): h(j) t End If Next j Next i For i 1 To s List1.AddItem n(i) & “:” & Str(h(i) Next i End Sub,Private Sub Form_Load()

14、 学生姓名数据n赋值语句，此处省略 学生身高数据h赋值语句，此处省略 For i 1 To s List1.AddItem n(i) & “：” & Str(h(i)在列表框显示学生姓名与身高原始数据 Next i End Sub 为使程序完整，请在划线处填上合适的语句。 (1)划线处应填入_。 (2)划线处应填入_。 (3)划线处应填入_,String,h(i)h(j,k=n(i):n(i)=n(j):n(j)=k,叶锦平和同学们去农科院开展研究性学习，大家都收获很大，锦平设计了一个VB程序，他把同学们收集到的水稻亩产量和同学姓名已分别保存在数组a和数组b中，第i个同学收集的亩产量保存在a(

15、i)中，对应的同学姓名保存在b(i)中，最后按亩产量从高到低进行排序。 程序界面如图所示，左边列表框List1中显示的是所有同学收集到的原始数据，单击”排序”按钮(Command1)后，在右边的列表框List2中显示排序完成后的结果(按亩产量从高到低排列,解决此问题的算法流程图如图所示，相应的排序部分程序如下： Dim a(1 To n) As Single Dim b(1 To n) As String Private Sub Command1_Click() Dim i As Integer, j As Integer, c As Single, t As String List2.Clear For i 1 To n 1 设共有n名同学 For j If Then c a(j 1) a(j 1) a(j) a(j) c t b(j 1) b(j 1) b(j) b(j) t End If Next j Next i For i 1 To n List2.AddItem Str(a(i) “ ” b(i) Ne