2018浙江高中信息技术排序和查找算法复习资料总结材料

1、实用文档2018年浙江省高中信息技术选考排序和查找算法复习资料、排序算法1.选择排序(1)概念：找出数组元素中最小(大)的数据，使它与第一个元素中的数据交换 位置;在余下的元素中继续找最小(大)的元素，与第二个元素中的数据交换位置(2)比较的次数：n*(n-1)/2 交换的次数：小于 n-1趟数：n-1dddddr 1191151151151152302302182162183ia318330319319422422422422422515519519530530(3)算法：将数组内的数据从小到大排序for i=1 to n-1min=ifor j=i+1 to nif d(j)<d(m

2、in) then min=jnext jif min<>i then k=d(min) d(min)=d(i) d(i)=kend ifnext i(4)例题：例题1:使用选择排序的方法对数据8、6、1、9、4从大到小排序，需要进行数据比较、数据互换白次数分别是( D )A、4,5B、10,2C、3,3D、10,4例题2:小陈设计了一个带密码的趣味“4+1”小游戏，小陈告诉大家，该密码可以通过以下方法破解：将一组顺序是“3、2、8、5、9”的数码，在用选择排序法将这组数码从大到小的排序过程中，进行两次数据交换，即得。则该密码可能是(D )A、98523B、92853C、98523D

3、> 98253例题3:以下表格中的数据为2009年快乐女生十进七淘汰赛的选手信息。某同学设计了一个Visual Basic程序用于选出晋及前七名的选手信息。程序界面如下 图所示，单击“十进七晋级名单”，在list2里显示晋及前七名的选手信息。阅读、完善以下程序，并上机验证。完成下面问题：Dim xs(1 To 10) As StringDim df(1 To 10) As IntegePrivate Sub Form_Load()Dim i As Integerxs(1)="黄 英"：df(1) = 88xs(2)="江映蓉 "：df(2) = 8

4、7xs(3)="李霄云 "：df(3) = 72xs(4)="刘惜君"：df(4) = 77xs(5)="谈莉娜" ：d(5) = 61xs(6)="郁可唯 "：df(6) = 81xs(7)="潘虹越 "：df(7) = 48xs(8)="潘 辰 "：df(8) = 38xs(9)="李媛希 "：df(9) = 36xs(10)="曾轶可 " :df(10) = 51 Fori = 1 To 10选手(XS)得分(df)黄英88江映暮

5、87李霄云72刘惜君77谈莉娜61郁可唯S1潘虹越48希辰38李媛希36曾轶可51List1.AddItem xs(i) + "" + Str(df(i)List1.AddItem ""Next iEnd SubPrivate Sub Command1_Click()Dim j As Integer, k As Integer, m As IntegerDim temp1 As StringDim temp2 As IntegerForj = 1 To 9m = jFor k = j + 1 To 10If Then m= kNext kIf j <

6、;> m Then temp1 = xs(j): (Z): xs(m) = temp1temp2 = df(j): df(j) = df(m): df(m) = temp2End IfNext jForj =List2.AddItem xs(j) + "" + Str(df(j)List2.AddItem ""Next jEnd Sub1) command1上单击事件处理过程中采用的算法是：诜择排序 (填：冒泡排序或选择排)2) command1上单击事件处理过程中采用的排序方式是：升序(填升序或降序)3)程序中划线处应填入程(k) > df

7、(m)4) 程序中划线处应填入 xs(j) = xs(m)5)程序中划线处应填入_1 to 72.冒泡排序(1)概念：把待排序的 n个元素的数组看成是垂直堆放的一列数据，从最下面的一个元素起，自下而上地比较相邻两个元素中的数据，将较小的数据换到上面的一个元素中，重复这一过程， 直到处理完最后两个元素中的数据，称为第一遍加工。 然后对余下的n-1个元素重复上述处理过程，直至最后进行余下的两个数据的比较和交换。dd119115230219I 318330422418515622(2)1152183W430522115115218218319_ 319422422530530算法：将数组内的数据从小

