算法实例选择排序法

1、小越中学信息技术组算法实例 选择排序法1选择排序算法的概念选择排序算法是对冒泡排序算法的改进。这种方法是对参加排序数组的所有元素中找出最小(或最大)数据的元素，使它与第一个元素中数据相互交换位置。然后在余下的元素中找出最小(或最大)的数据的元素，与第二个元素中的数据交换位置。以此类推，直到所有元素成为一个有序的序列。某数组d共有4个元素构成，每个元素的值如下表所示：数组元素数组元素d(1)d(2)d(3)d(4)值值1051239772用选择排序法按升序进行排序的过程，从数组第一个元素开始起：第1遍：寻找从d(1)到d(4)范围内的最小数据d(k)，即k4，将d(1)与d(k)互换数据：共比较

2、数据3次，交换数据1次。第2遍：寻找从d(2)到d(4)范围内的最小数据d(k)，即k3，将d(2)与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)中的数据自然是数组中的最大数据。因此，通过3遍这样的处理，整个数组内的数据将是有序的。4个元素共需进行3遍加工处理，总的比较次数为3216次，而总计交换次数

3、每一遍一次，共计只有3次。对于n个元素的数组，用选择算法进行排序时，比较次数与冒泡算法相同，但交换的次数比冒泡排序要少，因此它具有较高的效率。因此它具有较高的效率。2选择排序算法的程序实现选择排序的程序同样采用双重For循环嵌套来实现，外循环来控制是第几遍加工，内循环用来控制数组内进行排序元素的下标变化范围。在每一遍加工结束，都需要用一个变量来存储这一遍加工中所找出的最小(或最大)的数据在数组内的下标。现有n个数据，分别存放在数组变量a(1 To n)当中，采用选择排序算法程序实现其从小到大的程序结构如下：实现该算法的程序段如下：For i1 To n1kiFor ji1 to n If a(

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

5、下标k，把最小的数据放到a(2)中。这样，每遍加工，都能找出最小数的下标k，比较是不是i，如果不是，就将a(k)与a(i)交换。经过n1遍之后，就能实现从小到大的排序。选择排序的关键在于最小值变量k的值在不断的发生变化，而每一遍加工，最多只交换一次数据，所以排序的效率比冒泡排序要高。本节的学习要求掌握选择排序的基本思想，能根据选择排序的思想来进行选择排序的操作。掌握用程序来实现选择排序的算法，能根据生活中的实际要求编写选排排序的程序，从而进一步熟悉多重循环程序的编写。考查方式为选择题与填空题。1. 用选择排序算法对一组学生的身高数据进行升序排序，已知第一遍排序结束后的数据序列为166、169、

6、177、175、172，则下列选项中可能是原始数据序列的是 ()A175、177、169、166、172 B177、169、166、175、172C166、177、169、175、172 D166、169、172、175、177B 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 D3某校通过政府招投标

7、中心采购一套多媒体教学设备，有5家单位参加竞标，竞标价分别为18万、17万、23万、15万、16万元人民币。若采用选择排序算法对标价从大到小排序，需要进行数据互换的次数是 ()A1 B3C4 D5B 4圣诞节即将来临，某商场欲对仓库某货号商品进行补仓以应对即将举办的促销活动。6家供货商给出的报价分别为48、43、60、46、58、55，若采用选择排序算法对其进行从大到小排序，则第三遍的排序结果是()C 原始数据原始数据484360465855第第1遍遍604348465855第第2遍遍605848464355第第3遍遍第第4遍遍605855484346第第5遍遍605855484643A.60

8、、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都是排序算法，可能是冒泡排序或者选择排序，下面的表格反应的是在不同量的数据下，排序时进行数据交换的次数，分析算法1与算法2最有可能的排序算法分别是 ()C 排序的数据个数排序的数据个数算法算法1的交换次数的交换次数算法算法2的交换次数的交换次数57311418228313537485284182171105291094A.冒泡排序冒泡排序 B选择排序选择排序C冒泡排序选择排序 D选择排序冒泡排序6. 下列关于排序的说法，错误

9、的是 ()A相对而言，选择排序算法的效率比冒泡排序算法高B冒泡排序算法和选择排序算法的都需要用到双循环结构C对于n个无序数据，不管是冒泡排序还是选择排序，都要经过n1遍加工D冒泡排序算法的程序实现一般要用到数组变量k，而选择排序则不需要C 7. 小明编写了一个统计数组元素a(l)到a(n)中的“升序段”个数s(如图所示的数据序列，其 “升序段”的个数等于3)的VB程序。部分程序代码如下：k 0 s 0For i 2 To n If a(i) a(i 1) Then Else k 0 End If If k 1 Then s s 1 Next iTextl.Text Str(s) 方框中的正确语

10、句是()Akk1BK1CK1DKk1D 上虞区小越中学信息技术组1.利用已学的选择排序算法，对初始数据 49,38,65,97,76,13,27,49，进行认真的排序，并详细记录分次加工过程，请列出每次加工的数据序列。序后 13 38 65 97 76 49 27 49第二趟排序后 13 27 65 97 76 49 38 49第三趟排序后 13 27 38 97 76 49 65 49第四趟排序后 13 27 38 49 76 97 65 49第五趟排序后 13 27 38 49 49 97 65 76第六趟排序后 13 27 38 49 49 65 97 76第七趟排序后 13 27 38

11、 49 49 65 76 97最后排序结果 13 27 38 49 49 65 76 972.请完善选择排序算法的通用流程图(从小到大的顺序)。 【例1】在2015年秋季学校运动会上，男生第一组6位选手的110米栏成绩(单位：秒)分别是“18.4、17.3、16.9、18.8、18.1、16.7”，若使用选择排序法将该组的成绩按第一名、第二名、第三名的顺序排序，则第一次交换数据后的顺序是 () A.18.818.417.316.918.116.7 B.16.717.316.918.818.118.4 C.18.817.316.918.418.116.7 D.16.718.417.316.918

12、.818.1【例2】(浙江省2012年9月高考)实现某排序算法的部分VB程序如下： For i = 1 To 6k = iFor j = i + 1 To 7If a(j) a(k) Then k = jNext jIf i k Thent = a(i): a(i) = a(k): a(k) = tEnd IfNext i 在排序过程中，经过某一遍排序“加工”后，数组元素a(1)到a(7)的数据依次为“10，41，75，12，63，11，85”。则下一遍排序“加工”后数组元素a(1)到a(7)的数据依次是（） A. 10, 11, 41, 75, 12, 63, 85 B. 10, 11, 7

13、5, 12, 63, 41, 85 C. 10, 11, 12, 75, 63, 41, 85 D. 10, 11, 12, 41, 63, 75, 85上虞区小越中学信息技术组1.选择排序的基本思想是在所有的记录中选出最小(大)的数据，把它与第一个数据交换，然后在其余的记录中再选出最小(大)的数据与第二个数据交换，依此类推，直至所有数据排序完成。有一组数据，顺序是“4、6、2、8、9”，用选择排序法将这组数据从大到小排序，第二遍交换数据后的顺序是 （） A.9、4、6、2、8 B.9、8、4、2、6 C.9、8、2、4、6 D.9、8、2、6、4练习2.电视台为了统计参赛选手的短信支持度，来

14、确定参赛选手的人气，对观众短信进行记录，针对这一情况编写程序过程中效率最高的算法是 （） A.枚举算法B.解析算法C.选择排序D.冒泡排序3.有一组原始数据：21.0、35.3、31.6、12.8、37.0、19.0，利用选择排序算法进行从小到大的排序，经过第二次加工后的数据排列顺序是 （） A.19.0、21.0、35.3、31.6、12.8、37.0 B.19.0、35.3、31.6、12.8、37.0、21.0C.12.8、35.3、31.6、21.0、37.0、19.0 D.12.8、19.0、31.6、21.0、37.0、35.3上虞区小越中学信息技术组 4.有一组原始数据： gam

15、e、car、oae、eat、win、base、dog，利用选择排序算法进行从小到大的排序， 经过第二次加工后的数据排列顺序是 （） A.base、car、game、oae、eat、win、dog B.base、game、car、oae、eat、win、dog C.base、car、oae、eat、win、game、dog D.base、dog、game、car、oae、eat、win算法应用开发工程师职业概述：如果要问程序设计的灵魂是什么，相信很多人都会回答是算法，一个优秀的算法工程师往往可以带来生产力的巨大提升。当你为实现某一功能而冥思苦想、费尽周折时，可能你需要的只是另一个精辟而又简洁的算法。工作内容：设计和优化应用算法，并协助完成应用软件方案设计及算法设计；独立完成数学建模及算法设计；编写相关技术文档。职业要求：教育培训： 应用数学、计算机等相关专业本科以上学历。工作经验：算法开发人员重在很强的逻辑思维能力。并且需要熟练掌握数学建模、应用算法的设计和优化理论；精通C/C+ 或其他一种编程语言；熟悉数据库的接口技术。薪资行情：一般月薪范围45001