《选择排序算法（第一课时）.ppt》由会员分享，可在线阅读，更多相关《选择排序算法（第一课时）.ppt（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2.3.3选择排序选择排序算法算法第第一课时一课时一、冒泡导入思考思考1：将108、120、96、75这组数据按从小到大从小到大进行冒泡排序 1.需要进行几趟冒泡排序，每趟的排序结果分别是什么？2.整个排序过程中进行了几次数据比较数据比较？几次数据交换数据交换？3.能否减少交换次数？二、选择排序概念选择排序是在参与排序的所有数组元素数组元素中找出最小最小(或或最大最大)数据的元素数据的元素，使它与第一个元素中的数据第一个元素中的数据相互交换交换，然后再在余下余下的元素中找出最小(或最大)数据的元素，与第二个元素中的数据相互交换位置，以此类推，直到所有元素成为一个有序的序列。随堂练习随堂练习11
2、 1、某数组、某数组1010个元素，依次为个元素，依次为2 2、2020、1212、1515、1313、5050、5555、6060、8080、3030，若采用选择排序算法进行降序排序，则第，若采用选择排序算法进行降序排序，则第5 5遍排序完遍排序完成时的数据序列为成时的数据序列为 （）B.80B.80、6060、5555、5050、3030、2020、1515、1313、1212、2 2 A.80A.80、6060、5555、5050、3030、1313、1515、2020、2 2、1212C.80C.80、6060、5555、5050、3030、1515、2020、1212、2 2、131
3、3D.D.8080、6060、5555、5050、3030、1515、1212、2020、2 2、1313 D D2 2、用选择排序算法对一组学生的身高数据进行升序排序，已知第、用选择排序算法对一组学生的身高数据进行升序排序，已知第一遍排序结束后的数据序列为一遍排序结束后的数据序列为165165、168168、178178、175175、171171，则下列，则下列选项中可能是原始数据序列的是：选项中可能是原始数据序列的是：（）A.A.175175、178178、168168、165165、171 B.171 B.165165、178178、168168、175175、171 171 C.C.
4、178178、168168、165165、175175、171 171 D.165D.165、168168、171171、175175、178 178 C C三、选择排序流程图回顾表示算法的三种方法：回顾表示算法的三种方法：自然语言自然语言流程图流程图程序语言程序语言四、选择排序流程图开始开始选择排序选择排序结束结束流程图一：流程图一：问题一：问题一：选择排序是怎么一步步进行？选择排序是怎么一步步进行？讨论一讨论一:选择排序，每一趟排序可以分为几步？选择排序，每一趟排序可以分为几步？第一步，第一步，找最小数找最小数；第二步，第二步，交换位置交换位置。第一趟第二趟第三趟三、选择排序流程图开始开始
5、找最小数找最小数结束结束交交换换流程图二：流程图二：问题二：问题二：“找最小数找最小数”和和“交换位置交换位置”要重复几次？要重复几次？开始开始选择排序选择排序结束结束流程图一：流程图一：讨论二：讨论二：如果总共如果总共5个数，重复几次？个数，重复几次？如果总共如果总共N个数，重复个数，重复几次？几次？循环循环第一趟第二趟第三趟三、选择排序流程图开始开始找最小数找最小数交交换换3次次结束结束流程图三：流程图三：开始开始找最小数找最小数结束结束交交换换流程图二：流程图二：三、选择排序流程图改进后的流程图三：改进后的流程图三：开始开始找最小数找最小数结束结束交交换换i4？i1ii+1YN问题三：问
6、题三：怎么样在一组数中找到最小数据呢？怎么样在一组数中找到最小数据呢？i来记录循环次数循环次数，即选择排序所需趟数i=1，进入第一次循环，找到最小数75，交换到第一个位置，i自己加一个。i=2，进入第二次循环，找到最小数96，交换到第一个位置，i自己加一个。i=3，进入第三次循环，找到最小数108，交换到第一个位置，i自己加一个。i=4，跳出循环。三、选择排序流程图第几个数第几个数比较大小比较大小关系关系最小数最小数d(1)=108d(1)k1d(k)=108，k=1d(2)=120d(k)d(3)kd(4)k4d(k)=75，k=4表格介绍，k表示最小数位置，d(k)表示最小数1081209
7、6751234三、选择排序流程图问题四：问题四：数据交换是不是数据交换是不是每每趟都要进行？趟都要进行？流程图四（找最小数）流程图四（找最小数）流程图三：流程图三：开始开始找最小数找最小数结束结束交交换换i4？i1ii+1YN开始开始结束结束i 4?i 1输出输出YNN交交换换ii+1nk j j+1j=?k ,j d(j)d(k)?YYN124jii+1nNn三、选择排序流程图实例一：实例一：表格介绍，i表示第几趟选择排序，k表示最小数的位置。第几次第几次i最小数应放第几个位置最小数应放第几个位置最小数实际位置最小数实际位置ki,k关系关系是否交换是否交换第1趟最小数应放第1个位置第2趟最小
8、数应放第2个位置第3趟最小数应放第3个位置第4个第3个1434第4个23交换交换交换第一趟第二趟第三趟三、选择排序流程图实例实例二二：7510896120123475108961201234第一次第一次7510896120123475961081201234第二次第二次7596108120123475961081201234第三次第三次数据数据是否交换用什么结构表达是否交换用什么结构表达？选择选择表格介绍，i表示第几趟选择排序，k表示最小数的位置。第几次第几次i最小数应放第几个位置最小数应放第几个位置最小数实际位置最小数实际位置ki,k关系关系是否交换是否交换第1趟最小数应放第1个位置第2趟最
9、小数应放第2个位置第3趟最小数应放第3个位置第1个第3个1=13=3第3个23不用交换交换不用交换第一趟第二趟第三趟三、选择排序流程图开始开始k jj j+1j=n?k i，j i+1d(j)d(k)?结束结束i i+1in?i 1输出输出YNYNYN流程图五（数据交换）流程图五（数据交换）t=d(i):d(i)=d(k):d(k)=ti k?YNi i表示第几趟排序，表示第几趟排序，k表示最小数位置，表示最小数位置，d(k)表示最小数，表示最小数，j表示下一个数位置表示下一个数位置找找最最小小数数交交换换位位置置随堂练习随堂练习22 2、有、有5 5位运动员位运动员100100米成绩依次为米
10、成绩依次为13.813.8，12.512.5，13.013.0，13.213.2，13.413.4，用选择排序法，用选择排序法对数据五个数据从大到小排序，共需经过（对数据五个数据从大到小排序，共需经过（）次数据对调。）次数据对调。A.10 B.4 C.3 D.2 A.10 B.4 C.3 D.2D D1 1、某食品连锁店、某食品连锁店5 5位顾客贵宾消费卡的积分依次为位顾客贵宾消费卡的积分依次为900900、512512、613613、700700、810810，若采用选择排序算法对其进行从小到大排序，如下表，第二，若采用选择排序算法对其进行从小到大排序，如下表，第二趟的排序结果是（趟的排序结
11、果是（）A A512512 613613 700700 900900 810810 B B512512 613613 900900 700700 810810C C512512 900 900 700 700 810 613 810 613 D D512512 810810 613613 900900 700700原始数据原始数据900900 512512613613700700810810第一趟第一趟512512900900613613700700810810第二趟第二趟第三趟第三趟512512613613700700900900810810第四趟第四趟512512613613700700810810900900B B四、选择排序与冒泡排序算法效率对比冒泡排序冒泡排序选择排序选择排序比较次数比较次数交换次数交换次数n（n-1）/2n（n-1）/20,n（n-1）/20,n-1五、总结 l选择排序的概念选择排序的概念l选择排序的流程图选择排序的流程图l冒泡选择与选择排序算法效率对比冒泡选择与选择排序算法效率对比谢谢！