3.5选择排序算法及程序实现课件.ppt

1、1选择排序算法的概念选择排序算法的概念选择排序算法是对冒泡排序算法的改进。这种方法是选择排序算法是对冒泡排序算法的改进。这种方法是对参加排序数组的所有元素中找出最小对参加排序数组的所有元素中找出最小(或最大或最大)数据的元数据的元素，使它与第一个元素中数据相互交换位置。然后在余下素，使它与第一个元素中数据相互交换位置。然后在余下的元素中找出最小的元素中找出最小(或最大或最大)的数据的元素，与第二个元素的数据的元素，与第二个元素中的数据交换位置。以此类推，直到所有元素成为一个有中的数据交换位置。以此类推，直到所有元素成为一个有序的序列。序的序列。某数组某数组d共有共有4个元素构成，每个元素的值如

2、下表所示个元素构成，每个元素的值如下表所示：35 选择排序算法及程序实现选择排序算法及程序实现数组元素数组元素d(1)d(2)d(3)d(4)值值1051239772用选择排序法按升序进行排序的过程，从数组第一个元素开用选择排序法按升序进行排序的过程，从数组第一个元素开始起：始起：第第1遍：寻找从遍：寻找从d(1)到到d(4)范围内的最小数据范围内的最小数据d(k)，即，即k4，将将d(1)与与d(k)互换数据：互换数据：共比较数据共比较数据3次，交换数据次，交换数据1次。次。第第2遍：寻找从遍：寻找从d(2)到到d(4)范围内的最小数据范围内的最小数据d(k)，即，即k3，将，将d(2)与与

3、d(k)互换数据：互换数据：共比较数据共比较数据2次，交换数据次，交换数据1次。次。第第3遍：寻找从遍：寻找从d(3)到到d(4)范围内的最小数据范围内的最小数据d(k)，即，即k4，将，将d(3)与与d(k)互换数据：互换数据：总共比较数据总共比较数据1次，交换数据次，交换数据1次。次。显然，通过上述显然，通过上述3遍处理，数组遍处理，数组d中最小、第中最小、第2小、第小、第3小的数据已经分别存储在数组元素小的数据已经分别存储在数组元素d(1)、d(2)、d(3)中，即中，即数组元素数组元素d(1)到到d(3)变为有序，而剩下的变为有序，而剩下的d(4)中的数据自然中的数据自然是数组中的最大

4、数据。因此，通过是数组中的最大数据。因此，通过3遍这样的处理，整个数遍这样的处理，整个数组内的数据将是有序的。组内的数据将是有序的。4个元素共需进行个元素共需进行3遍加工处理，总的比较次数为遍加工处理，总的比较次数为3216次，而总计交换次数每一遍一次，共计只有次，而总计交换次数每一遍一次，共计只有3次。次。对于对于n个元素的数组，用选择算法进行排序时，比较个元素的数组，用选择算法进行排序时，比较次数与冒泡算法相同，但交换的次数比冒泡排序要少，因次数与冒泡算法相同，但交换的次数比冒泡排序要少，因此它具有较高的效率。此它具有较高的效率。2选择排序算法的程序实现选择排序算法的程序实现选择排序的程序

5、同样采用双重选择排序的程序同样采用双重For循环嵌套来实现，循环嵌套来实现，外循环来控制是第几遍加工，内循环用来控制数组内进行外循环来控制是第几遍加工，内循环用来控制数组内进行排序元素的下标变化范围。在每一遍加工结束，都需要用排序元素的下标变化范围。在每一遍加工结束，都需要用一个变量来存储这一遍加工中所找出的最小一个变量来存储这一遍加工中所找出的最小(或最大或最大)的数的数据在数组内的下标。据在数组内的下标。现有现有n个数据，分别存放在数组变量个数据，分别存放在数组变量a(1 To n)当中，采当中，采用选择排序算法程序实现其从小到大的程序结构如下：用选择排序算法程序实现其从小到大的程序结构如

