信息技术课程设计—冒泡算法的分析与设计课件.ppt

冒泡算法的分析与设计 第二讲：冒泡算法的分析与实现 课前回顾 冒泡实例 冒泡分析 冒泡实现 冒泡总结 巩固练习 2.1冒泡排序的实例 1.冒泡排序实例： 【从小到大】 2.1冒泡排序的实例 2. 冒泡实例总结： For i=1 to n-1 在d(i)、d(i+1)、…d(n)中通过位置互换最小数的存放在d(i)中；也就是选第i小的数放到第i号位置。 对冒泡排序：若待排序的序列有n个记录，那么最多进行n-1趟排序，最大比较次数为n（n-1）/2 。 2.2冒泡算法的分析 For i=1 to n-1 在d(i)、d(i+1)…d(n)中通过位置互换最小数的存放在d(i)中。也就是选第i小的数放到第i号位置 Next i 怎样把在d(i)、d(i+1)、…d(n)中通过位置互换把这些数中的最小数的存放在d(i)中 2.3核心算法的实现 2.5冒泡算法的实现 随堂练：冒泡算法填空 若将34，45，32，12，33从小到达冒泡排序， 那么排序过程中比较的次数有 次。 交换的次数有 次。 随堂练：冒泡算法填空 For i = 1 To 冒泡排序 递增 For j = To step If d(j) d(j - 1) Then End If Next j Next i 2.6冒泡算法总结与作业 算法总结 在要排序的一组数中，对当前还未排好序的范围内的全部数，自（上）左而（下）右对相邻的两个数依次进行比较和调整，让较大的数往右沉，较小的往左（上）冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。 课后作业 课后习题2.1、2.6、2.9 实验课上机实现冒泡算法 * 程序设计基础* 程序设计基础* 42 36 28 23 23 42 36 28 23 28 36 42 23 28 42 36 第一轮： 第二轮： 第三轮： ? 外层循环： 遍历N个数； 第i个数与剩下的n-i-1个数做比较； 即d(j)和d(j-1)之间的数据交换。 temp=d(j) d(j)=d(j-1) d(j-1)=temp 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 Next i 内层循环： 顺序不符： （了解） // ~· ****产生随机数**** ~·// Dim d(1 To 1000) As Integer Dim n As Integer Private Sub Command1_Click() Dim k, i As Integer n = Val(Text1.Text) Randomize timer List1.Clear For i = 1 To n k = Int(Rnd * 1000) List1.AddItem Str(k) d(i) = k Next i End Sub （掌握）//~· ****冒泡排序算法**** ~·// Private Sub Command2_Click() List2.Clear 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 Next i For i = 1 To n List2.AddItem Str(d(i)) Next i End Sub 5 9 交换d(j)和d(j-1)之间的数据 n-1 temp = d(j) d(j) = d(j - 1) d(j - 1) = temp n i+1 -1 * 程序设计基础* * *