- 168.00 KB
- 2022-08-10 发布
- 1、本文档由用户上传，淘文库整理发布，可阅读全部内容。
- 2、本文档内容版权归属内容提供方，所产生的收益全部归内容提供方所有。如果您对本文有版权争议，请立即联系网站客服。
- 3、本文档由用户上传，本站不保证质量和数量令人满意，可能有诸多瑕疵，付费之前，请仔细阅读内容确认后进行付费下载。
- 网站客服QQ：403074932
一、复习1、冒泡排序思路:小元素从根部逐次向上浮动2、冒泡排序程序设计要点：（1）基本形：Fori=1Ton-1Forj=nToi+1Step-1Ifd(j)d(j)thenk=jNextjIfk不等于1时，交换d(1)和d(k)交换d(1)与d(4)\n第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)\n第3遍选择18273236d(1)d(2)d(3)d(4)j=4k=3k=3Forj=4to4ifd(k)>d(j)thenk=jNextjIfk<>3then交换d(3)和d(k)\n四、算法分析第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‘因为循环变量的值在循环体内不能随意改变Forj=i+1to4\n五、程序实现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六、选择排序和冒泡排序的比较交换次数循环比较次数冒泡<=(n-1)*n/2(n-1)+…+3+2+1选择<=n-1(n-1)+…+3+2+1以n个数据为例:(运行比较程序)冒泡：从根部向上冒泡，逐个交换，先冒出最小，升序排序。选择：从顶部向下找较小数的下标，找到最小的数再交换至前，升序排序。选择排序是冒泡排序的改进。\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特点：对角减一，下标跟随，数值交换，大数下沉。\n八、复习题解高考倒计时P70例4、P74例11、P77第5题
微信/支付宝扫码支付下载