6、下：实现该算法的程序段如下：实现该算法的程序段如下：For i1 To n1kiFor ji1 to nIf a(j)a(k) Then kjNext jIf ik Thenta(i)：a(i)a(k)：a(k)tEnd IfNext i当外循环变量当外循环变量i取取1时，为第时，为第1遍加工，遍加工，k1，先假设第，先假设第1个数个数据元素为最小值，内循环从第据元素为最小值，内循环从第2个数开始比较，如果个数开始比较，如果a(2)小于小于a(1)，则将则将a(2)的下标赋值给的下标赋值给k，否则，否则k值不变，这个方法目的是保证值不变，这个方法目的是保证k是是本遍加工最小数据元素的下标。这样

7、，内循环一次完成之后，判本遍加工最小数据元素的下标。这样，内循环一次完成之后，判断断k是不是是不是a(1)的下标的下标1，如果不是，则把，如果不是，则把a(k)与与a(1)的数据进行交的数据进行交换，否则就不进行交换。这样，第换，否则就不进行交换。这样，第1遍加工后，就能把最小的数据遍加工后，就能把最小的数据存放在存放在a(1)中。当外层循环变量中。当外层循环变量i取取2时，为第时，为第2遍加工，找出遍加工，找出a(2)到到a(n)之间的最小数，记录好它的下标之间的最小数，记录好它的下标k，把最小的数据放到，把最小的数据放到a(2)中。中。这样，每遍加工，都能找出最小数的下标这样，每遍加工，都

8、能找出最小数的下标k，比较是不是，比较是不是i，如果不，如果不是，就将是，就将a(k)与与a(i)交换。经过交换。经过n1遍之后，就能实现从小到大的遍之后，就能实现从小到大的排序。排序。选择排序的关键在于最小值变量选择排序的关键在于最小值变量k的值在不断的发生变化，而每的值在不断的发生变化，而每一遍加工，最多只交换一次数据，所以排序的效率比冒泡排序要高。一遍加工，最多只交换一次数据，所以排序的效率比冒泡排序要高。本节的学习要求掌握选择排序的基本思想，能根据本节的学习要求掌握选择排序的基本思想，能根据选择排序的思想来进行选择排序的操作。掌握用程序来选择排序的思想来进行选择排序的操作。掌握用程序来

9、实现选择排序的算法，能根据生活中的实际要求编写选实现选择排序的算法，能根据生活中的实际要求编写选排排序的程序，从而进一步熟悉多重循环程序的编写。排排序的程序，从而进一步熟悉多重循环程序的编写。考查方式为选择题与填空题。考查方式为选择题与填空题。1. 用选择排序算法对一组学生的身高数据进行升序排序，已用选择排序算法对一组学生的身高数据进行升序排序，已知第一遍排序结束后的数据序列为知第一遍排序结束后的数据序列为166、169、177、175、172，则下列选项中可能是原始数据序列的是，则下列选项中可能是原始数据序列的是 ()A175、177、169、166、172 B177、169、166、175

10、、172C166、177、169、175、172 D166、169、172、175、177B B 2有有6位裁判为运动员评分，给出的分数分别为位裁判为运动员评分，给出的分数分别为48、45、63、46、59、57。采用选择排序算法对其进行排序，若。采用选择排序算法对其进行排序，若完成第一遍时的结果为：完成第一遍时的结果为：63、45、48、46、59、57，则，则完成第二遍时的结果是完成第二遍时的结果是 ()A63、45、48、46、59、57 B63、59、57、48、45、46C63、59、57、46、45、48 D63、59、48、46、45、57 D D3某校通过政府招投标中心采购一套

11、多媒体教学设备，有某校通过政府招投标中心采购一套多媒体教学设备，有5家单家单位参加竞标，竞标价分别为位参加竞标，竞标价分别为18万、万、17万、万、23万、万、15万、万、16万万元人民币。若采用选择排序算法对标价从大到小排序，需要元人民币。若采用选择排序算法对标价从大到小排序，需要进行数据互换的次数是进行数据互换的次数是 ()A1 B3C4 D5B B 4圣诞节即将来临，某商场欲对仓库某货号商品进行圣诞节即将来临，某商场欲对仓库某货号商品进行补仓以应对即将举办的促销活动。补仓以应对即将举办的促销活动。6家供货商给出的家供货商给出的报价分别为报价分别为48、43、60、46、58、55，若采用

