桶排序和索引排序算法导学案

vlambda
2020-04-01

桶排序和索引排序算法导学案

本文为“选考V B算法专题系列讲座10桶排序和索引排序算法”视频配套的导学案，请同学们先完成导学案再收看视频。

明天将推送“选考VB算法专题系列讲座 10桶排序和索引排序算法”视频，敬请期待！

桶排序和索引排序算法导学案

一

题目

1. 有如下程序段：

Const s = "3123abc21d64"Dim flag(0 To 9) As BooleanDim i As Integer, c As String, n As IntegerFor i = 0 To 9 flag(i) = FalseNext iFor i = 1 To Len(s) c = Mid(s, i, 1) If c >= "0" And c <= "9" Then flag(Val(c)) = TrueNext in = 0For i = 0 To 9 If flag(i) Then n = n + 1Next i

程序执行后n的值是（）

A 3 B 5 C 8 D 12

2. 有如下程序段：

Const s = "3123abc21d64"Dim flag(0 To 9) As IntegerDim i As Integer, c As String, n As IntegerFor i = 0 To 9 flag(i) = 0Next iFor i = 1 To Len(s) c = Mid(s, i, 1) If c >= "0" And c <= "9" Then flag(Val(c)) = flag(Val(c)) + 1Next in = 0For i = 0 To 9 n = n + flag(i)Next i

程序执行后n的值是（）

A 3 B 5 C 8 D 12

3. 有如下程序段：

Const s = "1234564321"Dim b(0 To 255) As IntegerDim i As Integer, c As String, n As IntegerFor i = 0 To 255 b(i) = 0Next iFor i = 1 To Len(s) c = Mid(s, i, 1) b(Asc(c)) = b(Asc(c)) + 1Next iFor i = 1 To Len(s) c = Mid(s, i, 1) If b(Asc(c)) = 1 Then Exit ForNext iText1.Text = c

程序执行后文本框Text1显示的内容为（）

A 1 B 4 C 5 D 6

4. 小王想对浙江省30万考生的技术成绩进行降序排序，成绩为0到100之间的整数。由于人数较多，使用选择，冒泡，插入等简单排序算法效率实在太低，是否有更高效的方法？

因为待排序的成绩为0到100之间的整数，所以可以使用桶排序。

桶排序算法分为三个步骤：把桶清空，把数据装入对应桶中和依次把数据从桶里倒出来。

假设我们把成绩存储在数组a中。可以设置一个长度为101的数组b，表示总共有101个桶，它的下标0-100就是各个桶的编号。

第一步：把桶清空，即初始化数组b 的值均为0 。

第二步：把数据装入对应桶中，即累计数组b各元素的值。例如，若出现a(i) = 80，则b(80) =b(80) + 1；若最终考80分的学生有10000名，则b(80) = 10000。

第三步：依次把数据从桶里倒出来，即逆序遍历数组b，从高到低依次输出成绩。若b(i)= k，则表示成绩为i的学生总共有k个，需要将成绩i输出k次。

假设已经把n名学生的成绩存储到数组a中，下面的代码能实现上述要求，请把缺失的代码补充完整。

Private Sub Command1_Click() Dim b(0 To 100) As Integer Dim c As Integer For i = 0 To 100 '把桶清空 b(i) = ① Next i For i = 1 To n '将数据装入桶中 b(a(i)) = ② Next i c = 0 For i = 0 To 100 '从桶中取出数据 For j = 1 To b(i) c = c + 1: a(c) =③ Next j Next iEnd Sub

5. 小王用计算机生成了n个10到99之间随机整数，要求这些数据进行“去重”和“升序排序”的工作，并输出处理后的数据。假设已经把n名学生的成绩存储到数组a中，下面的代码能实现上述要求，请把缺失的代码补充完整。

Private Sub Command4_Click() Dim b(10 To 99) As IntegerDim c As Integer, i As IntegerDim s As String For i = 10 To 99 '把桶清空 b(i) = ① Next i For i = 1 To n '将数据装入桶中 b(a(i)) = ② Next i c = 0 For i = 10 To 99 '从桶中取出数据 If b(i) > 0 Then c = c + 1 a(c) = ③ End If Next i s = "" For ④ s = s + Str(a(i)) Next i Text2.Text = sEnd Sub

6. 如下图所示，List1显示了排序前学生的姓名和成绩，点击按钮1或按钮2都能按照成绩从高到低将学生的姓名和成绩显示到List2中。按钮1和按钮2分别采用了不同的方法来实现了排序功能，其中Command1_Click()使用选择排序算法对数组score和pname都进行了排序，再输出排序后的姓名和成绩；但是Command2_Click()并没有对数组score和pname进行排序，而是引入了一个辅助数组q，数组q按顺序存储了各学生的序号，q(i)=k表示排名第i的人其序号为k。我们根据学生的成绩对数组q进行排序，并依次输出pname(q(i)) 和score(q(i))，这样就实现了按顺序输出学生姓名和成绩的功能。桶排序和索引排序算法导学案

下面的代码实现了上述功能，请将缺失的代码补充完整：

Const n = 6Dim score(1 To n) As Integer '存储学生的成绩Dim pname(1 To n) As String '存储学生的姓名Dim i As Integer, j As Integer, k As Integer
Private Sub Command1_Click() Dim tscore As Integer, tname As String For i = 1 To n - 1 k = i For j = i + 1 To n If ① Then k = j Next j If k <> i Then tscore = score(i): score(i) = score(k): score(k) = tscore tname = pname(i): pname(i) = pname(k): pname(k) = tname End If Next i For i = 1 To n List2.AddItem pname(i) + Str(score(i)) NextEnd Sub
Private Sub Command2_Click() Dim q(1 To n) As Integer, tpos As Integer 'q(i)=k表示排名第i的人其序号为k For i = 1 To n q(i) = i '初始化排名为i的人序号也是i Next '根据分数大小对学生的序号进行排序，并依次存储到数组q中 For i = 1 To n - 1 k = i For j = i + 1 To n If ② Then k = j Next j '目前排名为k的学生分数最高，将其序号与排名为i的学生交换，确保第i名学生的分数最高 If k <> i Then tpos = q(i): q(i) = q(k): q(k) = tpos End If Next i For i = 1 To n '按照排名输出学生的姓名和分数 List2.AddItem pname(q(i)) + Str(score(q(i))) NextEnd Sub
Private Sub Form_Load() score(1) = 86: score(2) = 96: score(3) = 88: score(4) = 76: score(5) = 86: score(6) = 82 pname(1) = "小美": pname(2) = "阿福": pname(3) = "小明": pname(4) = "李刚": pname(5) = "华哥": pname(6) = "小武" For i = 1 To n List1.AddItem pname(i) + Str(score(i)) NextEnd Sub

二

答案

1．【答案】B

2．【答案】C

3．【答案】C

4. 【答案】① 0 ② b(a(i)) + 1 ③ i

5. 【答案】① 0 ② b(a(i)) + 1 ③ i ④ i = 1 To c

6. 【答案】① score(j) > score(k) ② score(q(j)) > score(q(k))

需要本文word版的，可以加入“选考VB算法解析”知识星球参与讨论和下载文件，“选考VB算法解析”知识星球汇集了数量众多的同好，更多有趣的话题在这里讨论，更多有用的资料在这里分享。

我们专注选考VB算法，感兴趣就一起来！

vlambda博客
学习文章列表