第四讲 查找及排序

第四讲查找与排序★交换排序★插入排序★顺序查找★二分查找★选择排序查找(Searching)，也称检索，亦即查表，就是在大量的信息集中寻找一个“特定的”信息元素。人们几乎每天都要做“查找”工作，如查询电话号码、查字典、查图书目录卡片等。查找是数据处理领域中的一个重要内容，查找的效率将直接影响到数据处理的效率。查找基本概念☆查找表以集合为逻辑结构，以查找为核心运算，同时包括其他运算的数据结构。☆关键字用来标识数据元素的数据项，简称键。☆主关键字可以唯一标识一个数据元素的关键字。☆次关键字可以标识若干数据元素的关键字。☆查找

根据某个给定的K值，在查找表中寻找一个键值等于K的元素，若找到这样的元素，则称查找成功，此时的运算结果为该数据元素在查找表中的位置，否则称查找不成功，运算结果为一特殊标志。 查找是许多重要的计算机程序中最耗费时间的部分，查找算法的优劣密切关系着查找操作的速度。★查找的方法 查找某个数据元素依赖于该数据元素在一组数据中所处的位置，即该组数据的组织方式，故应按照数据元素的组织方式决定采用的查找方法；反过来，为了提高查找方法的效率，要求数据元素采用某些特殊的组织方式。★算法的评价 查找时通常只需要很少的辅助空间，因此更关心的是它的时间复杂度。在查找算法中，基本运算是给定值与关键字的比较，所以算法的主要时间是花费在“比较”上。 对于含有n个数据元素的查找表，查找成功时的平均查找长度为：ASL= 其中，Pi为查找第i个数据元素的概率；Ci为查到第i个数据元素时，需与关键字进行比较的次数。顺序查找 基本思想：从表的一端开始，依次将每个元素的关键字同给定值K进行比较，若某个元素的关键字等于给定值K，则表明查找成功，返回该元素的下标；反之，若直到所有元素都比较完毕，仍找不到关键字为K的元素，则表明查找失败，返回特定的值。#definemaxsize表长typedefstruct{keytypekey;//关键字………//其他域}rec;typedefstructrecsqtable[maxsize+1];intn;//最后一个数据元素的下标voidseqsrch(sqtabler，keytypek){//在长度为n的表r中查找关键字为k的元素，r[n]为表尾的扩充;i指示查找结果r[n].key=k;i=0;//给监督哨赋值while(r[i].key!=k)i++;if(i<n)printf(“succ,i=%d”,i);//查找成功，i指示待查元素在表中位置elseprintf(“unsucc”);//i=n时表明查找不成功}算法在顺序查找时，Ci取决于所查元素在表中的位置，Ci=i，设每个元素的查找概率相等，即Pi=1/n，则查找成功的平均查找长度为：ASL=查找不成功的查找长度为n+1。优点： 算法简单且适应面广，对表的结构无任何要求，无论元素是否按关键字有序都可应用缺点：平均查找长度比较大，特别是当n较大时，查找效率较低。二分查找 基本思想：设三个指针low,high和mid分别指示待查有序表的表头，表尾和中间元素，在开始查找时，三个指针的初值分别为：low=1；high=n；mid=(low+high)/2。折半查找是从表的中间元素开始，用待查元素的关键字k和r[mid].key比较，此时有三种情况(假设该查找表按关键字的非递减次序排列)。1)若r[mid].key=k，则查找成功；2)若r[mid].key>k，则k必在较低标号的那一半表中，令high=mid-13)若r[mid].key<k，则k必在较高标号的那一半表中，令low=mid+1例：给出表元素关键字为：{05,13,19,21,37,56,64,75,80,88,92}1.查找关键字k=21的情况(1)low=1;high=11;mid=(1+11)div2=60513192137566475808892lowmidhigh因为r[mid].key>k，所以向左找，令high=mid-1=5(2)low=1;high=5;mid=(1+5)div2=30513192137566475808892lowmidhigh因为r[mid].key<k，所以向右找，令low=mid+1=4(3)low=4;high=5;mid=(4+5)div2=40513192137566475808892lowmidhigh因为r[mid].key=k，查找成功，所查元素在表中的序号为mid的值(1)low=1;high=11;mid=(1+11)div2=6因为r[mid].key<k，所以向右找，令low=mid+1=7(2)low=7;high=11;mid=(7+11)div2=90513192137566475808892lowmidhigh因为r[mid].key<k，所以向右找，令low=mid+1=10(3)low=10;high=11;mid=(10+11)div2=100513192137566475808892lowmidhigh因为r[mid].key>k，所以向左找，high=mid-1=92.查找关键字k=85的情况0513192137566475808892lowmidhigh因为low>high，所以查找失败voidBinsrch(sqtabler，keytypek)//在长度为n的有序表r中查找关键字为k的元素，查到后输出{low=1；high=n；//置初值while(low<=high){mid=(low+high)/2；if(k==r[mid].key){printf("succi=%d\n"，mid)；break；}elseif(k>r[mid].key)

