资源简介 第3节 选择排序及程序实现考试内容考试要求选择排序算法思想c选择排序程序实现c一、选择排序算法思想每趟排序是在所有的数据中找出最大(或最小)的数据,与第一个数据交换位置,然后再在剩下的数据中找出最大(或最小)的数据,与第二个数据交换位置,以此类推,直到所有元素成为一个有序序列为止。n个数据排序共需进行n-1趟(遍)排序。二、选择排序算法框架设定:对数组d中的n个数据进行升序排序。(1)从前往后进行比较For i = 1 To n - 1 ′n个排序共进行n-1趟排序 假定i位置上的数为最小数 For j = i + 1 To n ′i后面的位置 ′若找到更小的数,则将用k记录此数的位置 Next j If k < > i Then ′若i位置上的数不是最小数,则和k位置上的数进行互换交换d(i)与d(k) End IfNext i注:若要按降序排列,将程序中的语句“If d(k)>d(j)”改为“If d(k)(2)从后往前进行比较For i = 1 To n - 1 ′n个排序共进行n-1趟排序 假定i位置上的数为最小数 For j = n To i + 1 Step -1 ′i后面的位置 ′若找到更小的数,则将用k记录此数的位置 Next j If k < > i Then ′若i位置上的数不是最小数,则和k位置上的数进行互换 交换d(i)与d(k) End IfNext i注:若要按降序排列,将程序中的语句“If d(k)>d(j)”改为“If d(k)三、选择排序程序实现设定:对数组d中的n个数据进行升序排序。(1)从前往后进行比较For i = 1 To n - 1 ′n个排序共进行n-1趟排序 k = i ′假定i位置上的数为最小数 For j = i + 1 To n ′i后面的位置 If d(k) > d(j) Then k = j ′若找到更小的数,则将用k记录此数的位置 Next j If k < > i Then ′若i位置上的数不是最小数,则和k位置上的数进行互换temp=d(k):d(k)=d(i):d(i)=temp End IfNext i(2)从后往前进行比较For i = 1 To n - 1 ′n个排序共进行n-1趟排序 k = i ′假定i位置上的数为最小数 For j = n To i + 1 Step -1 ′i后面的位置If d(k) > d(j) Then k = j ′若找到更小的数,则将用k记录此数的位置 Next j If k < > i Then ′若i位置上的数不是最小数,则和k位置上的数进行互换temp=d(k):d(k)=d(i):d(i)=temp End IfNext i一、选择排序算法思想理解选择排序的基本思想,学会将待排数据按照选择算法思想进行手工模拟排序。【典例1】 使用选择排序对下表中9个数据进行排序,排序过程如下所示:初始数据1005080706035908525第1遍1005080706035908525第2遍1009080706035508525第3遍则第三遍的排序结果为( )A.100,90,85,80,70,60,35,50,25B.100,90,85,70,60,35,50,80,25C.100,90,85,80,70,60,50,35,25D.100,90,85,60,70,35,50,80,25解析 本题主要考查选择排序算法的基本思想。观察第1、2遍的排序结果可知,该选择排序为降序排序,第3遍排序时,数据85与80进行交换,因此第三遍排序后的结果为“100,90,85,70,60,35,50,80,25”,答案为B。答案 B【变式训练】 采用选择排序算法对数组d中的8个数据“20,8,6,4,15,3,19,50”进行排序,部分程序如下:For i=1 To 5k = iFor j=i+1 To 8If d(j)If i< >k Thentt=d(k):d(k)=d(i):d(i)=ttEnd If Next jNext i该程序段执行后,数组元素d(1)~d(8)依次为( )A.3,4,6,8,15,19,20,50B.3,4,6,8,15,50,20,19C.3,4,6,8,15,20,19,50D.3,4,6,8,15,20,50,19解析 本题主要考查的是选择排序。根据语句“If d(j)初始数据208641531950第1遍386415201950第2遍346815201950第3遍346815201950第4遍346815201950第5遍346815201950因此答案为C。答案 C【方法总结】 选择排序时,首先用变量记录最大或最小元素的位置,然后与相应位置上的元素进行交换;通过If语句中表达式确定排序的升降性。二、选择排序算法实例应用【典例2】 有如下VB程序段:For n = 1 To 4 p = n For m = n + 1 To 5If a(m) < a(p) Then p = m Next m If p > n Then temp = a(n) a(n) = a(p) a(p) = temp End IfNext n设数组元素a(1)~a(5)的值分别为“1000,1200,1018,1208,1019”,经过该程序段“加工”后,数组元素a(1)+a(3)的值为( )A.2018 B.2019 C.2200 D.2208解析 本题主要考查的是选择排序算法。排序方式为升序,排序后数组元素a(1)~a(5)的值分别为“1000,1018,1019,1200,1208”,因此a(1)+a(3)=1000+1019=2019。答案 B【变式训练】 小赵对选择排序算法进行了如下改进:在数组的所有元素中找出最小和最大数据的元素,然后将这两个元素分别与第一个和最后一个元素交换数据,在余下的元素中找出最小和最大数据的元素,分别与第二个和倒数第二个元素交换数据,以此类推,直到所有元素的数据按升序排列。小赵编写的VB程序段如下:p = 1: q = 10Do While p < q iMin = p: iMax = p For i = p + 1 To qIf a(i) < a(iMin) Then iMin = iIf a(i) > a(iMax) Then iMax = i Next i t = a(iMin): a(iMin) = a(p): a(p) = t ____①____ t = a(iMax): a(iMax) = a(q): a(q) = t p = p + 1 q = q - 1Loop要使程序实现上述算法思想,则程序中划线处的语句是( )A.If iMax = p Then iMax = iMin B.If iMin = p Then iMin = iMaxC.If iMax = p Then iMin = iMaxD.If iMin = p Then iMax = iMin解析 本题考查的是选择排序算法的变式。选择排序的原本思想是找出一个最大(或最小)的元素将它与第一个元素进行互换,本题的选择排序算法思想是:首先找出当前数据中的一个最小元素和一个最大元素,然后将最小元素与队首元素交换,将最大元素与队尾元素进行互换。当最大元素在p位置时,由于它与最小元素进行互换后,原来的存放位置发生了变化,即由p的位置更改为iMin的位置了,因此要将它的新位置记录在iMax中,然后再与q位置上的元素进行互换。因此,答案为A。答案 A【方法总结】 在掌握选择排序常规算法的基础上,还要对选择排序的各种变式进行研究,做到举一反三,触类旁通。1.对数组元素a(1)~a(8)进行从小到大排序,其选择排序算法的VB程序段如下:For m=1 To 7 p=m For n=m+1 To 8 ________ Next n IF p< >m then t=a(p):a(p)=a(m):a(m)=tNext m划线处的语句是( )A.If a(n)B.If a(n)C.If a(n)>a(p) Then p=nD.If a(n)>a(p) Then p=m解析 本题主要考查的是选择排序的程序实现。要降序排序,因此划线处的语句为If a(n)答案 B2.实现某排序算法的部分VB程序如下:For i = 1 To 7 k = i For j = i + 1 To 8 If a(j) < a(k) Then k = j Next j If i < > k Then t = a(i): a(i) = a(k): a(k) = t End IfNext i在排序过程中,经过某一遍排序“加工”后,数组元素a(1)到a(8)的数据依次为“1,2,15,8,16,7,6,5”。则下一遍排序“加工”后数组元素a(1)到a(7)的数据依次是( )A.1,2,5,6,7,8,15,16B.1,2,5,15,16,7,6,8C.1,2,5,8,16,6,7,15D.1,2,5,8,16,7,6,15解析 本题主要考查的是选择排序(升序)的实现过程。根据程序代码或给出的数据序列可知,是升序排序,前2个数已经有序,因此下一遍的排序是剩下的6个元素中选出一个最小数与第三个位置上的元素进行交换,即15与5交换。第i遍1215816765第i+1遍1258167615具体排序如表。答案 D3.十佳歌手评选。某校举行学生歌唱比赛,得分最高的前十名选手为校园十佳歌手。下面的Visual Basic程序用于解决这一问题,数组a中存储了参赛学生的编号,数组b中存储了参赛学生的得分,原始信息显示在列表框List1中,单击“计算”按钮后,“得分”最高的10名学生的信息显示在列表框List2中,程序运行界面如图所示。程序代码如下:Const n = 80Dim a(1 To n) As String, b(1 To n) As SinglePrivate Sub Command1_Click() Dim i As Integer, j As Integer, m As Integer Dim s As String, t As SingleFor i = 1 To n - 1m = iFor j = i + 1 To n If ____①____ Then m = jNext jIf____②____ Then s = a(i): a(i) = a(m): a(m) = s t = b(i): b(i) = b(m): b(m) = tEnd IfNext iFor i = 1 To 10 List2.AddItem a(i) + “ ” + Str(b(i)) Next iEnd SubPrivate Sub Form_Load() ′此过程用于对数组a和数组b进行赋值,并显示在List1中,代码略End Sub(1)程序中加框部分的算法是________________(选填:选择排序/冒泡排序)。(2)在程序①和②划线处,填入适当的语句或表达式,把程序补充完整。解析 本题主要考查的是选择排序算法。十佳歌手的评选是按照选手的得分降序排序,取前十名得到的,数组b存储的是选手的得分,因此①处的语句为b(m)m。答案 (1)选择排序 (2)①b(m) < b(j) ②i < > m基础巩固1.有如下程序段:For i = 1 To 2For j = i + 1 To 5 If a(j) > a(i) Then t = a(j): a(j) = a(i): a(i) = tNext jNext i数组元素a(1)~a(5)的值依次为“3,11,19,17,7”,经过该程序段“加工”后,数组元素a(1)到a(5)的值依次为( )A.3,7,11,17,19 B.19,17,11,7,3C.19,17,3,11,7 D.19,17,3,7,11解析 本题主要考查的是选择排序算法。这是普通的选择排序,每遍排序时将i位置的元素顺序与它后面的元素比较,若比它大,则交换它们的位置。本程序是求二遍降序排序后数据的顺序。答案 C2.有如下VB程序段:For n = 1 To 4 p = n For m = n + 1 To 5If a(m) < a(p) Then p = m Next m If p > n Then temp = a(n) a(n) = a(p) a(p) = temp End IfNext n设数组元素a(1)~a(5)的值分别为“1000,1200,1018,1208,1019”,经过该程序段“加工”后,数组元素a(1)+a(3)的值为( )A.2018 B.2019 C.2200 D.2208解析 本题主要考查的是选择排序算法。排序方式为升序,排序后数组元素a(1)~a(5)的值分别为“1000,1018,1019,1200,1208”,因此a(1)+a(3)=1000+1019=2019。答案 B3.某排序算法的VB程序段如下: n = 10 For i = n To 8 Step -1p = iFor j = i - 1 To 1 Step -1 If a(p) > a(j) Then p = jNext jIf p < i Then tt = a(p): a(p) = a(i): a(i) = ttEnd If Next i For i = 1 To ns = s + Str(a(i)) Next i Text1.Text = sEnd Sub数组元素a(1)到a(10)的值依次为“92,1,84,52,69,50,29,68,87,19”,执行该程序段,文本框Text1中显示的是( )A.92 87 84 69 68 52 50 29 19 1B.92 87 84 52 69 50 68 29 19 1C.92 87 84 69 52 50 68 29 19 1D.92 87 84 52 50 69 68 29 19 1解析 本题是选择排序算法的一种变式。本题的选择排序进行的方式为:从后往前进行排序,即从后往前找到一个最小数,然后让其与最后一个数进行交换位置,再从后往前找到第二小的数,让其与倒数第二个数交换位置,共进行3趟排序,求三趟排序后数列的情况。答案 B4.某程序运行界面如图所示。程序运行时,单击“生成随机数”按钮,将随机生成n个[100,500]区间内的偶数,并在列表框List1中显示;在文本框Text1中输入整数k,单击“排序”按钮,将第k趟(遍)升序排序后的数据显示在列表框List2中。在程序中的划线处,填入适当的语句或表达式,把程序补充完整.Const n = 12Dim d(1 To n) As IntegerPrivate Sub Command1_Click() Dim i As Integer Randomize For i = 1 To n d(i) = Int(Rnd *____①____) * 2 + 100 List1.AddItem Str(d(i)) Next iEnd SubPrivate Sub Command2_Click() Dim k As Integer, i As Integer, j As Integer, t As Integer, p As Integer k = Val(Text1.Text) For i =____②____ p = i For j = i + 1 To n If ____③____ Then p = j Next j If p < > i Then t = d(p): d(p) = d(i): d(i) = t End If Next i For i = 1 To n List2.AddItem Str(d(i)) Next iEnd Sub解析 ①代码表示生成随机数,随机整数的范围为[100,500],括号内的范围为[0,200],因此,①处代码为201;变量i表示排序的趟数,题目要求进行k趟排序,因此②处代码为1 To k;排序方式为升序,因此③处代码为d(p) > d(j)。答案 ①201 ②1 To k ③d(p) > d(j)能力提升5.有一组正整数,要求对其中的素数进行升序排序。排序后素数在前,非素数在后。排序示例如下。Const n = 8Dim a(1 To n) As IntegerPrivate Sub Command1_Click() Dim i As Integer, j As Integer, k As Integer, t As Integer Dim flag As Boolean ′读取一组正整数,存储在数组a中,代码略 For i = 1 To n - 1′(1)If IsPrime(a(k)) Then flag = True Else flag = FalseFor j = i + 1 To n If IsPrime(a(j)) ThenIf Then′(2) k = j flag = TrueEnd If End IfNext jIf k < > i Then t = a(k): a(k) = a(i): a(i) = tEnd IfIf Not flag Then Exit For ′Exit For表示退出循环Next i ′依次输出排序后的数据。代码略End SubFunction IsPrime(m As Integer) As Boolean ′本函数判断m是否是素数:是素数返回值为True,不是素数返回值为False ′代码略End Function程序中加框(1)处应改正为_________________________________________;加框(2)处应改正为________________________________________________。解析 本题主要考查的是选择排序算法。本题对传统的选择排序进行变式,题意是对两类数据进行选择性排序。每趟排序进行时(升序),首先将i位置上的元素当作是最小数,因此(1)处语句应改为k=i,然后到它后面去找更小数,并将该数位置记录在变量k中。变量flag表示每趟进行时i位置上的数是否为素数,如果当前i位置的数不是素数,则找到它后面的第一个素数作为基数,并用k记录此素数的位置;如果素数已经出现过(flag=True),则该素数需要和它之前的素数比较大小,若当前素数更小,则更新k的值。答案 (1)k=i (2)Not flag Or a(j) 6.小炫报名参加“智力大冲浪”节目。比赛规则如下: 比赛开始时参赛者将预先得到M元奖金。比赛时间分为N个时段(N≤100),有N个小游戏,每个时段可完成1个游戏,第i个小游戏必须在规定期限t(i)时段前完成(1≤t(i)≤N),否则要从奖金M元中扣去奖金w(i),w(i)为自然数,不同的游戏扣去的奖金是不一样的。每个游戏必须从整时段开始。注意:比赛绝对不会让参赛者赔钱!例如:当N=5,M=100时游戏编号12345完成期限t(i)14232扣除奖金数w(i)541087在这种情况下,小炫依次完成编号为5、3、4、2、1的小游戏,获得了最高奖金95元。他的算法思想:让扣款高的游戏尽量准时完成。扣除的奖金越少,则最后赢取的奖金越多。(1)按扣款数值从大到小排序,在样例中,排序后游戏编号依次为3、4、5、1、2;(2)对于游戏i,在时间段1到t(i)完成,效果都是一样的,所以尽量放置的时间段t(i)完成,若该时段已经被占用,则依次考查时间段t(i)-1, t(i)-2,……,1。在样例中,①考虑游戏3,放置在时间段2完成(注:t(3)=2);②考虑游戏4,放置在时间段3完成(注:t(4)=3);③考虑游戏5,时间段2已被游戏3占用,放置在时间段1完成(注:t(5)-1=1);④考虑游戏1,时间段1已被游戏5占用,不能按时完成,记录扣款;⑤考虑游戏2,放置在时间段4完成(注:t(2)=4)小炫按如上算法编写了一个VB程序,计算“智力大冲浪”游戏中玩家最多可赢取的奖金,将结果输出到文本框Text1中。VB程序代码如下所示,请在划线处填入合适代码。Dim n As Integer, m As IntegerDim t(1 To 100) As Integer ′变量t(i) 表示第i个游戏的完成期限Dim w(1 To 100) As Integer ′变量w(i) 表示第i个游戏未完成要扣除的奖金Dim f(1 To 100) As Boolean ′变量f(i)表示第i个时段是否已经被占用Private Sub Form_Load() ′初始化游戏设置信息,时段数量n、初始奖金数m 、数组t、数组w ′代码略End SubSub swap(x As Integer, y As Integer) ′自定义过程,用Call语句来调用该过程 Dim z As Integer z = x: x = y: y = zEnd SubSub sort() ′自定义过程,可以用Call语句来调用该过程 Dim x As Integer, i As Integer, j As Integer For i = 1 To n - 1For j = i + 1 To n If w(i) < w(j) ThenCall swap( w(i), w(j) ) ′调用自定义过程 ____①____ End IfNext j Next iEnd SubPrivate Sub Command1_Click()Dim i As Integer, k As Integer, p As Integer Call sort ′调用自定义过程 tot = 0 For i = 1 To nf(i) = True Next i For i = 1 To n ′对每个游戏从该游戏的规定期限开始往左找可用时间段 ′找到可用时间段则完成该游戏,否则放弃该游戏p = -1k = t(i)Do While k > 0 And p = -1 If f(k) = True Thenp = kf(k) = False Else ____②____ End IfLoopIf p = -1 Then tot = tot + w(i) Next i ____③____ Text1.Text=Str(ans)End Sub解析 本题主要考查的是选择排序的朴素(非优化的)算法及程序综合应用能力。自定义过程sort()的功能是将数据按游戏扣除奖金数的降序排序,因此在满足条件时,除了交换扣除奖金数的数据外(t(i)与t(j)),还需交换游戏完成期限的数据,即交换t(i)与t(j)的值,因此①处应填入的语句为Call swap(t(i),t(j)),也可以写作Call swap(t(j),t(i));②处表示f(k) = False时的情况,即第k个时段已被用掉,按照游戏规则,将往左寻找一个空的时段,因此②处语句为k=k-1;变量tot表示扣除的总奖金数,m表示游戏开始前的总的奖金数,因此游戏结束时所获得的奖金数ans为m-tot,故③处应填入的语句为ans=m-tot。答案 ①call swap(t(i),t(j))或Call swap(t(j),t(i))②k=k-1 ③ans=m-tot课件19张PPT。第3节 选择排序及程序实现一、选择排序算法思想每趟排序是在所有的数据中找出最大(或最小)的数据,与第一个数据交换位置,然后再在剩下的数据中找出最大(或最小)的数据,与第二个数据交换位置,以此类推,直到所有元素成为一个有序序列为止。n个数据排序共需进行n-1趟(遍)排序。二、选择排序算法框架设定:对数组d中的n个数据进行升序排序。(1)从前往后进行比较For i = 1 To n - 1 ′n个排序共进行n-1趟排序 假定i位置上的数为最小数 For j = i + 1 To n ′i后面的位置 ′若找到更小的数,则将用k记录此数的位置 Next j If k < > i Then ′若i位置上的数不是最小数,则和k位置上的数进行互换交换d(i)与d(k) End IfNext i注:若要按降序排列,将程序中的语句“If d(k)>d(j)”改为“If d(k)(2)从后往前进行比较For i = 1 To n - 1 ′n个排序共进行n-1趟排序 假定i位置上的数为最小数 For j = n To i + 1 Step -1 ′i后面的位置 ′若找到更小的数,则将用k记录此数的位置 Next j If k < > i Then ′若i位置上的数不是最小数,则和k位置上的数进行互换 交换d(i)与d(k) End IfNext i注:若要按降序排列,将程序中的语句“If d(k)>d(j)”改为“If d(k)(1)从前往后进行比较For i = 1 To n - 1 ′n个排序共进行n-1趟排序 k = i ′假定i位置上的数为最小数 For j = i + 1 To n ′i后面的位置 If d(k) > d(j) Then k = j ′若找到更小的数,则将用k记录此数的位置 Next j If k < > i Then ′若i位置上的数不是最小数,则和k位置上的数进行互换 temp=d(k):d(k)=d(i):d(i)=temp End IfNext i(2)从后往前进行比较For i = 1 To n - 1 ′n个排序共进行n-1趟排序 k = i ′假定i位置上的数为最小数 For j = n To i + 1 Step -1 ′i后面的位置 If d(k) > d(j) Then k = j ′若找到更小的数,则将用k记录此数的位置 Next j If k < > i Then ′若i位置上的数不是最小数,则和k位置上的数进行互换 temp=d(k):d(k)=d(i):d(i)=temp End IfNext i一、选择排序算法思想理解选择排序的基本思想,学会将待排数据按照选择算法思想进行手工模拟排序。【典例1】 使用选择排序对下表中9个数据进行排序,排序过程如下所示:则第三遍的排序结果为( )A.100,90,85,80,70,60,35,50,25B.100,90,85,70,60,35,50,80,25C.100,90,85,80,70,60,50,35,25D.100,90,85,60,70,35,50,80,25解析 本题主要考查选择排序算法的基本思想。观察第1、2遍的排序结果可知,该选择排序为降序排序,第3遍排序时,数据85与80进行交换,因此第三遍排序后的结果为“100,90,85,70,60,35,50,80,25”,答案为B。答案 B【变式训练】 采用选择排序算法对数组d中的8个数据“20,8,6,4,15,3,19,50”进行排序,部分程序如下:For i=1 To 5 k = i For j=i+1 To 8 If d(j) If i< >k Then tt=d(k):d(k)=d(i):d(i)=tt End If Next jNext i该程序段执行后,数组元素d(1)~d(8)依次为( )A.3,4,6,8,15,19,20,50B.3,4,6,8,15,50,20,19C.3,4,6,8,15,20,19,50D.3,4,6,8,15,20,50,19解析 本题主要考查的是选择排序。根据语句“If d(j)【典例2】 有如下VB程序段:For n = 1 To 4 p = n For m = n + 1 To 5 If a(m) < a(p) Then p = m Next m If p > n Then temp = a(n) a(n) = a(p) a(p) = temp End IfNext n设数组元素a(1)~a(5)的值分别为“1000,1200,1018,1208,1019”,经过该程序段“加工”后,数组元素a(1)+a(3)的值为( )A.2018 B.2019 C.2200 D.2208解析 本题主要考查的是选择排序算法。排序方式为升序,排序后数组元素a(1)~a(5)的值分别为“1000,1018,1019,1200,1208”,因此a(1)+a(3)=1000+1019=2019。答案 B【变式训练】 小赵对选择排序算法进行了如下改进:在数组的所有元素中找出最小和最大数据的元素,然后将这两个元素分别与第一个和最后一个元素交换数据,在余下的元素中找出最小和最大数据的元素,分别与第二个和倒数第二个元素交换数据,以此类推,直到所有元素的数据按升序排列。小赵编写的VB程序段如下:p = 1: q = 10Do While p < q iMin = p: iMax = p For i = p + 1 To q If a(i) < a(iMin) Then iMin = i If a(i) > a(iMax) Then iMax = i Next i t = a(iMin): a(iMin) = a(p): a(p) = t ____①____ t = a(iMax): a(iMax) = a(q): a(q) = t p = p + 1 q = q - 1Loop要使程序实现上述算法思想,则程序中划线处的语句是( )A.If iMax = p Then iMax = iMin B.If iMin = p Then iMin = iMaxC.If iMax = p Then iMin = iMaxD.If iMin = p Then iMax = iMin解析 本题考查的是选择排序算法的变式。选择排序的原本思想是找出一个最大(或最小)的元素将它与第一个元素进行互换,本题的选择排序算法思想是:首先找出当前数据中的一个最小元素和一个最大元素,然后将最小元素与队首元素交换,将最大元素与队尾元素进行互换。当最大元素在p位置时,由于它与最小元素进行互换后,原来的存放位置发生了变化,即由p的位置更改为iMin的位置了,因此要将它的新位置记录在iMax中,然后再与q位置上的元素进行互换。因此,答案为A。答案 A【方法总结】 在掌握选择排序常规算法的基础上,还要对选择排序的各种变式进行研究,做到举一反三,触类旁通。 展开更多...... 收起↑ 资源列表 第3节 选择排序及程序实现.doc 第五单元第3讲 选择排序及程序实现.pptx