5.3 排序算法的程序实现 课件（28张幻灯片）

课件28张PPT。插 入 排 序5.3 排序算法的程序实现浙教版《算法与程序设计》第五章01part回 顾 旧 知排 序例：若将下列人物按其身高a(1 to 6)从低到高排123456 回 顾连 连 看例：若将下列人物按其身高a(1 to 6)从低到高排冒泡排序选择排序For i=1 to 5
k=i
For j=i+1 to 6
If a(j) Next j
If i<>k then
t=a(j):a(j)=a(k):a(k)=t
End if
Next iFor i=1 to 5
For j=6 to i+1 step -1
If a(j) t=a(j)
a(j)=a(j-1)
a(j-1)=t
End if
Next j
Next iFor i=1 to 5
For j=i+1 to 6
If a(j) t=a(j)
a(j)=a(i)
a(i)=t
End if
Next j
Next i02part认识插入排序 概 念插入排序 一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法。排 序例：若将下列人物按其身高a(1 to 6)从低到高排123456 回 顾排 序例：若将下列人物按其身高a(1 to 6)从低到高排123456 回 顾1234561、第2位的小明比吕玲矮（比较）
2、小明要放到一号位
但是1位被吕玲占了。
3、解决方法
（1）待插入的小明先放到空位0
（2）将吕玲后移
（3）将小明放到空出来的位置1234561、待插入的芳芳先放到空位0
2、比较
（1）0位内的芳芳比2位吕玲矮
（2）将吕玲从2位后移到3位
（3）0位内的芳芳比1位小明矮
（2）将小明从1位后移到2位
3、前面没有比较的对象了，将芳 芳放到空出来的位置10位拿来放置待排序的数据1、待插入的小琴先放到空位0
2、比较
（1）0位内的小琴比3位吕玲矮
（2）将吕玲从3位后移到4位
（3）0位内的小琴不比2位小明
矮（相等，小明不需要后移）
4、将芳芳放到小明后面1位1234561、待插入的放到空位0
2、拿0位与前面的比较（前面为有序）
比较：若比前面矮，则前面后移；
若他比前面高，则放在比较数据后面1位
123456123456方法:
1、将待插入对象放到预留位置
2、拿预留位内的对象与前面的对象比较
3、比较结果符合条件，则前面对象后移
4、找位置：前面不比他高，前面没人
将对象放到前面这个位置的后1位插 入 排 序 小 结03part 代码编写插入排序对下列数据进行排升序54 25 8 54 21 （n=5）a(1) a(2) a(3) a(4) a(5)a(0)1、待插入的放到空位0
2、拿0位与前面的比较（前面为有序）
比较：若前面比0位大，则前面后移；
若前面比0位小，否则放在比较数据后面1位
代码编写插入排序（基本代码 For）For i = 2 to n
a(0)=a(i)
for j=i-1 to 1 step -1
if a(j)>a(0) then
a(j+1)=a(j)
else
exit for
end if
next j
a(j+1)=a(0)
Next i
插入排序（基本代码Do）For i = 2 to n
a(0)=a(i)
d
Do while a(j)>a(0)
a(j+1)=a(j)
j=j-1
Loop
a(j+1)=a(0)
Next i
04part练习巩固例117.[加试题]有一种排序方法叫插入排序，它的基本思想是将一个数据插入到已经排好的有序数列中，从而得到一个新的、个数加1的有序数列。
小王编写了一个VB程序实现插入功能，功能如下：运行程序时，在列表框List1中显示排序前数据，单击“排序按钮”Command1，在列表框List2中显示这些数据按升序排序后的结果，程序运行效果如图例1Dim t As Integer, i As Integer
Dim a(1 To 10) As Integer
Private Sub Form_Load()
For i = 1 To 10
a(i) = Int(Rnd * 90) + 10
List1.additem str(a(i))
Next i
End Sub
Private Sub Command1_Click()
For i = To 10
If a(i) < a(i - 1) Then
t = a(i)
For j = i - 1 To 1 Step -1
If t > a(j) Then Exit For
a
Next j
= t
End If
Next I
For i = 1 To 10
List2.AddItem Str(a(i))
Next i
End Sub
例1Dim t As Integer, i As Integer
Dim a(1 To 10) As Integer
Private Sub Form_Load()
For i = 1 To 10
a(i) = Int(Rnd * 90) + 10
List1.additem str(a(i))
Next i
End Sub
例1Private Sub Command1_Click()
For i = To 10
If a(i) < a(i - 1) Then
t = a(i)
For j = i - 1 To 1 Step -1
If t > a(j) Then Exit For
u
Next j
= t
End If
Next I
For i = 1 To 10
List2.AddItem Str(a(i))
Next i
End Sub
例217【加试题】某活动给900个观众用三位数进行编号，编写VB程序随机产生10个编号，要求：
（1）产生的号码不重复；
（2）产生的号码按升序排列，例如：产生4个编号：120,188,211,278.当下一个生成的编号：150，则将编号自动排列为：120,150,188,211,278。程序运行界面如图所示：例2Dim a(10) As Integer
Private Sub Command1_Click()
Dim i As Integer, j As Integer
Dim temp As Integer, k As Integer
Randomize
a(1) = Int(Rnd * 900 + 100)
For i = 2 To 10
temp = Int(Rnd * 900 + 100)
If search(temp, i - 1)=true Then
i = i - 1
Else
k = i
For j = 1 To i - 1
If temp < a(j) Then k = j: Exit For
Next j
For j = i - 1 To k Step -1
a(j + 1) = a(j)
Next j
a(k) = temp
End If
Next i
List1.Clear
For i = 1 To 10
List1.AddItem Str(a(i))
Next i
End Sub
Function search(pp As Integer, t As Integer) As Boolean
Dim i As Integer
search = False
For i = 1 To t
If Then search = True: Exit For
Next i
End Function例2 Dim a(10) As Integer
Private Sub Command1_Click()
Dim I As Integer, j As Integer
Dim temp As Integer, k As Integer
Randomize
a(1) = Int(Rnd * 900 + 100)
For i = 2 To 10
temp = Int(Rnd * 900 + 100)
If search(temp, i - 1)=true Then
i = i - 1
例2Else
k = i
For j = 1 To i - 1
If temp < a(j) Then k = j: Exit For
Next j
For j = i - 1 To k Step -1
a(j + 1) = a(j)
Next j
;
End If
Next i
List1.Clear
For i = 1 To 10
List1.AddItem Str(a(i))
Next i
End Sub
例2
Function search(pp As Integer, t As Integer) As Boolean
Dim i As Integer
search = False
For i = 1 To t
If Then search = True: Exit For
Next i
End Function