《选择排序 (3).ppt》由会员分享，可在线阅读，更多相关《选择排序 (3).ppt（30页珍藏版）》请在三一文库上搜索。
1、选择排序算法设计,主讲：灵溪二高 李泽满,冒泡排序,冒泡算法是通过两两比较，不断交换,逐个推进的方式，来进行排序的。 一次遍历，得到一个最值。,冒泡排序,用数组来存储一系列同类型的数据, 然后调整数组中的元素 例如: dim d(1 to 4) as integer 定义一个数组变量d,第1次冒泡排序时 j 从 4 开始到2,P31,第2次冒泡排序时 j 从 4 开始到3,第3次冒泡排序时 j 从 4 开始到4,a(1） a(2） a(3） a(4） a(5） a(6）,按从低到高的顺序重新排队,擂主,方法1：用打擂法,擂主,擂主,方法1：用打擂法(比完),擂主,晋中市高中信息技术网络选修课,
2、排序前奏：求最大值,问题描述： 对于给定的任意一组变量值， 求出最大值。,选择排序,选择排序（递增）的方法是 找出数组元素中最小(大)的数据，使它与第一个元素中的数据交换位置 在余下的元素中继续找最小(大)的元素，与第二个元素中的数据交换位置 ,选择排序算法的思路,问题：,下面是8位同学的“体质健康综合评价”分数，请编写程序把它们由小到大排成顺序：86.5，77.5，87，68.9，89.6，77.2，79.7，71.1。,（1）分析问题,第一次选择、对调后的排列： 68.9，77.5，87，86.5，89.6，77.2，79.7，71.1,第二次选择、对调后的排列： 68.9，71.1，87
3、，86.5，89.6，77.2，79.7，77.5,不断重复这个过程，可以实现对数据进行排序的目的。因为排序的过程是不断在剩余的数据中选择最小的，所以把这种方法称为选择排序法。,选择排序算法的思路,（2）设计算法,选择排序算法的思路： 首先在全部数据中找出最小的，然后在余下的数据中继续找出最小的，不断重复这个过程，直到只剩下一个数据时为止。,N个数据的选择排序法示意图如下：,上面的示意图可以描述为用一个循环结构来完成：让I从1到N-1循环，在第I到第N数据中选择最小的，把它与排在第I位置的数据对调。,选择排序过程,第 1 遍 选择,j=2,Min=1 For j=2 to 4 if d(min
4、)d(j) then min=j Next j If min不等于1时，交换d(1)和d(min),第2遍选择,j=3,Min=2 For j=3 to 4 if d(min)d(j) then min=j Next j If min2 then 交换d(2)和d(min),第3遍选择,j=4,Min=3 For j=4 to 4 if d(min)d(j) then min=j Next j If min3 then 交换d(3)和d(min),分析,第1遍选择 ，j从2开始到4,Min=1 For j=2 to 4 if d(min)d(j) then min=j Next j If mi
5、n1，交换d(1)和d(min),Min=2 For j=3 to 4 if d(min)d(j) then min=j Next j If min2 then 交换d(2)和d(min),第2遍选择 ，j从3开始到4,第3遍选择 ，j从4开始到4,Min=3 For j=4 to 4 if d(min)d(j) then min=j Next j If min3 then 交换d(3)和d(min),用i来表示次数的变化,程序实现,For i = 1 To n - 1 选择第i个最小的数 Min=i For j=i+1 To n 如果找到更小的，用min记住它的编号 If d(Min) d(
6、j) Then Min=j Next j If Min i Then 如果最小的数所在的位置不是i，则交换 temp=d(i) :d(i)=d(Min):d(Min)=temp End If Next i,数组元素的个数,冒泡、选择排序算法比较,异同点 哪个算法更高效？ 小提示：排序算法最费时的是什么？ 一是两两比较 二是两两交换， 交换要比比较费时多了。,考点狙击：有可能考什么，怎么考,1、程序实现中几个变量的作用 2、第i趟排序的结果（通常数组元素5-8个，i=4，经常结合实际背景) 3、对整个排序过程的理解（包括比较次数、遍历次数、程序填空等） 4、对排序思想的理解（辨别排序是选择还是，
7、冒泡） 5、结合流程图或实际背景补充程序或程序改错,知识拓展,目前已有上百种排序算法，如插入排序、快排、堆排序、归并排序、希尔排序等等。其中插入排序、冒泡排序、选择排序被称为简单排序，其他很多算法可以说是几种算法的优化方案。 虽然排序的算法很多，但至今未有一个最理想的尽如人意的方法，更优秀的排序算法还等着各位同学去设计,概述,为什么要排序？,如何排序？,排序：将一组杂乱无章的数据变成一组有规律的数据。（递增或递减）,排序的方法有许多种，本节学习选择排序算法和插入排序算法。,排序算法：把一组数据整理为顺序的算法。一般，把从小到大称为顺序，而从大到小称为逆序。,选择排序算法,选择排序算法的思路,1
8、,选择排序编写程序的实践,2,4,N个数选择法升序排序的算法实现,N个数选择法升序排序： For i= 1 to n-1 1. 从第i个到第n个中， 找最小的数的位置k 2. 交换 Next i,第 i 步的操作： 从第i个到第n个中， 找最小的数的位置， 与第 i 个位置的数交换,各个击破,数据存储 一组同类型的数据可以用数组存储 比如，我们可以定义数组： dim data（1 to n） as integer 将数据存储到 data（1）、data（2） data(n) 在第i个到第n个中，找最小数的位置k k = i for j= i+1 to n if data(j) data(k)
9、then k = j next j 第k个位置和第i个位置的数据交换 temp = data(i) data(i) = data(k) data(k) = temp,算法实现,N个数选择法升序排序： For i= 1 to n-1 1. 从第i个到第n个中，找最小的数的位置k 2. 交换位置k和位置i上的数据 Next i,k = i for j= i+1 to n if data(j) data(k) then k = j next j,If k i then End if,temp = data(i) data(i)=data(k) data(k)=temp,选择排序算法的思路,假设N个数
10、据都存放在数组D中，在第I到第N数据中选择最小的，并记录位置（数组下标）的算法如下：,假设最小数据MIN=D(I),位置记录M=1;,令J=I+1;,如果D(J)MIN，那么让MIN=D(J):M=j;,当JN时令J增加1，返回 。,选择排序算法的思路,经过多次反复求精的步骤，选择排序算法比较完整的描述如下：,输入N的值并把N个数据读入数组D中； 令I=1; MIN=D(I),M=I; 令J=I+1; 如果D(J)MIN，那么让MIN=D(J):M=j; 当JN时令J增加1，返回; 交换I、M单元的值，即 K=D(I):D(I)=MIN:D(M)=K; 当IN-1时令I增加1，返回； 把排序后
11、的数组D中的数据输出到窗体； 结束。,选择排序算法的思路,用InputBox函数完成数据输入。按上述流程写出如下程序：,（3）编写程序,Private Sub Form_Click() Dim D(100) As Single N=Val(InputBox(“请输入数据的总数量”) For i=1 To N D(i)=Val(InputBox(“请输入第“ & i & “个数据”) Next i For i=1 To N-1 Min=D(i):M=i For j=i+1 To N If D(j)Min Then Min=D(j):M=j Next j k=D(i):D(i)=Min:D(M)=k Next i For i=1 To N Print D(i),:If i Mode 5 =0 Then Print Next i End Sub,（4）调试程序,选择排序编写程序的实践,问题,在大型国际运动会开幕式上，各国运动员出场的顺序一般都是按国家的英文名的字母顺序排列的。陈婷同学专门搜集了一些国家的名字存在文件“countries.txt”中，请你把这些国家名读出来，然后排好顺序后输出。,Thank You !,