算法实例选择排序法

小越中学信息技术组算法实例选择排序法临沭县实验中学1．选择排序算法的概念选择排序算法是对冒泡排序算法的改进。这种方法是对参加排序数组的所有元素中找出最小(或最大)数据的元素，使它与第一个元素中数据相互交换位置。然后在余下的元素中找出最小(或最大)的数据的元素，与第二个元素中的数据交换位置。以此类推，直到所有元素成为一个有序的序列。某数组d共有4个元素构成，每个元素的值如下表所示：数组元素d(1)d(2)d(3)d(4)值1051239772用选择排序法按升序进行排序的过程，从数组第一个元素开始起：第1遍：寻找从d(1)到d(4)范围内的最小数据d(k)，即k＝4，将d(1)与d(k)互换数据：共比较数据3次，交换数据1次。第2遍：寻找从d(2)到d(4)范围内的最小数据d(k)，即k＝3，将d(2)与d(k)互换数据：共比较数据2次，交换数据1次。第3遍：寻找从d(3)到d(4)范围内的最小数据d(k)，即k＝4，将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遍加工处理，总的比较次数为3＋2＋1＝6次，而总计交换次数每一遍一次，共计只有3次。对于n个元素的数组，用选择算法进行排序时，比较次数与冒泡算法相同，但交换的次数比冒泡排序要少，因此它具有较高的效率。2．选择排序算法的程序实现选择排序的程序同样采用双重For循环嵌套来实现，外循环来控制是第几遍加工，内循环用来控制数组内进行排序元素的下标变化范围。在每一遍加工结束，都需要用一个变量来存储这一遍加工中所找出的最小(或最大)的数据在数组内的下标。现有n个数据，分别存放在数组变量a(1Ton)当中，采用选择排序算法程序实现其从小到大的程序结构如下：实现该算法的程序段如下：Fori＝1Ton－1k＝iForj＝i＋1tonIfa(j)a(k)Thenk＝jNextjIfikThent＝a(i)：a(i)＝a(k)：a(k)＝tEndIfNexti当外循环变量i取1时，为第1遍加工，k＝1，先假设第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)之间的最小数，记录好它的下标k，把最小的数据放到a(2)中。这样，每遍加工，都能找出最小数的下标k，比较是不是i，如果不是，就将a(k)与a(i)交换。经过n－1遍之后，就能实现从小到大的排序。选择排序的关键在于最小值变量k的值在不断的发生变化，而每一遍加工，最多只交换一次数据，所以排序的效率比冒泡排序要高。选择排序方法1234567431891355743以7个元素为例说明选择排序位置1~位置7的元素初始排列如下所示选择排序实例1234567431891355743第一趟：从7个元素中选出最小者，将其换入位置1，过程为：令min_elem表示最小元素（初值为位置1的元素），k为最小元素的位置序号（初值为1），逐一比较，找出最小元素及其位置位置6的元素最小交换12345677439135543431234567718913554343第二趟：从6个元素中选出最小者，将其换入位置2，过程为：令min_elem表示最小元素（初值为位置2的元素），k为最小元素的位置序号（初值为2），逐一比较，找出最小元素及其位置位置3的元素最小交换12345677918135543431234567791813554343第三趟：从5个元素中选出最小者，将其换入位置3，过程为：令min_elem表示最小元素（初值为位置3的元素），k为最小元素的位置序号（初值为3），逐一比较，找出最小元素及其位置位置4的元素最小交换12345677913185543431234567791318554343第四趟：从4个元素中选出最小者，将其换入位置4，过程为：令min_elem表示最小元素（初值为位置4的元素），k为最小元素的位置序号（初值为4），逐一比较，找出最小元素及其位置位置4的元素最小交换12345677913185543431234567791318554343第五趟：从3个元素中选出最小者，将其换入位置5，过程为：令min_elem表示最小元素（初值为位置5的元素），k为最小元素的位置序号（初值为5），逐一比较，找出最小元素及其位置位置6的元素最小交换12345677913184355431234567791318435543第六趟：从2个元素中选出最小者，将其换入位置6，过程为：令min_elem表示最小元素（初值为位置6的元素），k为最小元素的位置序号（初值为6），逐一比较，找出最小元素及其位置位置7的元素最小交换12345677913184343551234567431891355743以7个元素为例，经过6趟选择，将元素排列有序排序1234567791318434355选择排序流程图7个元素进行选择排序时，需要六趟，用i表示趟数i←1i=6?结束Yi←i+1N进行第i趟选择排序开始7个元素进行选择排序时，需要六趟，用i表示趟数i←1i=6?结束Yi←i+1Nk表示最小元素的位置k←i,j←i+1比较ak和aj如果ajak则令k=jj←j+1NY交换ak和aj开始j=7?简单选择排序算法的性能分析移动次数：最好情况（正序）：0次12345123451234512345123451234最坏情况：3(n-1)次简单选择排序算法的性能分析移动次数：最好情况（正序）：0次空间性能：需一个辅助空间。稳定性：是一种稳定的排序算法。45231152341253412354123451234比较次数：)()1(21211nOnninni=-=--=）（简单选择排序的时间复杂度为O(n2)。1.用选择排序算法对一组学生的身高数据进行升序排序，已知第一遍排序结束后的数据序列为166、169、177、175、172，则下列选项中可能是原始数据序列的是()A．175、177、169、166、172B．177、169、166、175、172C．166、177、169、175、172D．166、169、172、175、177B2．有6位裁判为运动员评分，给出的分数分别为48、45、63、46、59、57。采用选择排序算法对其进行排序，若完成第一遍时的结果为：63、45、48、46、59、57，则完成第二遍时的结果是()A．63、45、48、46、59、57B．63、59、57、48、45、46C．63、59、57、46、45、48D．63、59、48、46、45、57D3．某校通过政府招投标中心采购一套多媒体教学设备，有5家单位参加竞标，竞标价分别为18万、17万、23万、15万、16万元人民币。若采用选择排序算法对标价从大到小排序，需要进行数据互换的次数是()A．1B．3C．4D．5B4．圣诞节即将来临，某商场欲对仓库某货号商品进行补仓以应对即将举办的促销活动。6家供货商给出的报价分别为48、43、60、46、58、55，若采用选择排序算法对其进行从大到小排序，则第三遍的排序结果是()C原始数据484360465855第1遍604348465855第2遍605848464355第3遍第4遍605855484346第5遍605855484643A.60、58、48、46、43、55B.60、43、48、46、58、55C.60、58、55、46、43、48D.60、58、55、48、46、435.已知算法1与算法2都是排序算法，可能是冒泡排序或者选择排序，下面的表格反应的是在不同量的数据下，排序时进行数据交换的次数，分析算法1与算法2最有可能的排序算法分别是()C排序的数据个数算法1的交换次数算法2的交换次数57311418228313537485284182171105291094A.冒泡排序冒泡排序B．选择排序选择排序C．冒泡排序选择排序D．选择排序冒泡排序6.下列关于排序的说法，错误的是()A．相对而言，选择排序算法的效率比冒泡排序算法高B．冒泡排序算法和选择排序算法的都需要用到双循环结构C．对于n个无序数据，不管是冒泡排序还是选择排序，都要经过n－1遍加工D．冒泡排序算法的程序实现一般要用到数组变量k，而选择排序则不需要C上虞区小越中学信息技术组1.利用已学的选择排序算法，对初始数据［49,38,65,97,76,13,27,49］，进行认真的排序，并详细记录分次加工过程，请列出每次加工的数据序列。第一趟排序后13［38659776492749］第二趟排序后1327［659776493849］第三趟排序后132738［9776496549］第四趟排序后13273849［76976549］第五趟排序后1327384949［976576］第六趟排序后132738494965［9776］第七趟排序后13273849496576［97］最后排序结果13273849496576972.请完善选择排序算法的通用流程图(从小到大的顺序)。【例1】在2015年秋季学校运动会上，男生第一组6位选手的110米栏成绩(单位：秒)分别是“18.4、17.3、16.9、18.8、18.1、16.7”，若使用选择排序法将该组的成绩按第一名、第二名、第三名……的顺序排序，则第一次交换数据后的顺序是()A.18.818.417.316.918.116.7B.16.717.316.918.818.118.4C.18.817.316.918.418.116.7D.16.718.417.316.918.818.1【例2】(浙江省2012年9月高考)实现某排序算法的部分VB程序如下：Fori=1To6k=iForj=i+1To7Ifa(j)＜a(k)Thenk=jNextjIfi＜＞kThent=a(i):a(i)=a(k):a(k)=tEndIfNexti在排序过程中，经过某一遍排序“加工”后，数组元素a(1)到a(7)的数据依次为“10，41，75，12，63，11，85”。则下一遍排序“加工”后数组元素a(1)到a(7)的数据依次是（）A.10,11,41,75,12,63,85B.10,11,75,12,63,41,85C.10,11,12,75,63,41,85D.10,11,12,41,63,75,85B找出最小的小的不在前面就交换B1.选择排序的基本思想是在所有的记录中选出最小(大)的数据，把它与第一个数据交换，然后在其余的记录中再选出最小(大)的数据与第二个数据交换，依此类推，直至所有数据排序完成。有一组数据，顺序是“4、6、2、8、9”，用选择排序法将这组数据从大到小排序，第二遍交换数据后的顺序是（）A.9、4、6、2、8B.9、8、4、2、6C.9、8、2、4、6D.9、8、2、6、4练习2.电视台为了统计参赛选手的短信支持度，来确定参赛选手的人气，对观众短信进行记录，针对这一情况编写程序过程中效率最高的算法是（）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.0B.19.0、35.3、31.6、12.8、37.0、21.0C.12.8、35.3、31.6、21.0、37.0、19.0D.12.8、19.