12、选择，若采用选择排序算法对其进行从大到小排序，则第三遍的排序排序算法对其进行从大到小排序，则第三遍的排序结果是结果是()C C 原始数据原始数据484360465855第第1遍遍604348465855第第2遍遍605848464355第第3遍遍第第4遍遍605855484346第第5遍遍605855484643A.60、58、48、46、43、55 B.60、43、48、46、58、55C.60、58、55、46、43、48 D.60、58、55、48、46、435. 已知算法已知算法1与算法与算法2都是排序算法，可能是冒泡排序或者选择排都是排序算法，可能是冒泡排序或者选择排序，下面的表格反

13、应的是在不同量的数据下，排序时进行数据序，下面的表格反应的是在不同量的数据下，排序时进行数据交换的次数，分析算法交换的次数，分析算法1与算法与算法2最有可能的排序算法分别是最有可能的排序算法分别是 ()C C 排序的数据个数排序的数据个数算法算法1的交换次数的交换次数算法算法2的交换次数的交换次数57311418228313537485284182171105291094A.冒泡排序冒泡排序冒泡排序冒泡排序 B选择排序选择排序选择排序选择排序C冒泡排序选择排序冒泡排序选择排序 D选择排序冒泡排序选择排序冒泡排序6.6. 下列关于排序的说法，错误的是下列关于排序的说法，错误的是 ( () )A

14、A相对而言，选择排序算法的效率比冒泡排序算法高相对而言，选择排序算法的效率比冒泡排序算法高B B冒泡排序算法和选择排序算法的都需要用到双循环结构冒泡排序算法和选择排序算法的都需要用到双循环结构C C对于对于n n个无序数据，不管是冒泡排序还是选择排序，都要个无序数据，不管是冒泡排序还是选择排序，都要经过经过n n1 1遍加工遍加工D D冒泡排序算法的程序实现一般要用到数组变量冒泡排序算法的程序实现一般要用到数组变量k k，而选择，而选择排序则不需要排序则不需要C C 7.7. 小明编写了一个统计数组元素小明编写了一个统计数组元素a(l)a(l)到到a(n)a(n)中的中的“升序段升序段”个个数

15、数s(s(如图所示的数据序列，其如图所示的数据序列，其 “ “升序段升序段”的个数等于的个数等于3)3)的的VBVB程序。程序。部分程序代码如下：部分程序代码如下：k k 0 0 s s 0 0For i For i 2 To n2 To n If a(i) a(i If a(i) a(i 1) Then1) Then Else Else k k 0 0 End If End If If k If k 1 Then s 1 Then s s s 1 1 Next iNext iTextl.Text Textl.Text Str(s) Str(s) 方框中的正确语句是方框中的正确语句是( ()

16、)A Ak kk k1 1B BK K1 1C CK K1 1D DK Kk k1 1D D For i 1 To n 1k i For j i 1 To n If d(j) d(k) Then k j Next jIf i k Then t d(i) : d(i) d(k) : d(k) tEnd IfNext iD D8下列下列VB程序段是选择法排序程序的主要部分。其中虚程序段是选择法排序程序的主要部分。其中虚线框内代码用于寻找数组元素线框内代码用于寻找数组元素d(i)到到d(n)的最小值。的最小值。虚虚线框内代码运行结束时，保虚虚线框内代码运行结束时，保存最小值的数组元素一定是存最小值的

17、数组元素一定是()Ad(n)Bd(j)Cd(i)Dd(k)D9. 有如下有如下VB程序，运行时，点击程序，运行时，点击“随机产生随机产生15个整数个整数”按钮按钮将随机产生将随机产生15个个1000以内的随机非负整数，如下图所示，以内的随机非负整数，如下图所示，Private Sub Command2_Click() 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 i k Then t a(i): a(i) a(k): a(k) t End If Next i For i 1 To n List2.AddIte

