算法实例选择排序法ppt课件.ppt

算法实例,选择排序法,临沭县实验中学,1选择排序算法的概念选择排序算法是对冒泡排序算法的改进。这种方法是对参加排序数组的所有元素中找出最小(或最大)数据的元素，使它与第一个元素中数据相互交换位置。然后在余下的元素中找出最小(或最大)的数据的元素，与第二个元素中的数据交换位置。以此类推，直到所有元素成为一个有序的序列。某数组d共有4个元素构成，每个元素的值如下表所示：,用选择排序法按升序进行排序的过程，从数组第一个元素开始起：第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)k 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的值在不断的发生变化，而每一遍加工，最多只交换一次数据，所以排序的效率比冒泡排序要高。,选择排序方法,43,18,9,13,55,7,43,以7个元素为例说明选择排序位置1位置7的元素初始排列如下所示,选择排序实例,43,18,9,13,55,7,43,第一趟：从7个元素中选出最小者，将其换入位置1，过程为：令min_elem表示最小元素（初值为位置1的元素），k为最小元素的位置序号（初值为1），逐一比较，找出最小元素及其位置,位置6的元素最小交换,7,18,9,13,55,43,43,第二趟：从6个元素中选出最小者，将其换入位置2，过程为：令min_elem表示最小元素（初值为位置2的元素），k为最小元素的位置序号（初值为2），逐一比较，找出最小元素及其位置,位置3的元素最小交换,7,9,18,13,55,43,43,第三趟：从5个元素中选出最小者，将其换入位置3，过程为：令min_elem表示最小元素（初值为位置3的元素），k为最小元素的位置序号（初值为3），逐一比较，找出最小元素及其位置,位置4的元素最小交换,7,9,13,18,55,43,43,第四趟：从4个元素中选出最小者，将其换入位置4，过程为：令min_elem表示最小元素（初值为位置4的元素），k为最小元素的位置序号（初值为4），逐一比较，找出最小元素及其位置,位置4的元素最小交换,7,9,13,18,55,43,43,第五趟：从3个元素中选出最小者，将其换入位置5，过程为：令min_elem表示最小元素（初值为位置5的元素），k为最小元素的位置序号（初值为5），逐一比较，找出最小元素及其位置,位置6的元素最小交换,7,9,13,18,43,55,43,第六趟：从2个元素中选出最小者，将其换入位置6，过程为：令min_elem表示最小元素（初值为位置6的元素），k为最小元素的位置序号（初值为6），逐一比较，找出最小元素及其位置,位置7的元素最小交换,43,18,9,13,55,7,43,以7个元素为例，经过6趟选择，将元素排列有序,排序,选择排序流程图,7个元素进行选择排序时，需要六趟，用i表示趟数,i 1,i=6?,结束,Y,i i+1,N,进行第i趟选择排序,开始,7个元素进行选择排序时，需要六趟，用i表示趟数,i 1,i=6?,结束,Y,i i+1,N,k表示最小元素的位置,开始,j=7?,简单选择排序算法的性能分析,移动次数：最好情况（正序）：0次,1,2,3,4,最坏情况：3(n-1)次,简单选择排序算法的性能分析,移动次数：最好情况（正序）：0次,空间性能：需一个辅助空间。稳定性：是一种稳定的排序算法。,1,2,3,4,比较次数：,简单选择排序的时间复杂度为O(n2)。,用选择排序算法对一组学生的身高数据进行升序排序，已知第一遍排序结束后的数据序列为166、169、177、175、172，则下列选项中可能是原始数据序列的是 ()A175、177、169、166、172 B177、169、166、175、172C166、177、169、175、172 D166、169、172、175、177,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,3某校通过政府招投标中心采购一套多媒体教学设备，有5家单位参加竞标，竞标价分别为18万、17万、23万、15万、16万元人民币。若采用选择排序算法对标价从大到小排序，需要进行数据互换的次数是 ()A1 B3C4 D5,B,4圣诞节即将来临，某商场欲对仓库某货号商品进行补仓以应对即将举办的促销活动。6家供货商给出的报价分别为48、43、60、46、58、55，若采用选择排序算法对其进行从大到小排序，则第三遍的排序结果是(),C,A.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、43,已知算法1与算法2都是排序算法，可能是冒泡排序或者选择排序，下面的表格反应的是在不同量的数据下，排序时进行数据交换的次数，分析算法1与算法2最有可能的排序算法分别是 (),C,A.冒泡排序冒泡排序 B选择排序选择排序C冒泡排序选择排序 D选择排序冒泡排序,下列关于排序的说法，错误的是 ()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 97,2.请完善选择排序算法的通用流程图(从小到大的顺序)。,【例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, 85,B,找出最小的,小的不在前面就交换,B,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.电视台为了统计参赛选手的短信支持度，来确定参赛选手的人气，对观众短信进行记录，针对这一情况编写程序过程中效率最高的算法是 （） 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,D,C,D,