算法实例选择排序法课件

算法实例选择排序法临沭县实验中学算法实例选择排序法临沭县实验中学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次。1．选择排序算法的概念数组元素d(1)d(2)d(3)d(4第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次。第2遍：寻找从d(2)到d(4)范围内的最小数据d(k)，即显然，通过上述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个元素的数组，用选择算法进行排序时，比较次数与冒泡算法相同，但交换的次数比冒泡排序要少，因此它具有较高的效率。显然，通过上述3遍处理，数组d中最小、第2小、第3小的数据已2．选择排序算法的程序实现选择排序的程序同样采用双重For循环嵌套来实现，外循环来控制是第几遍加工，内循环用来控制数组内进行排序元素的下标变化范围。在每一遍加工结束，都需要用一个变量来存储这一遍加工中所找出的最小(或最大)的数据在数组内的下标。现有n个数据，分别存放在数组变量a(1Ton)当中，采用选择排序算法程序实现其从小到大的程序结构如下：实现该算法的程序段如下：Fori＝1Ton－1

k＝i

Forj＝i＋1tonIfa(j)<a(k)Thenk＝j

Nextj

Ifi<>kThent＝a(i)：a(i)＝a(k)：a(k)＝t

EndIfNexti2．选择排序算法的程序实现实现该算法的程序段如下：当外循环变量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的值在不断的发生变化，而每一遍加工，最多只交换一次数据，所以排序的效率比冒泡排序要高。当外循环变量i取1时，为第1遍加工，k＝1，先假设第1个数据选择排序方法1234567431891355743以7个元素为例说明选择排序位置1~位置7的元素初始排列如下所示选择排序方法1234567431891355743以7个元素7选择排序实例1234567431891355743第一趟：从7个元素中选出最小者，将其换入位置1，过程为：令min_elem表示最小元素（初值为位置1的元素），k为最小元素的位置序号（初值为1），逐一比较，找出最小元素及其位置位置6的元素最小交换1234567743913554343选择排序实例1234567431891355743第一趟：从81234567718913554343第二趟：从6个元素中选出最小者，将其换入位置2，过程为：令min_elem表示最小元素（初值为位置2的元素），k为最小元素的位置序号（初值为2），逐一比较，找出最小元素及其位置位置3的元素最小交换12345677918135543431234567718913554343第二趟：从6个元素中选91234567791813554343第三趟：从5个元素中选出最小者，将其换入位置3，过程为：令min_elem表示最小元素（初值为位置3的元素），k为最小元素的位置序号（初值为3），逐一比较，找出最小元素及其位置位置4的元素最小交换12345677913185543431234567791813554343第三趟：从5个元素中选101234567791318554343第四趟：从4个元素中选出最小者，将其换入位置4，过程为：令min_elem表示最小元素（初值为位置4的元素），k为最小元素的位置序号（初值为4），逐一比较，找出最小元素及其位置位置4的元素最小交换12345677913185543431234567791318554343第四趟：从4个元素中选111234567791318554343第五趟：从3个元素中选出最小者，将其换入位置5，过程为：令min_elem表示最小元素（初值为位置5的元素），k为最小元素的位置序号（初值为5），逐一比较，找出最小元素及其位置位置6的元素最小交换12345677913184355431234567791318554343第五趟：从3个元素中选121234567791318435543第六趟：从2个元素中选出最小者，将其换入位置6，过程为：令min_elem表示最小元素（初值为位置6的元素），k为最小元素的位置序号（初值为6），逐一比较，找出最小元素及其位置位置7的元素最小交换12345677913184343551234567791318435543第六趟：从2个元素中选131234567431891355743以7个元素为例，经过6趟选择，将元素排列有序排序12345677913184343551234567431891355743以7个元素为例，经过614选择排序流程图7个元素进行选择排序时，需要六趟，用i表示趟数i←1i<=6?结束Yi←i+1N进行第i趟选择排序开始选择排序流程图7个元素进行选择排序时，需要六趟，用i表示趟数157个元素进行选择排序时，需要六趟，用i表示趟数i←1i<=6?结束Yi←i+1Nk表示最小元素的位置k←i,j←i+1比较ak和aj如果aj<ak则令k=jj←j+1NY交换ak和aj开始j<=7?7个元素进行选择排序时，需要六趟，用i表示趟数i←1i<16简单选择排序算法的性能分析移动次数：最好情况（正序）：0次12345123451234512345123451234简单选择排序算法的性能分析移动次数：123451234512最坏情况：3(n-1)次简单选择排序算法的性能分析移动次数：最好情况（正序）：0次空间性能：需一个辅助空间。稳定性：是一种稳定的排序算法。45231152341253412354123451234比较次数：)()1(21211nOnninni=-=-å-=）（简单选择排序的时间复杂度为O(n2)。最坏情况：3(n-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、57D用选择排序算法对一组学生的身高数据进行升序排序，已知第一遍排3．某校通过政府招投标中心采购一套多媒体教学设备，有5家单位参加竞标，竞标价分别为18万、17万、23万、15万、16万元人民币。若采用选择排序算法对标价从大到小排序，需要进行数据互换的次数是 (

)A．1 B．3 C．4 D．5B4．圣诞节即将来临，某商场欲对仓库某货号商品进行补仓以应对即将举办的促销活动。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、433．某校通过政府招投标中心采购一套多媒体教学设备，有5家单位已知算法1与算法2都是排序算法，可能是冒泡排序或者选择排序，下面的表格反应的是在不同量的数据下，排序时进行数据交换的次数，分析算法1与算法2最有可能的排序算法分别是 (

)C排序的数据个数算法1的交换次数算法2的交换次数57311418228313537485284182171105291094A.冒泡排序冒泡排序 B．选择排序选择排序C．冒泡排序选择排序 D．选择排序冒泡排序下列关于排序的说法，错误的是 (

)A．相对而言，选择排序算法的效率比冒泡排序算法高B．冒泡排序算法和选择排序算法的都需要用到双循环结构C．对于n个无序数据，不管是冒泡排序还是选择排序，都要经过n－1遍加工D．冒泡排序算法的程序实现一般要用到数组变量k，而选择排序则不需要C已知算法1与算法2都是排序算法，可能是冒泡排序或者选择排序，上虞区小越中学信息技术组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.利用已学的选择排序算法，对初始数

【例1】在2015年秋季学校运动会上，男生第一组6位选手的110米栏成绩(单位：秒)分别是“18.4、17.3、16.9、18.8、18.1、16.7”，若使用选择排序法将该组的成绩按第一名、第二名、第三名……的顺序排序，则第一次交换数据后的顺序是(

)A.18.8

18.4

17.3

16.9

18.1

16.7B.16.7

17.3

16.9

18.8

18.1

18.4C.18.8

17.3

16.9

18.4

18.1

16.7D.16.7

18.4

17.3

16.9

18.8

18.1【例2】(浙江省2012年9月高考)实现某排序算法的部分VB程序如下：Fori=1To6

k=i

Forj=i+1To7

Ifa(j)＜a(k)Thenk=jNextjIfi＜＞kThen

t=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,85 B.10,11,75,12,63,41,85C.10,11,12,75,63,41,85 D.10,11,12,41,63,75,85B找出最小的小的不在前面就交换B【例1】在2015年秋季学校运动会上，男生第一组6位选手的1.选择排序的基本思想是在所有的记录中选出最小(大)的数