浙教版信息技术选修1 5.3 排序算法的程序实现（共30张ppt)

课件30张PPT。排序算法的分析及实现 冒泡排序和选择排序３交换数据的实现(A=3:B=5)ＡＢ5C=A３ＣＡＢ5A=BC=A交换数据的实现(A=3:B=5)３5ＣＡＢB=CA=BC=A交换数据的实现(A=3:B=5)数组为了存储一组数据,我们需要用到数组变量例如 dim d(1 to 1000) as integer定义了一个整数类型的数组变量d, 下标从1到1000排序的意义排序是为了将一组杂乱的数据变成一组有序的数据。（递增或递减）如何实现将较小数逐次从下向上推移呢？从最后一个元素起，依次比较相邻的两个元素中的数据,将较小的数据调换到上面。冒泡排序算法冒泡排序法是简单的排序方法之一，它和气泡从水中往
上冒的情况有些类似。
方法 ：是在一列数据中把较小的数逐次向上推移的一种排序技术。原始序列最终序列用数组来存储一系列同类型的数据, 然后调整数组中的元素

dim d(1 to 4) as integer ‘定义一个数组变量d例：将以下四个数组元素用冒泡法进行排序(从小到大)d(1)=27 d(2)=36 d(3)=32 d(4)=18冒泡排序两个数进行数据交换,就象两杯水进行交换,需要再拿一个空杯（1）第一遍冒泡（最小数冒到最上面）（1）第一遍冒泡（最小数冒到最上面）（1）第一遍冒泡（2）第二遍冒泡（3）第三遍冒泡（1）第一遍冒泡4 3if d(4)jj-1if d(3) if d(j)Next jjj-1jj-1if d(j) if d(j)Next jjj-1（3）第三遍冒泡For j=4 to 4 step -1
if d(j)Next j（1）第一遍冒泡（2）第二遍冒泡（3）第三遍冒泡For j=4 to 2 step -1
if d(j)Next jFor j=4 to 3 step -1
if d(j)Next jFor j=4 to 4 step -1
if d(j)Next j
For j=4 to 2 step -1
if d(j)Next j
For j=4 to 3 step -1
if d(j)Next j
For j=4 to 4 step -1
if d(j)Next j第一遍第二遍第三遍J从4到2J从4到3J从4到4i=1i=2i=3i=1…2…3
For j=4 to i+1 step -1
if d(j)Next jFor i = 1 To 3(num-1)
Next i For j = 4(num) To i + 1 Step -1

Next jIf d(j) < d(j - 1) Then

