算法实例选择排序法.ppt

小越中学信息技术组算法实例选择排序法临沭县实验中学1选择排序算法的概念选择排序算法是对冒泡排序算法的改进。这种方法是对参加排序数组的所有元素中找出最小(或最大)数据的元素，使它与第一个元素中数据相互交换位置。然后在余下的元素中找出最小(或最大)的数据的元素，与第二个元素中的数据交换位置。以此类推，直到所有元素成为一个有序的序列。某数组d共有4个元素构成，每个元素的值如下表所示：数组元素数组元素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)与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次。对于n个元素的数组，用选择算法进行排序时，比较次数与冒泡算法相同，但交换的次数比冒泡排序要少，因此它具有较高的效率。因此它具有较高的效率。2选择排序算法的程序实现选择排序的程序同样采用双重For循环嵌套来实现，外循环来控制是第几遍加工，内循环用来控制数组内进行排序元素的下标变化范围。在每一遍加工结束，都需要用一个变量来存储这一遍加工中所找出的最小(或最大)的数据在数组内的下标。现有n个数据，分别存放在数组变量a(1 To n)当中，采用选择排序算法程序实现其从小到大的程序结构如下：实现该算法的程序段如下：For i1 To n1kiFor ji1 to n If 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是本遍加工最小数据元素的下标。这样，内循环一次完成之后，判断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)交换。经过n1遍之后，就能实现从小到大的排序。选择排序的关键在于最小值变量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+1Nk表示最小元素的位置k i,j i+1 比较比较ak和和aj如果如果ajak则令则令k=jj j+1NY交换交换ak和和aj开始开始j=7?简单选择排序算法的性能分析简单选择排序算法的性能分析移动次数：移动次数：最好情况（正序）：最好情况（正序）：0次次1 12 23 34 45 51 12 23 34 45 51 12 23 34 45 51 12 23 34 45 51 12 23 34 45 51 12 23 34 4最坏情况：最坏情况：3(n-1)次次简单选择排序算法的性能分析简单选择排序算法的性能分析移动次数：移动次数：最好情况（正序）：最好情况（正序）：0次次空间性能：空间性能：需一个辅助空间。需一个辅助空间。稳定性：稳定性：是一种稳定的排序算法。是一种稳定的排序算法。4 45 52 23 31 1 1 15 52 23 34 41 12 25 53 34 41 12 23 35 54 41 12 23 34 45 51 12 23 34 4比较次数：比较次数：)()1(21211nOnninni=-=-=）（简单选择排序的时间复杂度为简单选择排序的时间复杂度为O(n2)。1.用选择排序算法对一组学生的身高数据进行升序排序，已知第一遍排序结束后的数据序列为166、169、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某校通过政府招投标中心采购一套多媒体教学设备，有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、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.下列关于排序的说法，错误的是()A相对而言，选择排序算法的效率比冒泡排序算法高B冒泡排序算法和选择排序算法的都需要用到双循环结构C对于n个无序数据，不管是冒泡排序还是选择排序，都要经过n1遍加工D冒泡排序算法的程序实现一般要用到数组变量k，而选择排序则不需要C 上虞区小越中学信息技术组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 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.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,75,12,63,41,85 C.10,11,12,75,63,41,85 D.10,11,12,41,63,75,85B找出最小的小的不在前面就交换B1.选择排序的基本思想是在所有的记录中选出最小(大)的数据，把它与第一个数据交换，然后在其余的记录中再选出最小(大)的数据与第二个数据交换，依此类推，直至所有数据排序完成。有一组数据，顺序是“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.电视台为了统计参赛选手的短信支持度，来确定参赛选手的人气，对观众短信进行记录，针对这一情况编写程序过程中效率最高的算法是 （）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.3DCD