《高中信息技术 2、选择排序课件 浙教版.ppt》由会员分享，可在线阅读，更多相关《高中信息技术 2、选择排序课件 浙教版.ppt（12页珍藏版）》请在三一文库上搜索。
1、一、复习,1、冒泡排序思路:小元素从根部逐次向上浮动 2、冒泡排序程序设计要点：（1）基本形： For i = 1 To n-1 For j = n To i + 1 Step -1 If d(j) d(j - 1) Then t = p(i):p(i) = p(i - 1):p(i - 1) = t End If Next j Next i 规律：从根部向上冒泡，先冒出最小，连续双循环，双循环变量值对角加一，循环体数值交换,2、冒泡排序程序设计要点,（2）冒泡排序程序的小小变形： For j =2 to n For i = n To j Step -1 If p(i) p(i - 1) Th
2、en k = p(i): p(i)=p(i - 1):p(i - 1) = k Next i Next j 规律：对角相等、数值交换。 思考：排前10个应怎样改程序？,3、冒泡排序的循环比较次数及优缺点,（1）、n个数冒泡排序的循环比较次数是(n-1)+(n-2)+3+2+1 （2）、 n个数冒泡排序的交换次数不定 （3）、冒泡排序的优点：算法简洁明了、便于编程实现。 （4）、冒泡排序的缺点：交换次数频繁，程序执行时间长。,二、选择排序,选择排序（递增）的思路是 先找出n个数中最小的数据（下标跟踪），与数组第一个元素中的数据交换位置 再在余下的n-1个元素中继续找最小的元素，与第二个元素中的数
3、据交换位置 依次类推，直到排序结束。,对比:冒泡、选择排序的循环次数（即比较次数）相同，不同的是交换次数。,三、选择排序算法演示,第 1 遍 选择,j=2,k=1 For j=2 to 4 if d(k)d(j) then k=j Next j If k不等于1时，交换d(1)和d(k),交换d(1)与d(4),第2遍选择,j=3,k=2 For j=3 to 4 if d(k)d(j) then k=j Next j If k2 then 交换d(2)和d(k),第3遍选择,j=4,k=3 For j=4 to 4 if d(k)d(j) then k=j Next j If k3 then
4、 交换d(3)和d(k),四、算法分析,第1遍选择 ，j从2开始到4,k=1 For j=2 to 4 if d(k)d(j) then k=j Next j If k1，交换d(1)和d(k),k=2 For j=3 to 4 if d(k)d(j) then k=j Next j If k2 then 交换d(2)和d(k),第2遍选择 ，j从3开始到4,第3遍选择 ，j从4开始到4,k=3 For j=4 to 4 if d(k)d(j) then k=j Next j If k3 then 交换d(3)和d(k),用i来表示次数的变化,For i=1 to 3 K=i 因为循环变量的值
5、在 循环体内不能随意改变 For j=i +1 to 4,五、程序实现,For i = 1 To n- 1 选择第i个作为最小的数 k = i For j = i + 1 To n 如果找到更小的，用k记住它的编号 If d(k) d(j) Then k = j 注意：d(k)与d(j)比较 Next j,特点：平行加一，下标跟随，数值交换，小数上冒。,选择排序基本形,If k i Then 如果最小的数所在的位置不是i，则交换 t = d(i) d(i) = d(k) d(k) =t 注意： d(k)与d(i)交换 End If Next i,六、选择排序和冒泡排序的比较,以n个数据为例:(
6、运行比较程序),冒泡：从根部向上冒泡，逐个交换，先冒出最小，升序排序。 选择：从顶部向下找较小数的下标，找到最小的数再交换至前，升序排序。 选择排序是冒泡排序的改进。,七、选择排序的变形,For i= n To 2 Step -1 Max = i 选择第i个作为最大的数 For j = 1 To i-1 如果找到更大的，用max记住它的编号 If d(Max) i Then 如果最大的数所在的位置不是i，则交换 k = d(i) d(i) = d(Max) d(Max) = k d(max)与d(i)交换 End If Next I,特点：对角减一，下标跟随，数值交换，大数下沉。,八、复习题解,高考倒计时 P70例4、 P74例11、 P77第5题,