low=mid+1；//向右找else

high=mid-1；//向左找}if(low>high)printf("nosucc\n")；//low>high，查找不成功}算法以上面的11个元素的查找表为例，找到第6个元素仅需比较1次；找到第3个和第9个元素需比较2次；找到第1,4,7和10个元素需比较3次；找到第2,5,8和11个元素需比较4次。上面的查找过程可以用下图所示的一棵二叉树来表示。6391471011258树中每一个结点表示表中的一个数据元素，结点中的值为该元素在表中的位置 查找某一元素的比较次数最多等于树的深度.即log2n找到元素的过程正好是从根节点一直走到某个叶子节点的路径，因此所用的比较次数最多等于树的深度。由此看来，无论元素找到或找不到，查找某一元素的比较次数最多等于树的深度.即log2n。排序(Sorting)，是指将一个无序序列整理成按值非递减（递增）顺序排列的有序序列。排序排序分为内排序和外排序。内排序的整个排序过程都在内存进行。当文件很大以至于内存不足以存放全部记录，在排序过程中需要对外存进行存取访问，称之为外排序。我们只讨论内排序，并且排序的对象一般认为是顺序存储的线性表（一维数组）。内部排序的方法

在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。使有序区中记录的数目增加一个或几个的操作称为一趟排序。存放待排序数据的数据结构：typedefstruct{intkey;datatypeotheritem;//其他域}records;typedefstructrecordsList[n+1];内排序插入类排序直接插入排序折半插入排序希尔排序交换类排序冒泡排序快速排序选择类排序选择排序堆排序归并类排序归并排序其他排序计数排序基数排序冒泡排序 基本思想：比较k1和k2,如果这些关键字的值不符合排序顺序,就交换k1和k2；然后对记录k2和k3,k3和k4等等进行相同的工作。直到kn-1和kn为止,到此得到一个最大(或最小)关键字值存在kn的位置上(通常将此过程叫做一趟)。重复这个过程,就得到在位置kn-1,kn-2等处的适当记录,使得所有记录最终被排好序。例如:将5个记录的关键字7,4,8,3,9进行冒泡排序。排序后k1≤k2≤…≤kn(n=5)。7443347344837773888899999①②③④

第四趟就没有可交换的偶对,排序结束。voidbubblesort(Listr,intn){for(m=1;m<=n;m++)scanf(“%d”,&r[m]);k=n;do{all=“T”;//all=T,标志没有交换的;all=F,标志有交换的for(m=1;m<=k-1;m++){i=m+1;if(r[m]>r[i]){max=r[m];r[m]=r[i];r[j]=max;all=“F”;}}k--;}while((all==“T”)||(k==1))}算法时间分析:最好的情况（关键字在记录序列中顺序有序）：只需进行一趟起泡“比较”的次数：“移动”的次数：n-10

最坏的情况（关键字在记录序列中逆序有序）：需进行n-1趟起泡“比较”的次数：快速排序 基本思想：设输入文件有n个记录R1,R2,…,Rn,它们对应的关键字是k1,k2,…,kn。该方法先取序列中任一关键字K(通常取第一个)，然后用K从两头到中间进行交换，就能形成一个分划：凡是小于等于K的被移到左边，凡是大于K的被移到右边。例:初始关键字[4655134294051770]将46→xij第一次交换后[

55134294051770]ji第二次交换后[17551342940570]ji第三次交换后[17

134294055570]j第四次交换后[1705134294

5570]jii1755059446第五趟排序后0513174246557094第一趟排序后[17051342]46[945570]第二趟排序后[1305]17[42]46[945570]第三趟排序后[05]1317[42]46[945570]第四趟排序后0513174246[7055]94

例:初始关键字[4655134294051770]算法voidqksort(Listr,intL,intP)//将r[L]至r[P]进行排序{do{while((r[j].key>=x.key)&&(j>i))j--;//从表尾一端开始比较if(i<j){r[i]=r[j];i++;while((r[i].key<=x.key)&&(i<j))i++;//再从表的始端起进行比较if(i<j){r[j]=r[i];j--;}}}while(i!=j);r[i]=x;i++;j--;//一趟快排结束，将x移至正确位置if(L<j)qksort(r,L,j);//反复排序前一部分if(i<P)qksort(r,i,P);//反复排序后一部分}//qksort时间分析:快速排序是目前内部排序中最快的方法。若关键字的分布式均匀的，可以粗略的认为每次划分都把文件分成长度相等的两个文件。但如果原来的文件是有次序的，时间复杂性为O(n2)。因此，快速排序偏爱一个无次序的文件。令T(n)为分类n个记录所需之比较次数,设n=2k，则k=log2n，有：T(n)≤cn+2T(n/2)(其中cn为进行一趟排序所需的时间)T(n)≤cn+2(cn/2+2T(n/4))≤2cn+4T(n/4)……≤kcn+2kT(1)=O(nlog2n)直接插入排序假设在排序过程中，记录序列R[1..n]的状态为：

则一趟插入排序的基本思想为：将记录R[i]插入到有序子序列R[1..i-1]中，使记录的有序序列从R[1..i-1]变为R[1..i]。显然，完成这个“插入”需分三步进行：1．查找R[i]的插入位置j+1；2．将R[j+1..i-1]中的记录后移一个位置；3．将R[i]复制到R[j+1]的位置上。算法voidinsort(Listr,intn){//r为给定的表，其记录为r[i]，i=1，…，nfor(i=2;i<=n;i++){r[0]=r[i];//r[0]作为标志位j=i-1;while(r[0].key<r[j].key){r[j+1]=r[j];j--;}//j从i-1至0，r[j].key与r[i].key进行比较r[j+1]=r[0];}}//insort时间分析：

实现排序的基本操作有两个：（1）“比较”序列中两个关键字的大小；（2）“移动”记录。对于直接插入排序：最好的情况（关键字在记录序列中顺序有序）：最坏的情况（关键字在记录序列中逆序有序）：“比较”的次数：“移动”的次数：

2(n-1)“比较”的次数：“移动”的次数：

希尔排序 基本思想：对待排序记录序列先作“宏观”调整，再作“微观”调整。所谓“宏观”调整，指的是，“跳跃式”的插入排序。即：将记录序列分成若干子序列，每个子序列分别进行插入排序,待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。假设将n个记录分成d个子序列，则这d个子序列分别为：{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]}{R[2]，R[2+d]，R[2+2d]，…，R[2+kd]}…{R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d]}其中，d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。例如：

第二趟希尔排序，设增量d=3

第三趟希尔排序，设增量d=1voidShellInsert(Listr,intd)//本算法对直接插入算法作了以下修改：//1.前后记录位置的增量是d，而不是1；//2.r[0]只是暂存单元，不是哨兵。当j<=0时，插入位置已找到。{for(i=d+1;i<=n;i++)if(r[i]<r[i-d])//需将r[i]插入有序增量子表{r[0]=r[i];//暂存在R[0]j=i-d;while((j>0)and(r[0]<r[j])){r[j+d]=r[j];//记录后移，查找插入位置j=j-d;}r[j+d]=r[0];//插入}}算法例如,假设文件中8个记录的关键字,我们不采用顺序比较,而是先从第一个关键字开始每隔4个关键字进行比较;同理第二个也从隔4个关键字进行比较,第三个…,第四个…,依次做下去.题中选d1=4,从小到大排序:例初始d1=44655134294170570

55与1713与05第一趟后结果4617054294551370

46与0594与1346与13第二趟后结果d2=20517134246559470

13,46分别交换两次0513174246557094

第三趟后结果d3=113与1794与70简单选择排序 基本思想：首先在n个记录中选择一个具有最小或最大关键字的记录，将选出的记录与记录集合中的第一个记录交换位置。然后在r[2]至r[n]中选择一个最小或最大的值与r[2]交换位置，…，依此类推，直至r[n-1]和r[n]比较完毕。voidslsort(Listr,intn)//每次从r[j](j=i+1,…n)中选了最小值，与r[i](i=1,2,…,n-1)交换，进行分类{for(i=1;i<=n-1;i++)//共进行n-1趟排序{m=i;for(j=i+1;j<=n;j++)if(r[j].key<r[m].key)m=j;//m指示关键字最小的记录的序号if(m!=i){x=r[i];r[i]=r[m];r[m]=x;}}}例：关键字序列{055，55，60，13，05，94，17，70},利用选择排序算法进行排序。关键字r[1]055r[2]55r[3]60r[4]13r[5]05r[6]94r[7]17r[8]70i=1,m=505556013055941770i=2,m=405136055055941770i=3,m=705131755055946070i=4,m=405131755055946070i=5,m=505131755055946070i=6,m=705131755055609470i=7,m=805131755055607094算法的复杂性分析：当选择第一个最小值时需进行n-1次比较，选第二个最小值时需进行n-2次比较，…，选n-1个最小值时需进行n-(n-1)次比较，所以总的比较次数为(n-1)+(n-2)+…+2+1=n(n-1)/2故排序n个记录需要时间为O(n2)。由于执行一次交换，需三次移动记录，最多交换n-1次，故最多移动次数为3(n-1)堆排序堆是由n个记录的线性序列{R1,R2,…，Rn};其关键字序列{k1,k2,…，kn},满足下列特性时，称之为堆。或若将此数列看成是一棵完全二叉树的顺序存储表示，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左、右子树不空时，根结点的值小于(或大于)左、右子树根结点的值。下列两个序列为堆，对应的完全二叉树如下图{96，83，27，38，11，09}9683273811091236248547305391ki≤k2iki≤k2i+1ki≥k2iki≥k2i+1大根堆小根堆{12，36，24，85，47，30，53，91}1)首先将一个关键字集合用完全二叉树的形式排列; 如给定关键字集合为{46,55,13,42,94,17,5,70}组成的完全二叉树如下：465513429417570建堆的过程2)开始建堆：采用筛选法，逐步将大的关键字筛到堆底。筛选法的思想是这样的：

►假设集合r有m个结点，从某个结点i（第一次i=[m/2]）开始筛选;

►先看第i个结点的左右子树，设第i个结点的左子树为kj,右子树为kj+1。若kj<kj+1则沿左分支筛，否则沿右分支筛选，即（j=j+1）。将ki与kj进行比较，若ki>kj则对调，小的上来大的下去。

►

然后kj作为新的根结点，再对新的根结点的左右子树进行判断。重复上述过程，直到某个结点的左或右子树根结点的下标大于m为止。第一次调用筛选法：m=8,i=[m/2]=4,从i=4开始，看k4的左右子树，仅有左子树，因此42与70比较，42<70，所以不变。j=i*2=8，i=j，再向下看，此时的i无左右子树,所以返回，如右图所示。4655134294170570第二次调用筛选法：i=3,k3=13,13的左右子树为17和05，因17>05,故沿右子树比较，13>05,进行对调，此时13无左右子树，所以返回。46551342941705700513{46,55,13,42,94,17,05,70}{46,55,05,42,94,17,13,70}

►先看第i个结点的左右子树，设第i个结点的左子树为kj,右子树为kj+1。若kj<kj+1则沿左分支筛，否则沿右分支筛选，即（j=j+1）。将ki与kj进行比较，若ki>kj则对调，小的上来大的下去。

►然后kj作为新的根结点，再对新的根结点的左右子树进行判断。重复上述过程，直到某个结点的左或右子树根结点的下标大于m为止。第三次调用筛选法：i=2,k2=55,因为42<94，所以沿左子树筛选，42<55,进行对调，此时55还有左子树70，因55<70，所以不变，再向下70无左右子树，所以返回，此时二叉树如右图所示。4655054294171370第四次调用筛选法：i=1,k1=46,因为05<42，所以沿右子树筛选，05<46,进行对调，此时46还有左右子树17,13，因13<17，所以再沿右子树筛选，13<46,所以对调，46无左右子树，所以返回，此时二叉树如右图所示。4642055594171370554246054613{46,42,05,55,94,17,13,70}{05,42,13,55,94,17,46,70}

►先看第i个结点的左右子树，设第i个结点的左子树为kj,右子树为kj+1。若kj<kj+1则沿左分支筛，否则沿右分支筛选，即（j=j+1）。将ki与kj进行比较，若ki>kj则对调，小的上来大的下去。