第7节 其他排序算法
模拟演练
1.有如下程序段:
i = 1
Do While i <= 5
If i = 0 or a(i -1) <= a(i) Then
i = i + 1
Else
t = a(i): a(i) = a(i -1): a(i -1) = t
i = i - 1
End If
Loop
数组元素a(0)到a(5)的值依次为“0,71,22,48,79,27”,经过该程序段“加工”后,数组元素a(4)的值为( )
A.0 B.71 C.48 D.27
答案 B 本题要理解程序的整体功能,数据从前往后比,如果连续的两个数据升序,i加1,继续比较紧邻的后面两数,如果不是升序状态,先交换两数,然后i减1,退回前面,重新比较原来的两个数,直到所有数据升序。
2.有如下VB程序段:
For i = 1 To n - 1
t = n - (n + i) Mod 2
For j = t To i + 2 Step -2
If d(j) > d(j - 2) Then t = d(j):d(j) = d(j - 2):d(j - 2)= t
Next j
Next i
已知n = 10,数组元素d(1)到d(10)的原始数据为1、2、3、4、5、6、7、8、9、10,程序运行后,d(10)的值为( )
A.9 B.1 C.2 D.10
答案 C 本题是隔位冒泡排序。每一次外循环,变量t的值9和10交替出现。当i=1时,对d(9)、d(7)、……、d(3)、d(1)进行一趟冒泡(降序),当i=2时,对d(10)、d(8)、……、d(4)、d(2)进行一趟冒泡(降序),最终实现d(9)、d(7)、……、d(3)、d(1)降序排序,d(10)、d(8)、……、d(4)、d(2)降序排序。显然偶数位上的最小值d(10)=2。
3.有以下VB程序段:
a(1)=6:a(2)=8:a(3)=7:a(4)=3:a(5)=1:a(6)=2:a(7)=5:a(8)=4
i = 1: j = 8
key = a(1)
Do While i < j
Do While i < j And a(j) >= key
j = j - 1
Loop
a(i) = a(j)
Do While i < j And a(i) <= key
i = i + 1
Loop
a(j) = a(i)
Loop
a(i) = key
For i = 1 To 8
Label1.Caption=Label1.Caption++Str(a(i))
Next i
执行该程序段,标签Label1上显示的内容是( )
A.12345678 B.876 C.45231678 D.451
答案 C 本题考查经典快速排序算法思想,当然只是快速排序的第一趟。以元素6为基点,将大于6的元素移到右边,小于6的元素移到左边。关于本题的解题方法,最直接的是将数据代入运算,得出答案。
4.小明最近学习了一种插入排序的算法。算法的基本思想如下:每次将一个待排序的记录,按其关键字大小插入前面已经排好序的记录集中,使记录依然有序,直到所有待排序记录全部插入完成。
如数据25 54 8 54 21 排序过程如下(n=5):
待排序数据:【25】 54 8 54 21
i=2:【25 54】 8 54 21
i=3:【8 25 54】 54 21
i=4:【8 25 54 54】 21
i=5:【8 21 25 54 54】
程序产生10个-100~100之间的整数,从小到大排序后输出,运行结果如图所示:
/
实现上述功能的VB程序代码如下,但加框处代码有错,请改正。
Dim a(0 To 10) As Integer
Private Sub Command1_Click()’产生10个随机数放在数组a中
Dim i As Integer
For i = 1 To 10
a(i) = Int(Rnd * 101)’①
List1.AddItem Str(a(i))
Next i
End Sub
Private Sub Command2_Click()
Dim i As Integer, j As Integer
For i = 2 To 10
a(0) = a(i)
j = i - 1
Do While a(0) < a(j)
a(j) = a(j+1)’②
j = j - 1
Loop
a(j + 1) = a(0)
Next i
For i = 1 To 10
List2.AddItem Str(a(i))
Next i
End Sub
①处的代码修改为 。?
②处的代码修改为 。?
答案 ①a(i) = Int(Rnd * 201) - 100
②a(j + 1) = a(j)
解析 ①考查随机函数的应用。Rnd的范围是[0,1),Int(Rnd * 201)的范围是0~200,因此表达式的范围是-100~100。②当前第a(i)个数暂存在a(0)中,从第i-1依次往前找,比a(0)大的元素都往后移动一位。
5.某公司面试程序题如下:公司有10000名员工,请设计一个算法对该公司员工的年龄做递增排序输出。小刘设计了一个算法:利用数组b记录每个数据出现的次数,数组b下标范围为年龄范围,然后根据每个年龄值的个数进行排序。
例如,有如下年龄存在数组a中:
a(1)
a(2)
a(3)
a(4)
a(5)
a(6)
a(7)
a(8)
a(9)
a(10)
20
19
18
19
15
12
15
20
17
19
利用一个数组b(b(10 To 20))记录每个数出现的次数:
b(10)
b(11)
b(12)
b(13)
b(14)
b(15)
b(16)
b(17)
b(18)
b(19)
b(20)
0
0
1
0
0
2
0
1
1
3
2
根据数组b对数组a进行排序:
a(1)
a(2)
a(3)
a(4)
a(5)
a(6)
a(7)
a(8)
a(9)
a(10)
12
15
15
17
18
19
19
19
20
20
Dim a(10000) As Integer ’存放读入的年龄数据
Dim b(100) As Integer ’存放各个年龄出现的个数
Private Sub Command1_Click()
’从数据库读入年龄数据放入数组a中
End Sub
Private Sub Command2_Click()
For i = 1 To 100
b(i) = 0
Next i
For i = 1 To 10000 ’统计每个年龄数据的个数
① ?
Next i
End Sub
Private Sub Command3_Click()
j = 0
For i = 1 To 100
If b(i) <> 0 Then
Do While b(i) <> 0
② ?
a(j) = i
b(i) = b(i-1)’③
Loop
End If
Next i
For i = 1 To 10000
List2.AddItem Str(a(i))
Next i
End Sub
/
(1)为实现程序功能,请在划线①②处填入合适的代码。
①处填入的代码为 。?
②处填入的代码为 。?
(2)加框处③代码有错,请修正。
③处的代码修改为 。?
答案 (1)b(a(i)) = b(a(i)) + 1;j = j + 1
(2)b(i) = b(i) - 1
解析 (1)①根据题意,数组b存放每个年龄的个数,例如a中某个元素28,相应b(28)加1。
②当前程序段表示,在数组a中从第一位开始存放重新排序后的年龄i,当前年龄的个数存放在b(i)中,将数组b中非0元素展开,一直到b(i)=0。
(2)表示当前年龄为i的数据减少一个,直到b(i)=0。
6.编写一个VB程序,实现程序功能如下:随机产生10个1~20之间的整数存放在数组a,在列表框List1中显示,单击“排序”按钮Command1后,在列表框List2中显示升序排序后的结果,运行界面如图所示。具体算法描述如下:引入数组index,index(i)存储i位置应放置的数组元素的下标。排序完毕,a(index(i))成为升序序列,即a(index(1))≤a(index(2))≤a(index(3))≤……≤a(index(i))。在数组a的所有元素中找出最小元素,将其所在位罝存放在数组元素index(1)中,然后在余下的元素中找出最小元素,将其所在位置存放在数组元素index(2)中,以此类推,直到完成所有元素排序。如n=5时,数组a排序后各变量值如下表所示。
i
1
2
3
4
5
a(i)
17
19
9
13
6
index(i)
5
3
4
1
2
a(index(i))
6
9
13
17
19
实现上述功能的VB程序如下,但加框处代码有错,请改正。
Const n = 10
Const maxn = 20
Dim a(1 To n) As Integer, index(1 To n) As Integer, flag(1 To n) As Boolean
Private Sub Form_Load()
Dim i As Integer
Randomize
For i = 1 To n
flag(i) = False
a(i) = Int(Rnd() * maxn) + 1
List1.AddItem Str(a(i))
Next i
End Sub
Private Sub Command1_Click()
Dim i As Integer, j As Integer
Dim k As Integer
For i = 1 To n
For j = 1 To n
If flag(j) = False Then k = j: Exit For
Next j
For m = k + 1 To n
Ifflag(m) = False Or a(m) > a(k) Then k = m’(1)
Next m
index(i) = k
flag(k) = True
Next i
For i = 1 To n
List2.AddItemStr (a(i))’(2)
Next i
End sub
答案 (1)flag(m) = False And a(m) < a(k)
(2)Str(a(index(i)))
解析 本题的关键是理解数组index的用途,它存储的是数组a的值所在的位置。用数组flag标记数组a中对应位置的值是否已经确定排序号。(1)第一个要修改的地方应该是要确定数组a中还没确定排名的位置里的最小值的位置,用k来记住,所以把最小值所在的位置逐个存入数组index,最终数组index里就有数组a的位置排序。因此答案是flag(m)=False And a(m)
课件6张PPT。
第7节 其他排序算法1.插入排序(Insertion Sort)
思想方法:
(1)从第一个元素开始,该元素可以认为已经被排序;
(2)取出下一个元素,在已经排序的元素序列中从后向前扫描;
(3)如果该元素(已排序)大于新元素,将该元素移到下一位置; (4)重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;教材研读(5)将新元素插入到该位置后;
重复步骤(2)~(5)。
核心代码(升序):为a(i)找到插入位置,后继元素依次往后移一个位置
For i = 2 To n(a(1)不用排)
key = a(i)(a(i)需保留一下,否则一会儿值会被替换)
j=i-1
Do While j >= 1 And key j=j-1 Loop
a(j+1) =key
Next2.计数排序(Counting Sort)
思想方法:
找出待排序的数组a中最大和最小的元素;
统计数组中每个值为i的元素出现的次数,存入数组c的第i项;
输出原数组:根据c(i)中的值,输出原数组a的值,每放一个元素就将c(i)减 去1。核心代码:统计同样值的个数,存在数组c中,最后从小到大重新存回数组 a中。For i = 1 To n
c(a(i)) = c(a(i)) + 1
Next
i = 1
For j = Min To Max
Do While c(j) > 0
a(i) = j i = i + 1 c(j) = c(j) - 1
Loop
Next