高中信息技术-2、选择排序课件-浙教版.ppt

《高中信息技术-2、选择排序课件-浙教版.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、复习1、冒泡排序思路:小元素从根部逐次向上浮动2、冒泡排序程序设计要点：（1）基本形：Fori=1Ton-1Forj=nToi+1Step-1Ifd(j)

2、前10个应怎样改程序？3、冒泡排序的循环比较次数及优缺点（1）、n个数冒泡排序的循环比较次数是(n-1)+(n-2)+…+3+2+1（2）、n个数冒泡排序的交换次数不定（3）、冒泡排序的优点：算法简洁明了、便于编程实现。（4）、冒泡排序的缺点：交换次数频繁，程序执行时间长。二、选择排序选择排序（递增）的思路是先找出n个数中最小的数据（下标跟踪），与数组第一个元素中的数据交换位置再在余下的n-1个元素中继续找最小的元素，与第二个元素中的数据交换位置依次类推，直到排序结束。对比:冒泡、选择排序的循环次数（即比较次数）相同，不同的是交换次数。三、选择排序算法演示第1遍选择27363218d

3、(1)d(2)d(3)d(4)j=2k=127363218j=3k=127363218j=4k=j18363227k=1Forj=2to4ifd(k)>d(j)thenk=jNextjIfk不等于1时，交换d(1)和d(k)交换d(1)与d(4)第2遍选择18363227d(1)d(2)d(3)d(4)j=3k=218363227j=3k=j18363227j=4k=jj=418363227k=j18273236k=2Forj=3to4ifd(k)>d(j)thenk=jNextjIfk<>2then交换d(2)和d(k)第3遍选择18273236d(1)d(2)d(3)d(4)j=

4、4k=3k=3Forj=4to4ifd(k)>d(j)thenk=jNextjIfk<>3then交换d(3)和d(k)四、算法分析第1遍选择，j从2开始到4k=1Forj=2to4ifd(k)>d(j)thenk=jNextjIfk<>1，交换d(1)和d(k)k=2Forj=3to4ifd(k)>d(j)thenk=jNextjIfk<>2then交换d(2)和d(k)第2遍选择，j从3开始到4第3遍选择，j从4开始到4k=3Forj=4to4ifd(k)>d(j)thenk=jNextjIfk<>3then交换d(3)和d(k)用i来表示次数的变化Fori=1to3K=i‘因为

5、循环变量的值在循环体内不能随意改变Forj=i+1to4五、程序实现Fori=1Ton-1‘选择第i个作为最小的数k=iForj=i+1Ton'如果找到更小的，用k记住它的编号Ifd(k)>d(j)Thenk=j‘注意：d(k)与d(j)比较Nextj特点：平行加一，下标跟随，数值交换，小数上冒。——选择排序基本形Ifk<>iThen'如果最小的数所在的位置不是i，则交换t=d(i)d(i)=d(k)d(k)=t'注意：d(k)与d(i)交换EndIfNexti六、选择排序和冒泡排序的比较交换次数循环比较次数冒泡<=(n-1)*n/2(n-1)+…+3+2+1选择<=n-1(n-1)

6、+…+3+2+1以n个数据为例:(运行比较程序)冒泡：从根部向上冒泡，逐个交换，先冒出最小，升序排序。选择：从顶部向下找较小数的下标，找到最小的数再交换至前，升序排序。选择排序是冒泡排序的改进。七、选择排序的变形Fori=nTo2Step-1Max=i‘选择第i个作为最大的数Forj=1Toi-1‘如果找到更大的，用max记住它的编号Ifd(Max)iThen‘如果最大的数所在的位置不是i，则交换k=d(i)d(i)=d(Max)d(Max)=k‘d(max)与d(i)交换EndIfNextI特点：对角减

7、一，下标跟随，数值交换，大数下沉。八、复习题解高考倒计时P70例4、P74例11、P77第5题