8、到大排序for i=1 to n-1for j=n to i+1 step -1if d(j)<d(j-1) thenk=d(j)d(j)=d(j-1)d(j-1)=kend ifnext jnext i(3)例题：例题1: 5位学生100米短跑的成绩(单位：秒)如下表。若采用冒泡排序算法对其进行排序，则第 3趟的排序结果是(A )原始数据14.213.512.613.312.8第1趟12.614.213.512.813.3第2趟12.612.814.213.513.3第3趟第4趟12.612.813.313.514.2A、12.6 12.8 13.314.2 13.5C、12.6 12

9、.814.2 13.5 13.3B 、12.6 12.8 13.3 13.5 14.2D 、12.6 12.8 13.5 14.2 13.3例题2:下表记录了 6个数据排序的过程。分析表中数据可知，该排序采用的算法与排序方式分别为(C )A、冒泡排序、降序 C冒泡排序、升序B、选择排序、降序D、选择排序、升序原始数据655759444569第1遍446557594569第2遍444565575969第3遍444557655969文案大全例题3:随机产生10个两位正整数，并对它们进行排序。 用VB编写的程序运行界 面如下图所示，请阅读并完善程序段，并上机验证。Dim d(1 to 10) as

10、integer'定义一个一维数组d,用于存放10个正整数Dim i As Integer As IntegerDim j As Integer, temp As IntegerPrivate Sub Command1_Click()'随机产生10个两位正整数Randomize '随机数初始化List1.Clear '原始数据清空Fori = 1 To 10d(i) = int(Rnd*90)+10List1.AddItem Str(d(i)将数据显示到原始数据列表中NextEnd SubPrivate Sub Command2_Click()'对10个两

11、位正整数进行排序List2.Clear'将排序后的列表数据清空For i = 1 To 9For j = 10 to i+1 step -1If d(j)>d(j-1) Thentemp=d(j):d(j)=d(j-1):d(j-1)=tempEnd IfNext jNext iFori = 1 To 10List2.AddItem Str(d(i)'在列表2中显示排序后的数据Next iEnd Sub3.选择排序和冒泡排序对比：若数组d里有n个待排序的数据，分别用冒泡法和选择法对此进行排序，试填充下表中的数据。排序方法趟数方向核心操作比较次数交换次数冒泡R-1自下而上数

12、据比较 数据交换)r2<=n'(n-iy2选择n-l自上而下找数据 数据交换rfn-1)a<=n-l、查找算法1.顺序查找(1)概念：从数组的第一个数据开始，逐个将数据与给定的值进行比较。若某个数据和给 定的值相等，则查找成功，输出所查数据的位置；反之，查找不成功，输出“数据 不存在于此数组中”kevV3265i=1i=2i-3i-4i=5kev3299i港到(2)算法:顺序查找的程序实现key在规模为n的数组变量d中查找某 一数据(假期要查找的数据存储 在变量ks中)d132062130For i-1 to n3321742526If d(i)=key then52589

13、Print 找到了，位置在皿i63265Exit sub74832wild if870521711 MilNext iPrint *找不ST2.对分查找(1)概念：前提：数组中被查找的数据必须是 有序的基本思想：首先将查找的数据与有序数组内处于中间位置的数据进行比较，如果两者相等，则查找成功；否则根据数组元素的有序性， 就可确定该数据应该在数组的前半 部分还是后半部分继续进行查找。在新确定的范围内，继续按上述方法进行查找， 直到获得最终结果。(2)算法：对分查找过程；d1234567ID15171822NT354i- 1我们用变迁：和j记豪 所要杳找跑用的起始 和终止位置.皿表示此 范困内的中间位置Key1a9101112131416 1645 4862656772SB97 qa*tii-£ix(i+jy2 f-8j=16dd1101102152163P 173174iT418522522627G27736735g45846943* i=9948*=-1-910621062.11651165-J-H1267m -fK(i+j)/2)-12126713P ?21372