冒泡排序 1、冒泡排序基本思想 将 n 个数据看作竖向排列的一组数据，每趟排序自下而上对每对相邻数据进行比较，若次序不 符合要求就进行交换，每趟排序结束时都能使排序范围内关键字最小的记录像一个气泡一样升到上 端的对应位置，整个排序过程共进行 n－1 趟，依次将关键字最小、次小……的各个数据冒到表的第 一个、第二个……位置上。 n  n  1 ★ 用冒泡排序对 n 个数据进行排序时，共需进行 n－1 趟排序，比较的总次数为 2 例 1：对 10 个数据进行冒泡排序，需要比较的次数是(　　) A.90 B.110 C.45 D.55 例 2：篮球联赛中，有 5 个班级的比赛积分依次为 14，11，13，8，9。若采用冒泡排序算法对其进 行从小到大排序，则完成第二遍时的结果是(　　) A.8，11，13，14，9 B.8，9，13，14，11 C.8，9，14，11，13 D.14，13，11，9，8 例 3：某书店在 5 所学校流动售书量(单位：本)分别是 88，110，48，64，35。采用冒泡排序法对其 进行排序，若完成第一遍时的结果是：35，88，110，48，64，则完成第二遍时的结果是(　　) A.35，88，110，48，64 B.35，48，88，64，110 C.35，48，88，110，64 D.35，48，64，88，110 例 4：某市组织了一次我心目中最喜爱的球队的评比活动， 6 个球队网上投票数为 201、287、501、189、397、295，若采用冒泡排序算法对其进行从大到小排序，则第三遍加工后的 结果是(　　) A.501 397 295 287 201 189 B.501 397 201 287 295 189 C.501 397 295 201 189 287 D.501 397 295 201 287 原数据 201 287 501 189 397 295 第一遍 第二遍 第三遍 501 201 287 397 189 295 501 397 201 287 295 189 189 2、冒泡排序程序实现 说明：以存放 d 数组 n 个数据升序为例的程序如下： 教材实例 冒泡变式 For i＝1 To n－1　 For j＝1 To n－i If d(j)＞d(j＋1) Then d(j)=d(j)＋d(j＋1)：d(j＋1)=d(j)－d(j＋1) d(j)=d(j)－d(j＋1) End If For i＝1 To n－1　 For j＝n To i＋1 Step －1 If d(j)＜d(j－1) Then temp＝d(j)：d(j)＝d(j－1)：d(j－1)＝temp End If 　Next j 1 　Next j Next i Next i ’降序只需将 d(j)＜d(j－1)改为 If d(j)＞d(j－1)即可 ★ temp＝d(j)：d(j)＝d(j－1)：d(j－1)＝temp 与 d(j)=d(j)＋d(j＋1)：d(j＋1)=d(j)－d(j＋1)：d(j)=d(j)－d(j＋1) 为两种不同的交换数组中数据的方式 例 1：有如下程序段： A.“118”，“15”，“2”，“36”，“88”，“98” s＝“” B.“118”，“15”，“36”，“88”，“98”，“2” For i＝1 To 3 C.“2”，“15”，“36”，“118”，“88”，“98” 　For j＝7 To i＋1 Step－1 D.“2”，“15”，“36”，“88”，“98”，“118” If a(j)＜a(j－1) Then 例 2：（浙江选考模拟)数组元素 a(1)到 a(5)的 5 　k＝a(j)：a(j)＝a(j－1)：a(j－1)＝k 个数据依次为“3，9，6，8，4” ，若采用如下排 End If 序算法 　Next j For i＝1 To 3 　s＝s＋Str(a(i)) For j＝1 To 5－i Next i If a(j)＞a(j＋1) Then Text1.Text＝s t＝a(j) 数 组 元 素 a(1) 到 a(7) 的 数 据 依 次 为 a(j)＝a(j＋1) “3，9，1，5，8，6，2”，经过该程序段“加工” a(j＋1)＝t 后，文本框 Text1 中显示的内容是(　　) End If A.1 2 3 B.9 8 6 Next j C.3 9 1 D.8 6 2 Text1.Text＝Text1.Text＋Str(a(i)) 例 3 ： 已 知 字 符 串 a(1) 到 a(6) 的 原 始 数 据 为 Next i “118”， 该程序执行后，文本框 Text1 显示的内容是（ “36”，“98”，“15”，“88”，“2”，为了对该数组进 ） 行排序操作，小吴编写了以下 VB 程序： A.3 4 6 B.6 8 9 For i＝1 to 3 C.3 6 4 D.3 6 6 例 4：冒泡排序在某一遍加工过程中没有数据交 For j＝6 to i＋1 step －1 换，说明数据已经有序，优化程序段如下 If a(j)＜a(j－1) Then i＝1：flag=True 　t＝a(j)：a(j)＝a(j－1)：a(j－1)＝t Do While i＜＝4 And flag＝True End if Next j flag=False For j＝5 To i＋1 Step －1 Next i 则程序运行之后，数据 a(1)到 a(6)的值依次为( ) 2 If a(j)＞a(j－1) i＝i＋1 t＝a(j)：a(j)＝a(j－1)：a(j－1)＝t Loop flag＝True 数 组 元 素 a(1) 到 a(5) 的 值 依 次 为 End if “48，36，24，97，77”，经过该程序段“加工”，i 的值为 Next j ※ 随堂练习 1、有一个数组，采用冒泡排序，第一遍排序后的结果为：4，10，5，32，6，7，9，17，24 那么该 数组的原始顺序不可能的是(　 　) A．10，5，32，6，7，9，17，24，4 B．10，5，32，6，7，9，4，17，24 C．10，5，32，4，6，7，9，17，24 D．4，10，5，32，17，9，24，6，7 2、（金华一中 11）有如下程序段： For i = 1 To 2 For j = 1 To 7-i 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 数组元素 a（1）到 a（7）的值依次为“44，24，33，67，77，58，12”，经过该程序段“加工”后，数 组元素 a（1）到 a（5）的值依次为（ ） A.12，24，44，33，58 B.12，24，33，67，77 C.24，33，44，58，12 D.44，24，33，58，12 3、有如下 VB 程序段： Dim a(1 to 6)as String i＝1 Do While i <＝ 2 For j ＝ i To 5 　If a(j)>a(j＋1) Then 　t＝a(j)：a(j)＝a(j＋1)：a(j＋1)＝t 　 End If Next j Text1.Text ＝ Text1.Text ＋ ” ” ＋ a(i) 3 i＝i＋1 Loop 数组元素 a(1)到 a(6)的值分别为”9”，”121”，”58”，”34”，”78”，”21”，程序运行后，文本框 Text1 中 显示的内容为(　 　) A．9　34 B．9　21 C．121　34 D．121　21 4、某排序算法的 VB 程序段如下： For i ＝ 1 To 2 For j ＝ 1 To 6－2*i If a(j)<a(j＋2) Then 　　　 　t＝a(j)：a(j)＝a(j＋2)：a(j＋2)＝t End If Next j Next i 数组元素 a(1)～a(6)的初始值依次为“15，13，44，38，26，7”，执行该程序段后，数组 a 元素的值分 别为(　 　) A．44，38，26，13，15，7 B．44，7，26，13，15，38 C．15，38，26，13，44，7 D．44，38，26，15，13，7 5、有如下 VB 程序段： 执行程序后，a 数组各元素可能是 (　　) For i ＝ 1 To 6 A．1，2，3，4，5，6 　a(i) ＝ Int(Rnd() * 10) ＋ 1 B．1，0，3，6，5，8 　If a(i) Mod 2 <> i Mod 2 Then C．3，2，7，6，11，8 i＝i－1 D．2，1，4，3，10，9 6、有如下 VB 程序段： End If Next i n＝8 For i ＝ 1 To 5 For i ＝ 1 To n For j ＝ 6 To i ＋ 2 Step －1 d(i) ＝ Int(Rnd * 10) ＋ 1 If a(j) < a(j － 2) Then Next i 　　　t＝a(j)：a(j)＝a(j－2)：a(j－2)＝t For i ＝ 2 To n － 1 End If k＝1 Next j For j ＝ 1 To n － i Next i If d(j)*k>d(j＋2)*k Then　 4 执行该程序段后，d 数组各元素可能是(　　) temp＝d(j)：d(j)＝d(j＋2)：d(j＋2)＝temp End If A．3，10，3，5，4，4，10，1 k ＝ －k B．0，3，4，5，6，6，7，8 Next j C．2，1，3，4，5，6，8，7 Next i D．6，4，5，6，5，7，1，10 5 选择排序 ※ 选择排序的基本思想 每趟排序是在所有的数据中找出最小(或最大)的数据，使它与第一个数据相互交换位置，然后 再在剩下的数据中找出最小(或最大)的数据，与第二个数据相互交换位置，以此类推，直到所有元 素成为一个有序序列。 例 ： 一 次 运 动 会 上 ， 某 组 6 位 选 手 的 百 米 成 绩 ( 单 位 ： 秒 ) 分 别 是 “14.1、12.3、11.2、14.8、13.9、11.0”，若使用选择排序法将该组的成绩按第一名、第二名、第三名 ……的顺序排序，则第一次交换数据后的顺序是(　　) A.14.8　14.1　12.3　11.2