浙教版信息技术选修1 VB教程—排序算法复习课件（共22张ppt）

课件22张PPT。排序问题 1、冒泡法(起泡法)
2、顺序交换法
3、选择法
4、插入法
1、冒泡法首先我们来看把最大的那个数放在最后位置上的方法：
假设有5个数，分别为10，2，6，7，4，存放在a(1)-a(5)中。
首先，从a(1)到a(5)，相邻的两数两两进行比较，在每次比较过程中，若前一个数比后一个数大，则交换两元素的内容。第一轮的比较过程：
for j=1 to 4
if a(j)>a(j+1) Then
t=a(j): a(j)=a(j+1) : a(j+1)=t
End if
Next j1、冒泡法现在重复上述算法：把a(1)到a(4)中的最大数放在a(4)中，a(1)到a(3) 中的最大数放在a(3)中，a(1)与a(2) 中的最大数放在a(2)中。这样一共经过4次选大就把a(1)到a(5)中的数进行由小到大排序。 在排序过程中小数象气泡一样上浮，而大数逐个下沉，所以叫起泡法。第1轮：
for j=1 to 4
if a(j)>a(j+1) Then
t=a(j): a(j)=a(j+1) : a(j+1)=t
End if
Next j
第2轮：
for j=1 to 3
if a(j)>a(j+1) Then
t=a(j): a(j)=a(j+1) : a(j+1)=t
End if
Next j
第3轮：
for j=1 to 2
if a(j)>a(j+1) Then
t=a(j): a(j)=a(j+1) : a(j+1)=t
End if
Next j
第4轮：
for j=1 to 1
if a(j)>a(j+1) Then
t=a(j): a(j)=a(j+1) : a(j+1)=t
End if
Next j第i轮：
for j=1 to 5-i
if a(j)>a(j+1) Then
t=a(j): a(j)=a(j+1): a(j+1)=t
End if
Next jFor i=1 to 4Next i1.冒泡法冒泡法程序清单：
Dim a(1 To 5) As Integer
For i = 1 To 5
a(i) = Val(InputBox("输入一个数"))
Next i
For i=1 to 4
For j=1 To 5-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
For i = 1 To 5
Print a(i);
Next i冒泡排序思考：如果这5个数是2，4，6，7，10，简述程序执行流程。1.冒泡法改进算法:
Dim a(1 To 5) As Integer
For i = 1 To 5
a(i) = Val(InputBox("输入一个数"))
Next i
For i=1 to 4
flag=0
For j=1 To 5-i
if a(j)>a(j+1) Then
t=a(j): a(j)=a(j+1): a(j+1)=t: flag=1
End if
Next j
If flag=0 Then Exit For
Next i
For i = 1 To 5
Print a(i);
Next i1.冒泡法对已知存放在数组中的n个数，用冒泡法按递增顺序排序。
(1) 从第一个元素开始，将相邻的数比较，若为逆序，就交换，比较完一轮，最大的数已沉底，成为数组中的最后一个元素a(n)
(2) 对a(1)和a(n-1)的n-1个数进行同(1)的操作，次大的数放入a(n-1)中，完成第二轮排序。
(3) 进行n-1轮排序，所有的数排序完毕。1.冒泡法n个数冒泡法递增排序程序清单：
Dim a%(), i%, j%, n%
n = InputBox("请输入一个正整数")
ReDim a(1 To n)
For i = 1 To n
a(i) = Int(Rnd * 100) : Print a(i);
Next i
For i = 1 To n - 1
For j = 1 To n - 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
Print
For i = 1 To n
Print a(i);
Next i2、顺序交换法我们再来看一种将最小的数放在第一个位置的算法
先设定用a(1)存放最小值，然后用a(1)分别与其后的每一个数a(j)(j=2..5)进行比较，在比较过程中如果a(1)不是小的数，就将a(1)与a(j)互换。第一轮的比较过程
For j=2 To 5
if(a(1)>a(j)) Then
t=a(1) : a(1)=a(j) : a(j)=t
End if
Next j2、顺序交换法现在重复上述算法：把a(2)到a(5)中的最小数放在a(2)中，a(3)到a(5)中的最小数放在a(3)中，a(4)与a(5)中的最小数放在a(4)中。这样一共经过4次选小就把a(1)到a(5)中的数进行由小到大排序。第1轮：
for j=2 to 5
if a(1)>a(j) Then
t=a(1): a(1)=a(j) : a(j)=t
End if
Next j
第2轮：
for j=3 to 5
if a(2)>a(j) Then
t=a(2): a(2)=a(j) : a(j)=t
End if
Next j
第3轮：
for j=4 to 5
if a(3)>a(j) Then
t=a(3): a(3)=a(j) : a(j)=t
End if
Next j
第4轮：
for j=5 to 5
if a(4)>a(j) Then
t=a(4): a(4)=a(j) : a(j)=t
End if
Next j
第i轮：
for j=i+1 to 5
if a(i)>a(j) Then
t=a(i): a(i)=a(j): a(j)=t
End if
Next jFor i=1 to 4Next i2、顺序交换法 Dim a(1 To 5) As Integer
For i = 1 To 5
a(i) = Val(InputBox("输入一个数"))
Next i
For i = 1 To 4
For j = i+1 To 5
If a(i) > a(j) Then
t = a(i): a(i) = a(j): a(j) = t
End if
Next j
Next i
For i = 1 To 5
Print a(i);
Next i顺序排序2、顺序交换法对已知存放在数组中的n个数，用顺序交换法按递增顺序排序。
(1) 从第一个元素开始，将它和其后的每个元素进行比较，若为逆序，就交换，比较完一轮，a(1)成为数组中的最小的元素。
(2) 对a(2)和a(n)的n-1个数进行同(1)的操作，次小的数放入a(2)中，完成第二轮排序。
(3) 进行n-1轮排序，所有的数排序完毕。2、顺序交换法n个数顺序法递增排序程序清单：
Dim a%(), i%, j%, n%
n = InputBox("请输入一个正整数")
ReDim a(1 To n)
For i = 1 To n
a(i) = Int(Rnd * 100): Print a(i);
Next i
For i = 1 To n - 1
For j = i + 1 To n
If a(i) > a(j) Then
t = a(i): a(i) = a(j): a(j) = t
End If
Next j
Next i
Print
For i = 1 To n
Print a(i);
Next i
3、选择法算法：不急于交换，先找出a(1)到a(5)中最小数所在的位置K，一遍扫描完之后，再把a(1)与a(K)互换。
重复此算法，只是每次重复进行比较的数列范围向后移一个位置。即第二遍从a(2)到a(5)中去找最小数的位置，最后把a(2)与a(K)对调，第三遍从a(3)到a(5)中去找最小数的位置，最后把a(3)与a(K)对调，…此过程重复4次后，即将a数组中的5个数按由小到大的顺序排好。这种排序方法叫选择法。第1轮：
k=1
for j=2 to 5
if a(j)Next j
if k<>1 then t=a(1):a(1)=a(k):a(k)=t
第2轮：
k=2
for j=3 to 5
if a(j)Next j
if k<>2 then t=a(2):a(2)=a(k):a(k)=t
第3轮：
k=3
for j=4 to 5
if a(j)Next j
if k<>3 then t=a(3):a(3)=a(k):a(k)=t
第4轮：
k=4
for j=5 to 5
if a(j)Next j
if k<>4 then t=a(4):a(4)=a(k):a(k)=t第i轮：
k=i
for j=i+1 to 5
if a(j)Next j
if k<>i then t=a(i):a(i)=a(k):a(k)=tFor i=1 to 4Next i3、选择法选择排序法程序清单：
Dim a(1 To 5) As Integer
For i = 1 To 5
a(i) = Val(InputBox("输入一个数"))
Next i
For i=1 to 4
k=i
For j=i+1 To 5
if a(j) Next j
if k<>i Then t=a(i): a(i)=a(k): a(k)=t
Next i
For i = 1 To 5
Print a(i);
Next i排序过程3、选择法对已知存放在数组中的n个数，用选择法按递增顺序排序。
(1) 从n个数的序列中选出最小的数，与第1个数交换位置；
(2) 除第1个数外，其余n-1个数再按(1)的方法选出次小的数，与第2个数交换位置；
(3) 重复(1)n-1遍，最后构成递增序列。3、选择法n个数选择法递增排序程序清单：
Dim a%(), i%, j%, n%
n = InputBox("请输入一个正整数")
ReDim a(1 To n)
For i = 1 To n
a(i) = Int(Rnd * 100): Print a(i);
Next i
For i = 1 To n – 1
k=i
For j = i + 1 To n
If a(j) < a(k) Then k=j
Next j
if k<>i then t=a(i): a(i)=a(k): a(k)=t
Next i
Print
For i = 1 To n
Print a(i);
Next i
4 插入法a数组key=20例7 将一个数插入到有序的（由小到大）数列中，插入后数列仍然有序。20算法：
1. 找到插入数在数组中的位置i
2. 将从n到i的每个元素向后移动一个位置
3. 插入数4 插入法将一个数插入到有序数列，使插入后数列仍然有序的程序清单:
Dim a(1 To 10) As Integer
For i = 1 To 9
a(i) = (i-1)*3+1
Next i
Key = Val(InputBox("输入一个数"))
For i=1 to 9
If a(i)>Key Then Exit For
next i
For k = 9 To i Step -1
a(k + 1) = a(k)
Next k
a(i) = Key
For i = 1 To 10
Print a(i);
Next i4 插入法插入法2： 用上面的插入方法将一批数排序（从小到大），设数列中开始只有一个元素。Dim x(1 To 10) As Integer
For i = 1 To 10
x(i) = Val(InputBox("输入一个数"))
Next i
For i = 1 To 9
Key = x(i + 1)
j = 1
Do While (Key >= x(j) And j <= i)
j = j + 1
Loop
For k = i To j Step -1
x(k + 1) = x(k)
Next k
x(j) = Key
Next i
For i = 1 To 10
Print x(i);
Next iFor j=1 to i
If x(j)>Key Then Exit For
Next j