2023学年完整公开课版排序和查找

排序和查找排序数据排序（sorting）是最重要的计算应用之一。例如查字典，字典中的词条是按序存放的，我们才能按字母顺序找到要查的字。又如图书馆的藏书也是按书的编号有序排列的。在计算机上数据库里的资料也是有序排列的。排序

排序（sorting）是数据处理中经常使用的一种重要运算。其功能是将数据元素的无序序列调整为一个有序序列。数据元素中一般有多个数据项，排序可选择其中一个可排序的数据项（可进行比较运算）作为依据，称为排序关键字。常用的排序法比如我们对高考考生的统计表进行排序，可根据考生的准考证号，这样的关键字可以保证排序结果的唯一性，称主关键字。但为了便于录取，我们也可以按高考总分排序，只可称关键字,这样同一分数的人很多，这些人的排名可再取一个次关键字如数学或语文分来排序，以减少重复排名的随意性。从小到大排序称升序，反之为降序。最常见的三类是选择排序、插入排序和交换排序。基本思想是：

每一趟从待排序的记录中选出关键字最小的元素，顺序放在已排好序的子序列的后面，直到全部记录排序完成。直接选择排序（StraightSelectionSort）是最简单的。此方法的最大优点是易读。缺点是做过的工作和序列的部分有序性利用不上，效率低。选择排序中也有可能利用到以前的工作的方法，如堆排列（HeapSort）。选择排序[49 38 65 97 76 13 27 49’]

13 [38 65 97 76 49 27 49’]

13 27 [65 97 76 49

38

49’]

13 27 38 [97

76

49 65 49’]

13 27 38 49 [76 97 65 49’]

13 27 38 49 49’ [97

65 76]

13 27 38 49 49’ 65 [97

76]

13 27 38 49 49’ 65 76 97

图1直接选择排序的过程选择排序【例】直接选择排序voidSelectSort(intslist[],intlast){inti,j,k,temp;for(i=0;i<last;i++){ k=i; temp=slist[i]; for(j=i;j<=last;j++)if(slist[j]<temp){ k=j; temp=slist[j]; } if(k!=i){ temp=slist[i]; slist[i]=slist[k]; slist[k]=temp; }}}（1）直接插入排序的思想是：(以升序为例)当插入第i(i>=1)个元素sl[i]时，前面的元素sl[0]，sl[1],…，sl[i-1]已经排好序，我们将sl[i]的关键字与sl[i-1]，sl[i-2]，…，的关键码顺序进行比较，找到第一个比它小的，则sl[i]插到该元素之后。插入排序i0123456temp初始序列[8]67945261[68]7945272[678]945293[6789]45244[46789]5255[456789]226[2456789]直接插入排序算法中用了一个临时变量temp，要插入的元素放到temp中，这样插入前各元素后移时允许将该元素冲掉。插入排序【例】升序直接插入排序算法voidInsertSort(intslist[],intlast){ inti,j,temp; for(i=1;i<=last;i++){ temp=slist[i]; j=i; while(j>0&&temp<slist[j-1]){ slist[j]=slist[j-1]; j--;//查找与移动同时做

} slist[j]=temp; }}（2）对半插入排序（BinaryInsertSort）是用对半查找的思想取代顺序查找。对半插入排序要快于插入排序。插入排序【例】升序对半插入排序算法升序对半插入排序算法。当关键字相同时，插入排序原来在前的仍在前，称稳定排序。voidBinaryInsertSort(intslist[],intlast){ intlow,high,mid,i,j,temp; for(i=1;i<=last;i++){ temp=slist[i]; low=0; high=i-1; while(low<=high){//请注意与对半查找的

mid=(low+high)/2;//不同之处

if(temp<slist[mid])high=mid-1; elselow=mid+1; }//稳定排序

for(j=i-1;j>=low;j--)slist[j+1]=slist[j]; slist[low]=temp; }}查找一、随机产生若干个整数，使用顺序查找和对分查找进行查寻数据，输出查找结果。

（1）顺序查找算法流程图（2）编写程序代码PrivateSubCommand6_Click()'顺序查找

DimiAsInteger,keyAsInteger

key=Val(Text2.Text)'查找的数据

Fori=1Tonum'依次查找

Ifd(i)=keyThen'找到了数据

Label5.Caption="在数组的第"+Str(i)+"个位置"

ExitFor'中断当前For循环

EndIf

Next

Ifi=num+1ThenLabel5.Caption="在数组中没有找到数据"+Str(key)

EndSub

二、如果数组中有n个元素，那么顺序查找的平均查找次数是（n+1）/2次，有没有效率更高的查找算法呢？

1.猜数游戏

在猜数游戏过程，如何使用更少的次数猜对数字呢？采用对半策略。第一次猜50，结果是太小了，所以数字肯定在51～100，第二次就猜51～100的当中位置（取下限的整数），猜75，结果是太大了，所以数字肯定在51～74，再猜当中位置57，正好猜中！这种猜数的方法就是对分查找的算法。2.对分查找算法首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。对分查找的前提条件数组中的数据是已经排序的。(1)对分查找算法流程图对分查找过程如下图所示：（2）编写程序代码PrivateSubCommand4_Click()'对分查找

DimiAsInteger,jAsInteger,keyAsInteger,mAsInteger

DimncAsInteger

IfNotsortedThen'进行对分查找时，需先对数据进行排序

MsgBox"进行对分查找时，需先对数据进行排序"

ExitSub'结束过程

EndIf

key=Val(Text2.Text)'输入查找的数据

i=1

j=num

nc=0'查找次数nc

DoWhilei<=j'对分查找

nc=nc+1

m=Fix((i+j)/2)

Ifd(m)=keyThen‘找到了

Label6.Caption="在数组的第"+Str(m)+"个位置，共查找了"+Str(nc)+"次"

ExitSub

EndIf

Ifkey<d(m)Then'未找到，继续查找

j=m-1

Else

i=m+1

End