18、m Str(i) & “：” & Str(a(i) Next iEnd Sub注：该示例程序在素材文件夹下注：该示例程序在素材文件夹下vb26文件夹中。文件夹中。点击点击“选择排序选择排序”时，输出的数据结果在屏幕上从上到下的时，输出的数据结果在屏幕上从上到下的显示顺序为显示顺序为_(选填从大到小选填从大到小/从小到大从小到大)。若要使它以。若要使它以相反的顺序显示，那么方框内的语句应修改为相反的顺序显示，那么方框内的语句应修改为_。从小到大从小到大a(j)a(k)102010年冬奥会开幕式中各代表团的入场顺序是：希腊排在第一位，东道主加年冬奥会开幕式中各代表团的入场顺序是：希腊排在第一位，东

19、道主加拿大排在最后一位，其余拿大排在最后一位，其余80个代表团入场顺序按国家或地区名称依次排列。个代表团入场顺序按国家或地区名称依次排列。下列下列VB程序实现如下功能：单击命令按钮程序实现如下功能：单击命令按钮Command1后，在列表框后，在列表框List1中中按入场顺序显示所有代表团的名称。请回答下列问题：按入场顺序显示所有代表团的名称。请回答下列问题：(1)虚线框内程序段所用的排序算法虚线框内程序段所用的排序算法的名称是的名称是_。在划线出填入合适的代码。在划线出填入合适的代码。 Dim a(0 To 81) As String Dim n As Integer Private Sub

20、Form_Load()用于用于将将82个参赛代表团名称放入数组个参赛代表团名称放入数组a中中n 80a(0) “Greece”a(n 1) “Canada”另外另外80个代表团名称放在个代表团名称放在a(1)至至a(80)中，代码略中，代码略End SubPrivate Sub Command1_Click() Dim s As Dim i As Integer, j As Integer, k As Integer For i=1 To n-1 k=i For j=i+1 To n If a(j) a(k) Then k=j Next j s=a(i):a(i)=a(k):a(k)=s Ne

21、xt i List1.Clear For i 0 To List1.AddItem a(i) Next iEnd Sub选择排序算法选择排序算法String81 (3)程序中划线处应填入程序中划线处应填入_。(2)程序中划线处应填入程序中划线处应填入_。 11某俱乐部举行射击比赛，最后有十人进入决某俱乐部举行射击比赛，最后有十人进入决赛，录入员编制了如下赛，录入员编制了如下VB程序，功能是根据成绩程序，功能是根据成绩进行排序，程序中数组进行排序，程序中数组a保存所有参赛者的姓名，保存所有参赛者的姓名，数组数组b保存此成绩对应的成绩，第保存此成绩对应的成绩，第i位参赛者的姓位参赛者的姓名保存在名

22、保存在a(i)中，成绩保存在中，成绩保存在b(i)中。中。程序界面如图所示，左边列表框程序界面如图所示，左边列表框List1中显示原始中显示原始数据数据(姓名和相应的成绩姓名和相应的成绩)，单击，单击“排序排序”按钮按钮(Command1)，排序后的结果按成绩从高到低显示，排序后的结果按成绩从高到低显示在列表框在列表框List2中。中。解决此问题的算法流程图如图所示，排序部分的程序段如下：解决此问题的算法流程图如图所示，排序部分的程序段如下：Dim a(1 To 12) As StringDim b(1 To 12) As SinglePrivate Sub Command1_Click()

23、Dim i As Integer, j As Integer, k As Integer, x As Single, y As String For i 1 To 11 k i For j i 1 To 12 If Then k j Next j If k i Then y a(i): a(i) a(k): a(k) y End If Next i For i 1 To 12 List2.AddItem a(i) ” ” Str(b(i) Next iEnd SubPrivate Sub Form_Load() 此过程用于对数组此过程用于对数组a和数组和数组b进行初始赋值，代码略进行初始赋值，

24、代码略End Sub(1)解决此问题的算法是解决此问题的算法是_。(2)程序中划线处应填入程序中划线处应填入_。(3)程序中划线处应填入程序中划线处应填入_。注：该示例程序在素材文注：该示例程序在素材文件夹下件夹下vb27文件夹中。文件夹中。选择排序算法选择排序算法b(j)b(k)x=b(i):b(i)=b(k):b(k)=x12. 某校高三年级段要将模拟考试成绩进行一个排名，需某校高三年级段要将模拟考试成绩进行一个排名，需要对总分进行排名次。以下程序运行时，自动在列表要对总分进行排名次。以下程序运行时，自动在列表框显示学生姓名与成绩，点击框显示学生姓名与成绩，点击“排名次排名次”按钮按钮Co

25、mmand1，将按成绩从高，将按成绩从高到底进行排序。到底进行排序。程序运行界面如下图所示：程序运行界面如下图所示：部分程序代码如下所示：部分程序代码如下所示：Dim xm(1 To 45) As String用于存储学生姓名用于存储学生姓名Dim cj(1 To 45) As Single 用于存储学生总分用于存储学生总分Private Sub Command1_Click()List1.ClearDim i As Integer, j As Integer, k As Integer, x As Single, y As StringFor i 1 To 44 k i For _If cj

26、(j) cj(k) Then k j Next j If k i Thenx cj(i)：cj(i) cj(k): cj(k) xy xm(i): xm(i) xm(k): xm(k) y End If Next iFor i _ List1.AddItem Str(i) ” ” xm(i) ” ” Str(cj(i)Next iEnd Sub 在程序和划线处，填入适当的语在程序和划线处，填入适当的语句或表达式句或表达式，把程序补充完整：，把程序补充完整：(1)程序中划线处应填入程序中划线处应填入_。(2)程序中划线处应填入程序中划线处应填入_。注：该示例程序在素材文件夹下注：该示例程序在素材

27、文件夹下vb28文件夹中。文件夹中。Private Sub Form_Load()此处为姓名与成绩赋值语句，忽略此处为姓名与成绩赋值语句，忽略For i 1 To 45 List1.AddItem xm(i) ” ” Str(cj(i)Next iEnd Subj=i+1 To 451 To 4513. (操作题操作题)设计一个设计一个VB程序，模拟电商网站的商品价程序，模拟电商网站的商品价格排序格排序(假设共假设共100个价格个价格)。运行界面如下图所示：。运行界面如下图所示：控件类控件类控件名称控件名称属性属性属性值属性值说明说明窗体窗体Form1Caption价格排序价格排序定义程序的窗

28、口标题栏文本定义程序的窗口标题栏文本框架框架Frame1Caption排序方式排序方式框架为单选控件提供可识别框架为单选控件提供可识别的分组，美化窗体的分组，美化窗体单选按钮单选按钮Option1Caption按价格从低到高按价格从低到高提示排序方式提示排序方式(升序升序)单选按钮单选按钮Option2Caption按价格从高到低按价格从高到低提示排序方式提示排序方式(降序降序)列表框列表框List1显示价格数组显示价格数组a中数据中数据命令按钮命令按钮Command1Caption排序排序说明按钮的作用说明按钮的作用(1)请按下表中的说明在窗体中添加控件并设置控件的属性值：请按下表中的说明在

29、窗体中添加控件并设置控件的属性值：(2)打开代码窗口，添加变量声明代码：打开代码窗口，添加变量声明代码： Dim a(1 To 100) As Single 定义价格数组定义价格数组 Dim i As Integer, j As Integer, k As Integer Dim t As Single Const n 100(3)双击窗体，添加数组初始化代码：双击窗体，添加数组初始化代码：Private Sub Form_Load()For i 1 To 100 a(i) Format(Rnd() * 100 500, “00.0”) 模拟价格，模拟价格，产生产生500至至600一个随机数，

30、带一位小数一个随机数，带一位小数 List1.AddItem a(i) Next iEnd Sub(4)双击双击“排序排序”按钮按钮Command1，添加如下代码，添加如下代码Private Sub Command1_Click()List1.ClearFor i 1 To n 1 k i For j i 1 To n If Option1.Value True ThenIf Then k j 按价格从低到高排序按价格从低到高排序ElseIf a(j) a(k) Then k j 按价格从高到底排序按价格从高到底排序End If Next j If i k Thent a(i): a(i) a(k): a(k) t End IfNext iFor i 1 To 100 显示排序后的数据显示排序后的数据Next iEnd Sub(5)在程序和划线处，填入适当的语句或表达式，把程在程序和划线处，填入适当的语句或表达式，把程序补充完整：序补充完整：划线处应填入划线处应填入_。划线处应填入划线处应填入_。(6)程序调试正确后，在当前文件夹下生成程序调试正确后，在当前文件夹下生成“moni.exe”，并，并递交给老师。递交给老师。注：该示例程序在素材文件夹下注：该示例程序在素材文件夹下vb29文件夹中。文件夹中。a(j)a(k) List1.AddItem a(i)