End Ifk = d(j): d(j) = d(j - 1): d(j - 1) = kNum:数组元素的个数
问：5个数比较怎么改？交换d(j) 和d(j-1)的值算法分析以i表示次数练习：随机产生10个整数，并用冒泡法排序（从小到大）。（从后往前 小的数向前上升）
Dim a(1 To 10) As Integer
Dim i,j, t As Integer
Print "排序前："
Randomize
For i = 1 To 10
a(i) = Int(Rnd * 100)
Print a(i);
Next i
For j = 1 To 9
For i = 10 To j+1 Step -1
If a(i) < a(i - 1) Then
t = a(i)
a(i) = a(i - 1)
a(i - 1) = t
End If
Next i
Next j
Print
Print "排序后："
For i = 1 To 10
Print a(i);
Next i第一遍:j=1
a(10)与a(9)比较后(如果a(10)小于a(9),进行互换处理。）
a(9)与a(8)比较后处理
…
a(2)与a(1)比较后处理
第二遍:j=2
a(10)与a(9)比较后处理
…
a(3)与a(2)比较后处理
第三遍:j=3
….
第九遍:j=9
a(10)与a(9)比较后处理
j=10循环结束。10个数排序的核心代码For j = 1 To 9
For i = 10 To j+1 Step -1
If a(i) < a(i - 1) Then
t = a(i)
a(i) = a(i - 1)
a(i - 1) = t
End If
Next i
Next j小结：1、冒泡排序：是指把n个要排序的数看成一垂直列，从最下面的数开始两两比较相邻的两个数，把小的数向上换，经过n-1遍处理以达到排序目的的一种排序方法。2、如果有n个数组的元素进行排序，则要进行n-1趟冒泡…….
第n-1趟冒泡要经过1次比较第一趟冒泡要经过n-1次比较第二趟冒泡要经过n-2次比较总计:(n-1)+(n-2)+(n-3)+………+2+1=n(n-1)/23、双重循环的特点？“外一次，内一轮”。
选择排序算法选择排序算法是对冒泡排序算法的改进。
这种方法是在参加排序的所有数组元素中找出最小（或最大）数据的元素，使它与第一个元素中的数据相互交换位置。然后再在余下的元素中找出最小（或最大）的数据的元素，与第二个元素中的数据相互交换位置。以此类推，直到所有的元素成为一个有序的序列。
由于排序过程中，交换的次数比冒泡排序少，因此它具有较高的效率。原始序列最终序列用数组来存储一系列同类型的数据, 然后调整数组中的元素

dim d(1 to 4) as integer ‘定义一个数组变量d例：将以下四个数组元素用选择进行排序(从小到大)d(1)=27 d(2)=36 d(3)=32 d(4)=18选择排序算法演示第 1 遍 j=2Min=1
For j=2 to 4
if d(min)>d(j) then min=j
Next j
If min不等于1时，交换d(1)和d(min)第2遍选择j=3Min=2
For j=3 to 4
if d(min)>d(j) then min=j
Next j
If min<>2 then 交换d(2)和d(min) 第3遍选择j=4Min=3
For j=4 to 4
if d(min)>d(j) then min=j
Next j
If min<>3 then 交换d(3)和d(min) 分析第1遍选择 ，j从2开始到4Min=1
For j=2 to 4
if d(min)>d(j) then min=j
Next j
If min<>1，交换d(1)和d(min)Min=2
For j=3 to 4
if d(min)>d(j) then min=j
Next j
If min<>2 then 交换d(2)和d(min)第2遍选择 ，j从3开始到4第3遍选择 ，j从4开始到4Min=3
For j=4 to 4
if d(min)>d(j) then min=j
Next j
If min<>3 then 交换d(3)和d(min)用i来表示次数的变化程序实现For i = 1 To 3（num - 1 ） '选择第i个最小的数
Min = i
For j = i + 1 To 4（num ） '如果找到更小的，用min记住它的编号
If d(Min) > d(j) Then Min = j
Next j
If Min <> i Then '如果最小的数所在的位置不是i，则交换
temp = d(i)
d(i) = d(Min)
d(Min) = temp
End If
Next i数组元素的个数练习：随机产生10个整数，并用选择排序算法排序（从小到大）。Dim a(1 To 10) As Integer
Dim i,j, k,t As Integer
Print "排序前："
Randomize
For i = 1 To 10
a(i) = Int(Rnd * 100)
Print a(i);
Next i
For j = 1To 9
k=j
For i = j+1 To 10
If a(i)Next i
IF j<>k then
t=a(j):a(j)=a(k):a(k)=t
End if
Next j
Print
Print "排序后："
For i = 1 To 10
Print a(i);
Next i第一遍:j=1
k=j即k=1
数组a里面a(1)到a(10)10个元素比较大小，找到最小的元素a(i),让k=i(小循环作用)
退出小循环后，交换a(1)与a(k)的值。
第二遍:j=2
k=j即k=2
数组a里面a(2)到a(10)9个元素比较大小，找到最小的元素a(i),让k=i(小循环作用)
退出小循环后，交换a(2)与a(k)的值。
第三遍:j=3
….
第九遍:j=9
k=j即k=9
数组a里面a(9)到a(10)2个元素比较大小，找到最小的元素a(i),让k=i(小循环作用)
退出小循环后，交换a(9)与a(k)的值。
j=10循环结束。练习：随机产生10个整数，并用选择排序算法排序（从小到大）。Dim a(1 To 10) As Integer
Dim i,j, k,t As Integer
Print "排序前："
Randomize
For i = 1 To 10
a(i) = Int(Rnd * 100)
Print a(i);
Next i
For j = 1To 9
k=j
For i = j+1 To 10
If a(i)Next i
IF j<>k then
t=a(j):a(j)=a(k):a(k)=t
End if
Next j
Print
Print "排序后："
For i = 1 To 10
Print a(i);
Next i
Dim a(1 To 10) As Integer
Dim i,j, t As Integer
Print "排序前："
Randomize
For i = 1 To 10
a(i) = Int(Rnd * 100)
Print a(i);
Next i
For j = 1 To 9
For i = 10 To j+1 Step -1
If a(i) < a(i - 1) Then
t = a(i)
a(i) = a(i - 1)
a(i - 1) = t
End If
Next i
Next j
Print
Print "排序后："
For i = 1 To 10
Print a(i);
Next i选择排序算法冒泡排序算法要区分一个排序是冒泡排序还是选择排序，就
看交换是在双重循环中的哪一个循环中发生。
如果元素交换是在里面的小循环中发生，就是
冒泡排序，是在外面的大循环中发生，就是选
择排序。总结：1、下表中原始数据是一组学生的军训打靶成绩，若采用冒泡排序算法对其进行排序，则第3遍的排序结果是：85889398951．有一组数，依次为3、2、8、5、9，若采用选择排序算法对其进行从大到小排序，则第二趟的排序结果是
（A）9 2 8 5 3 （B）9 5 8 2 3
（C）9 8 2 5 3 （D）9 2 8 3 5