选择排序 (3).ppt

《选择排序 (3).ppt》由会员分享，可在线阅读，更多相关《选择排序 (3).ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、选择排序算法设计选择排序算法设计主讲：灵溪二高 李泽满冒泡排序v冒泡算法是通过两两比较，不断交换,逐个推进的方式，来进行排序的。v一次遍历，得到一个最值。冒泡排序v 用数组来存储一系列同类型的数据, 然后调整数组中的元素v 例如: dim d(1 to 4) as integer 定义一个数组变量d27363218d (1) d (2) d (3) d (4) jj-127361832jj-127183632jj-118273632第1次冒泡排序时 j 从 4 开始到2P31第2次冒泡排序时 j 从 4 开始到318273632d (1) d (2) d (3) d (4) jj-118273

2、236jj-118273236第3次冒泡排序时 j 从 4 开始到418273236d (1) d (2) d (3) d (4) jj-118273236 a(1） a(2） a(3） a(4） a(5） a(6）按从低到高的顺序重新排队擂主擂主方法方法1 1：用打擂法：用打擂法擂主擂主擂主擂主方法方法1 1：用打擂法：用打擂法( (比完比完) )擂主擂主晋中市高中信息技术网络选修课排序前奏：求最大值问题描述：问题描述：对于给定的任意一组变量值，求出最大值。选择排序v选择排序（递增）的方法是 找出数组元素中最小(大)的数据，使它与第一个元素中的数据交换位置 在余下的元素中继续找最小(大)的元

3、素，与第二个元素中的数据交换位置 选择排序算法的思路问题：问题：下面是8位同学的“体质健康综合评价”分数，请编写程序把它们由小到大排成顺序：86.5，77.5，87，68.9，89.6，77.2，79.7，71.1。（1 1）分析问题）分析问题第一次选择、对调后的排列：68.9，77.5，87，86.5，89.6，77.2，79.7，71.1第二次选择、对调后的排列：68.9，71.1，87，86.5，89.6，77.2，79.7，77.5不断重复这个过程，可以实现对数据进行排序的目的。因为排序的过程是不断在剩余的数据中选择最小的，所以把这种方法称为选择排序法。选择排序算法的思路（2 2）设计

4、算法）设计算法选择排序算法的思路：首先在全部数据中找出最小的，然后在余下的数据中继续找出最小的，不断重复这个过程，直到只剩下一个数据时为止。N个数据的选择排序法示意图如下：在N个数据中选择最小的，把它与第1个位置的数据对调在剩下的N-1个数据中选择最小的，把它与第2个位置的数据对调在剩下的N-2个数据中选择最小的，把它与第3个位置的数据对调在剩下的2个数据中选择最小的，把它与第N-1个位置的数据对调上面的示意图可以描述为用一个循环结构来完成：让I从1到N-1循环，在第I到第N数据中选择最小的，把它与排在第I位置的数据对调。选择排序过程v第 1 遍 选择27363218d (1) d (2) d

5、 (3) d (4) j=2Min=1 27363218j=3Min=1 27363218j=4Min=j 18363227Min=1For j=2 to 4 if d(min)d(j) then min=jNext jIf min不等于1时，交换d(1)和d(min)第2遍选择18363227d (1) d (2) d (3) d (4) j=3Min=2 18363227j=3Min=j 18363227j=4Min=j j=418363227Min=j 18273236Min=2For j=3 to 4 if d(min)d(j) then min=jNext jIf min2 then

6、 交换d(2)和d(min) 第3遍选择18273236d (1) d (2) d (3) d (4) j=4Min=3 Min=3For j=4 to 4 if d(min)d(j) then min=jNext jIf min3 then 交换d(3)和d(min) 分析v第1遍选择 ，j从2开始到4Min=1For j=2 to 4 if d(min)d(j) then min=jNext jIf min1，交换d(1)和d(min)Min=2For j=3 to 4 if d(min)d(j) then min=jNext jIf min2 then 交换d(2)和d(min)n第2遍

7、选择 ，j从3开始到4n第3遍选择 ，j从4开始到4Min=3For j=4 to 4 if d(min)d(j) then min=jNext jIf 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(j) Then Min=j Next j If Min i Then 如果最小的数所在的位置不是如果最小的数所在的位置不是i，则交换，则交换 temp=d(i) :d(i)=d(Min):d(

8、Min)=temp End IfNext i数组元素的数组元素的个数个数冒泡、选择排序算法比较v异同点v哪个算法更高效？ 小提示：排序算法最费时的是什么？ 一是两两比较 二是两两交换， 交换要比比较费时多了。考点狙击：有可能考什么，怎么考v 1、程序实现中几个变量的作用v 2、第i趟排序的结果（通常数组元素5-8个，i=4，经常结合实际背景)v 3、对整个排序过程的理解（包括比较次数、遍历次数、程序填空等）v 4、对排序思想的理解（辨别排序是选择还是，冒泡）v 5、结合流程图或实际背景补充程序或程序改错知识拓展v目前已有上百种排序算法，如插入排序、快排、堆排序、归并排序、希尔排序等等。其中插入

9、排序、冒泡排序、选择排序被称为简单排序，其他很多算法可以说是几种算法的优化方案。v虽然排序的算法很多，但至今未有一个最理想的尽如人意的方法，更优秀的排序算法还等着各位同学去设计概述为什么要排序？如何排序？排序：将一组杂乱无章的数据变成一组有规律的数据。（递增或递减）排序的方法有许多种，本节学习选择排序算法和插入排序算法。排序算法：把一组数据整理为顺序的算法。一般，把从小到大称为顺序，而从大到小称为逆序。选择排序算法选择排序算法的思路1选择排序编写程序的实践24N个数选择法升序排序的算法实现N N个数选择法升序排序：个数选择法升序排序： For i= 1 to n-1 For i= 1 to n

10、-1 1. 1. 从第从第i i个到第个到第n n个中，个中， 找最小的数的位置找最小的数的位置k k 2. 2. 交换交换 Next i Next i第第 i i 步的操作：步的操作： 从第从第i i个到第个到第n n个中，个中， 找最小的数的位置，找最小的数的位置， 与第与第 i i 个位置的数交换个位置的数交换各个击破1. 数据存储 一组同类型的数据可以用数组存储 比如，我们可以定义数组： dim data（1 to n） as integer 将数据存储到 data（1）、data（2） data(n)2. 在第i个到第n个中，找最小数的位置kk = ifor j= i+1 to n

11、if data(j) data(k) then k = jnext j 3. 第k个位置和第i个位置的数据交换temp = data(i)data(i) = data(k)data(k) = temp算法实现N N个数选择法升序排序：个数选择法升序排序： For i= 1 to n-1 For i= 1 to n-1 1. 1. 从第从第i i个到第个到第n n个中，个中，找最小的数的位置找最小的数的位置k k 2. 2. 交换位置交换位置k k和位置和位置i i上的数据上的数据 Next i Next ik = ifor j= i+1 to n if data(j) data(k) then

12、 k = jnext j If k i thenEnd iftemp = data(i)data(i)=data(k)data(k)=temp选择排序算法的思路假设N个数据都存放在数组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

13、=j;当JN时令J增加1，返回;交换I、M单元的值，即K=D(I):D(I)=MIN:D(M)=K;当IN-1时令I增加1，返回；把排序后的数组D中的数据输出到窗体；结束。选择排序算法的思路用InputBox函数完成数据输入。按上述流程写出如下程序：（3 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 iEnd Sub（4 4）调试程序）调试程序选择排序编写程序的实践问题问题 在大型国际运动会开幕式上，各国运动员出场的顺序一般都是按国家的英文名的字母顺序排列的。陈婷同学专门搜集了一些国家的名字存在文件“countries.txt”中，请你把这些国家名读出来，然后排好顺序后输出。