【教学课件】第2章查找和排序.ppt

《【教学课件】第2章查找和排序.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第2章查找和排序.ppt（78页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、下一页上一页停止放映第2章查找和排序 西安交通大学计教中心西安交通大学计教中心1下一页上一页停止放映查找基本概念查找基本概念 查找表:由同一类数据构成的用于查找的集合被称作查找表。查找表是具有一定存储结构的数据集合，比如顺序表结构、链式结构、树形结构等。查找往往根据数据元素的某个属性进行。例如根据学号查找某个学生记录。这种被用于查找的元素属性一般称为关键字，它往往可以唯一标识一个元素。2下一页上一页停止放映 静静态态查查找找表表:查查找找表表一一旦旦建建立立，在在以以后后的的查查找找过过程程中中就就不不会会改改变变。它它所所对对应应的的查查找找算算法法属属于于静静态态查找技术。查找技术。动动态

2、态查查找找表表：查查找找表表建建立立后后，在在后后来来的的查查找找过过程程中中仍仍会会改改变变查查找找表表的的内内容容。它它所所对对应应的的查查找找算算法法属于动态查找技术。属于动态查找技术。动态查找的例子词汇统计问题。就是统计一篇文章中使用了多少词汇以及每个词汇的使用次数。解决方法是先建立一个空的查找表，以后每读到一个词就在查找表中查询一下，如果该词汇存在则将其使用次数加一，否则将新词插入到查找表中并设使用次数为一次。显然，这个查找表是不断扩张的。3下一页上一页停止放映平均查找长度：平均查找长度：为了确定数据元素在查找表中的位置，需要将给定值和表中的数据元素的关键字进行比较的次数的期望值。平

3、均查找长度ASL的计算方法为：n 为表长；Pi为查找第i个元素的概率。Ci为找到该记录时，曾和给定值比较过的数据元素的个数。在等概率条件下（Pi=1/n）这时平均查找长度为：其中其中：4下一页上一页停止放映静态查找技术静态查找技术 假设静态顺序查找表的存储结构为：struct SSTableElemType*data;/存储空间地址int length;/表的长度 ;顺序查找表元素存放在data0至datalength-1中。5下一页上一页停止放映1 1顺序查找顺序查找 顺序查找的方法是从表的一端开始，逐一比较给定的数据key和表中数据元素的关键字x的值，若两个数据一致则查找成功，同时给出该数

4、据元素在表中的位置，否则查找失败。6下一页上一页停止放映算法描述算法描述查找操作步骤：step1 从第1个元素开始查找；step2 用待查关键字值与各结点（记录）的关键字值逐个进行比较；若找到相等的结点，则查找成功；否则，查找失败。7下一页上一页停止放映顺序查找算法框图顺序查找算法框图 i=0seq_search(Aseq_search(A，n n，key)key)A A 待查表待查表n n 元素个数元素个数key key 要找的值要找的值in&Ai!=key?YN查找查找keykey的循环的循环显示显示“查找失败查找失败”返回返回开始开始i+Ai=key?YN显示显示“查找成功查找成功”8下

5、一页上一页停止放映 顺序查找算法顺序查找算法C+C+语言描述如下：语言描述如下：int SqSearch(SSTable&L,KeyType key)int k=0;while(kL.length&L.datak.x!=key)k+;if(kL.length)return k+1;/返回数据元素位置返回数据元素位置else return 0;该该算算法法若若查查找找成成功功，则则函函数数返返回回值值为为目目标标元元素素在在表表中中的位置，否则返回的位置，否则返回0 0。这里元素位置从。这里元素位置从1 1开始算起。开始算起。9下一页上一页停止放映 在上述算法中为了避免“出界”，需在循环中作kL

6、.length 的判断，这使算法的执行时间几乎增加一倍。为提高效率，对查找表的结构改动如下：适当设置数组长度，将元素存于data1至datalength-1中，在0号单元预存待查找数据key作为监视哨。改写查找过程为从后往前查找。因为循环查找过程至少会在0号单元停止，这样就不必在每一次循环中都判别是否数组出界。10下一页上一页停止放映改进的顺序查找算法改进的顺序查找算法C+C+语言描述如下：语言描述如下：int SqSearch(SSTable&L,KeyType key)L.data0.x=key;/监视哨int k=L.length;while(L.datak.x!=key)k=k-1;/

7、从后往前找从后往前找return k;/找不到时，k为0 该算法若查找成功，则函数返回值为目标元素在表中的位置，否则返回0。11下一页上一页停止放映对于改进的顺序查找而言，找到第i个元素的比较次数Ci=n-i+1，所以在等概率查找的情况下，顺序表查找的平均查找长度为：ASLn2l优点:对结点的逻辑次序(不必有序)和存储结构(顺序、链表均可）无要求；当序列中记录“基本有序”或N值较小时，是较好的算法；l缺点：ASL较长l讨论：能否减少比较次数，以提高效率。算法讨论算法讨论例子12下一页上一页停止放映2 2折半查找折半查找(也称二分查找也称二分查找)算法思想：将有序数列的中点设置为比较对象，如果要

8、找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。即通过一次比较，将查找区间缩小一半。二分查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，二分查找的先决条件是查找表中的数据元素必须有序。13下一页上一页停止放映l算法步骤：step1step1 首先确定整个查找区间的中间位置，mid=（left+right）/2step2step2 用待查关键字值与中间位置的关键字值进行比较；若相等，则查找成功；若大于，则在后半区域继续进行二分查找；若小于，则在前半区域继续进行二分查找。Step3Step3 对确定的缩小区域再按二分公式，重复上述步骤；最后最后，得到结果

9、：要么，查找成功，要么，查找失败。14下一页上一页停止放映折半查找算法的折半查找算法的C+C+语言描述如下：语言描述如下：int BinSearch(SSTable&L,KeyType key)int low,high,mid;low=0;high=L.length-1;/设置查找区间初值 while(low=high)mid=(low+high)/2;if(key=L.datamid.x)return mid+1;/查找成功 else if(keya2,取第3个块;在第3块中用顺序法查找,比较两次,就可以找出60的元素来。19下一页上一页停止放映索引表结构定义索引表结构定义typedef s

10、truct int key;/*块最大值 */int link;/*指向块入口地址*/index;示例示例20下一页上一页停止放映3、动态查找技术动态查找技术 前两种查找方法各有千秋。二分法查找效率高，顺序法可以采用链表存储结构，操作灵活。能否设计更好的算法？使其既有二分法的高效率，又有链表灵活性的查找方法？动态查找技术所依赖的查找表就是这样的算法，例如二叉排序树等。它们的共同特点是结构灵活，易于实现插入、删除等操作。这里主要介绍简单易用的二叉排序树。二叉排序树实际上就是将数据元素组织成二叉树形式，以达到与二分法相同的查找效率，而又具有链表的插入、删除操作的灵活性。21下一页上一页停止放映 二

11、叉排序树的定义：二叉排序树可能为一棵空的二叉树，若非空则必须满足以下特征：（1 1 1 1）根结点左子树中所有结）根结点左子树中所有结）根结点左子树中所有结）根结点左子树中所有结点的关键字小于根结点的关点的关键字小于根结点的关点的关键字小于根结点的关点的关键字小于根结点的关键字；键字；键字；键字；（2 2 2 2）根结点右子树中所有结）根结点右子树中所有结）根结点右子树中所有结）根结点右子树中所有结点的关键字大于或等于根结点的关键字大于或等于根结点的关键字大于或等于根结点的关键字大于或等于根结点的关键字；点的关键字；点的关键字；点的关键字；（3 3 3 3）根结点的左右子树也都）根结点的左右子

12、树也都）根结点的左右子树也都）根结点的左右子树也都是二叉排序树。是二叉排序树。是二叉排序树。是二叉排序树。一棵二叉排序树22下一页上一页停止放映算法描述：step1 首先建立起二叉排序树。step2 将待查关键字值与树根结点进行比较，若相等，查找成功；step3 否则根据比较结果确定查找路径：若小于根结点的关键字值，则与左子树的根结点的关键字值进行比较；若大于等于根结点的关键字值，则与右子树的根结点的关键字值进行比较。step4 重复上述步骤，直到要么找到，查找成功；要么找不到，查找失败。23下一页上一页停止放映二叉排序树结点结构二叉排序树结点结构 typedef struct BinNode

13、 typedef struct BinNode ElemType x;ElemType x;/关键字关键字struct BinNode*leftstruct BinNode*left；/左子指针左子指针 struct BinNode*right;struct BinNode*right;/右子指针右子指针*BinNodePtr;*BinNodePtr;24下一页上一页停止放映二叉排序树生成算法二叉排序树生成算法 建立二叉树建立二叉树Create_btree()Create_btree()查询结点查询结点Search_btree()Search_btree()打印二叉树打印二叉树Print_bt

14、ree()Print_btree()主程序主程序Btree.cppBtree.cpp25下一页上一页停止放映主程序框图主程序框图 开始开始初始化初始化输入结点数据循环输入结点数据循环！ROOTroot=create_btee（）（）create_btree()结束结束?NY打印该树打印该树查找指定结点查找指定结点Print_btree()Search_btree()26下一页上一页停止放映 主程序主程序void main()char*s,*c,key=;struct tree*create_btree(),*search_btree(),*root=0;do /输入插入元素的循环 cout“E

15、nter a letter:”;gets(s);if(!root)root=create_btree(root,root,*s);/插入头结点 else create_btrr(root,root,*s);/插入子结点 while(*s);print_btree(root,0);/打印二叉树 key=1;while(key)/反复搜索循环 coutc;key=search_btree(root,c);/搜索二叉树 cout“press to continuen”;27下一页上一页停止放映生成二叉排序树程序生成二叉排序树程序 struct tree create_btree(struct tre

16、e*root,struct tree*r,char info)if(r=0)r=new(struct tree);/生成一个结点空间 if(r=0)/空间满,返回 coutleft=0;r-right=0;r-info=info;if(root)/若根非空 if(infoinfo)root-left=r;/插入左子 else root-right=r;/或插入右子 else /若根为空 r-right=0;r-left=0;return r;if(infoinfo)create_btree(r,r-left,info);/插入左子树 if(info=r-info)create_btree(r,

17、r-right,info);/插入右子树二叉树生成28下一页上一页停止放映打印二叉排序树程序打印二叉排序树程序print_btree(struct tree*r,int l)int i；if(r=0)return；print_tree(r-left,l+1)；/打印左子树 for(i=0;il;i+)cout“”；coutinfo；/打印根结点 print_btree(r-right,l+1)；/打印右子树 29下一页上一页停止放映 struct tree*search_btree(struct tree*root,char key)if(!root)coutinfo!=key)/查找查找ke

18、ykey循环循环 if(keyinfo)root=root-left;/沿左路查找沿左路查找 else root=root-right;/沿右路查找沿右路查找 if(root=0)/到叶结点也没找到到叶结点也没找到 cout“Search Failuren”;break;if(root!=0)/查找成功查找成功 cout“Successful search!key=”infoendl;return root;查询二叉排序树程序30下一页上一页停止放映举例举例 输入：输出：h b d d p e r h b p e r 例子hprdbe前序遍历序列：h d b e p r中序遍历序列：b d e

19、 h p r后序遍历序列：b e d r p h31下一页上一页停止放映 动态查找过程也是生成二叉排序树的过程。假定由整数序列10，6，19，22，8，2生成一棵二叉排序树，可以采用逐个元素插入的方法实现。(1)首先将10作为根结点(2)然后插入6时，通过比较知610，所以将6作为10的左孩子插入；(3)同理将19作为10的右孩子插入；(4)整数22通过和10、19比较后，作为19的右孩子插入。(5)依次插入剩余的其他元素 32下一页上一页停止放映哈希（hash）查找哈希查找也称为散列查找。它不同于前面介绍的几种查找方法。上述方法都是把查找建立在比较的基础上，而哈希查找则是通过计算存储地址的方

20、法进行查找的。计算是计算机的特点之一，因此，建立在计算基础上的哈希查找是一种快速查找方法。33下一页上一页停止放映哈希查找的基本概念哈希表 由哈希函数的值组成的表。哈希查找是建立在哈希表的基础上，它是线性表的一种重要存储方式和检索方法。在哈希表中可以实现对数据元素的快速检索。哈希函数 哈希表中元素是由哈希函数确定的。将数据元素的关键字K作为自变量，通过一定的函数关系（称为哈希函数），计算出的值，即为该元素的存储地址。表示为：Addr=H（key）建立哈希函数的原则均匀性 H（key）的值均匀分布在哈希表中；简单 以提高地址计算的速度。34下一页上一页停止放映冲突及冲突处理在哈希元素求解过程中，

21、不同关键字值对应到同一个存储地址的现象称为冲突。即关 键 字 K1 K2，但 哈 希 函 数 值 H（K1）=H（K2）。均匀的哈希函数可以减少冲突，但不能避免冲突。发生冲突后，必须解决；也即必须寻找下一个可用地址。处理冲突是建立哈希表过程中不可缺少的一部分。35下一页上一页停止放映处理冲突 开放地址法当发生地址冲突后，求解下一个地址用 Hi=(H（key）+di）MOD m i=1,2,k(k m-1)其中:H(key)为哈希函数,m为哈希表长度,di为增量序列。增量序列的不同取法，又构成不同的开放地址法。线性探测再散列 di=1,2,m-1二次探测再散列 di=1di=12,-1,-12,

22、2,22,-2,-22,+k,+k2,-k,-k2(k(k m/2)m/2)36下一页上一页停止放映处理冲突 链地址法当发生地址冲突后,将所有函数值相同的记录连成一个单链表。37下一页上一页停止放映 链地址法处理冲突对给定数列 22,41,53,46,30,13,1,67,建立哈希表。表长取9,即08。哈希函数设定为:H(key)=key MOD 8。123456741 1 46 13 30 225367H(22)=H(46)=H(30)=6H(22)=H(46)=H(30)=6H(53)=H(13)=5H(53)=H(13)=5H(67)=3H(67)=3H(41)=H(1)=1H(41)=

23、H(1)=138下一页上一页停止放映哈希查找操作步骤用给定的哈希函数构造哈希表根据选择的冲突处理方法解决地址冲突在哈希表的基础上执行哈希查找39下一页上一页停止放映建立哈希表建立哈希表操作步骤：step1 取数据元素的关键字key，计算其哈希函数值（地址）。若该地址对应的存储空间还没有被占用，则将该元素存入；否则执行step2解决冲突。step2 根据选择的冲突处理方法，计算关键字key的下一个存储地址。若下一个存储地址仍被占用，则继续执行step2，直到找到能用的存储地址为止。40下一页上一页停止放映举例 对给定数列 22,41,53,46,30,13,1,67,建立哈希表。表长取9,即08

24、。哈希函数设定为:H(key)=key MOD 8,用线性探测解决冲突 Hi=(H(key)+di)MOD m,di=1,2,m-1。0 1 2 3 4 5 6 7 82222 0 1 2 3 4 5 6 7 841比较次数：比较次数：1 1取取4141，计算，计算H H（4141）=1=1，该地址空，可用；，该地址空，可用；取取2222，计算，计算H H（2222）=6=6，该地址空，可用；，该地址空，可用；41下一页上一页停止放映举例（续一）取取5353，计算，计算 H H（5353）=5=5，该地址空，可用；，该地址空，可用；2241 0 1 2 3 4 5 6 7 853 比较次数：比

25、较次数：1 1 1224153460 1 2 3 4 5 6 7 8 比较次数：比较次数：1 1 1 2取取4646，计算，计算 H H（4646）=6=6，该地址冲突，用线性探，该地址冲突，用线性探测法计算下一个可用地址测法计算下一个可用地址 Hi=Hi=（6+16+1）MOD 8=7MOD 8=7，该地址空，可用；，该地址空，可用；42下一页上一页停止放映举例（续二）取取3030，计算，计算 H H（3030）=6=6，该地址冲突，用线性，该地址冲突，用线性探测法计算下一个可用地址探测法计算下一个可用地址 Hi=Hi=（6+16+1）MOD 8=MOD 8=7 7，该地址冲突，再用线性探测

26、法计算下一个可，该地址冲突，再用线性探测法计算下一个可用地址；用地址；Hi=0Hi=0，地址空，可用；，地址空，可用；22410 1 2 3 4 5 6 7 853 比较次数：比较次数：3 1 1 1 24630224153460 1 2 3 4 5 6 7 8 比较次数：比较次数：3 1 6 1 1 23013取取1313，计算，计算 H H（1313）=5=5，依法解决冲突，得出：，依法解决冲突，得出：43下一页上一页停止放映举例（续三）取取1 1，计算，计算 H H（1 1）=1=1，该地址冲突，解决冲突可得：，该地址冲突，解决冲突可得：22410 1 2 3 4 5 6 7 85346

27、3013 比较次数：比较次数：3 1 6 3 1 1 21224153463013167 比较次数：比较次数：3 1 6 3 2 1 1 20 1 2 3 4 5 6 7 8取取6767，计算，计算 H H（6767）=3=3，冲突，解决冲突，得出：，冲突，解决冲突，得出：44下一页上一页停止放映 哈希查找 哈希查找的过程和建立哈希表的过程是一致的。设哈希表为HST0M-1，哈希函数取H（key），解决冲突的方法为R（x），则哈希查找步骤为：Step1 对给定k值，计算哈希地址 Di=H（k）；若HSTi为空，则查找失败；若HSTi=k，则查找成功；否则，执行step2（处理冲突）。Step2

28、 重复计算处理冲突的下一个存储地址 Dk=R（Dk-1），直 到 HSTDk为 空，或HSTDk=k为止。若HSTDk=K，则查找成功，否则查找失败。45下一页上一页停止放映 查找举例 以上述哈希表为例。哈希函数为H(key)=key MOD 8,设有数列22,41,53,46,30,13,1,67,用线性探测法解决冲突,建立的哈希的表为:0 1 2 3 4 5 6 7 8比较次数：比较次数：3 1 6 3 2 1 1 2 3 1 6 3 2 1 1 222415346301316781819平均查找长度平均查找长度ASL=(3+1+6+3+2+1+1+2)=ASL=(3+1+6+3+2+1+

29、1+2)=查找查找key=67 key=67 比较两次找到两次找到,查找成功查找成功;查找查找key=21 key=21 比较比较8 8次找不到次找不到,查找失败。查找失败。示例示例46下一页上一页停止放映排序基本概念排序基本概念 排序是计算机内经常进行的一种操作，其目的是将一组同类型的记录序列调整为按照元素关键字有序的记录序列。例如将学生记录按学号排序，将课程记录按课程编码排序。排序的形式化定义为：假设含n个记录的序列为 R1,R2,，Rn，其相应的关键字序列为 K1,K2,，Kn。这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系Kp1Kp2Kpn，按此固有关系将最初的记录序列

30、重新排列为 Rp1,Rp2,，Rpn 的操作称作排序。47下一页上一页停止放映 排序分为内部排序和外部排序。若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。本节只讨论内部排序的若干方法 48下一页上一页停止放映内部排序分类方法内部排序分类方法按方法实现特点可分为插入排序、选择排序、交换排序、归并排序等等；按方法效率可分为简单的排序法、先进的排序法等等。简单的排序法包括插入排序、选择排序、冒泡排序等，它们的时间复杂度为O(n2)。而先进的排序法包括快速排序、归并排序等，它们的时间复

31、杂度大约为O(nlog2n)。49下一页上一页停止放映插入排序算法基本思想：将n个元素的数列分为已有序和无序两个部分。a1，a2，a3，a4，,an a1(1)，a2(1)，a3(1)，a4(1),an(1).a1(n-1)，a2(n-1)，,an(n-1)有序有序 无序无序每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较,找出插入位置,将该元素插入到有序数列的合适位置中。50下一页上一页停止放映插入排序算法步骤Step1 从有序数列a1和无序数列a2,a3,an开始进行排序;Step2 处理第i个元素时(i=2,3,n),数列 a1,a2,ai-1是已有序的,而数列ai

32、,ai+1,an是无序的。用ai与ai-1、a i-2,a1进行比较,找出合适的位置将ai插入。Step3 重复Step2，共进行n-1的插入处理，数列全部有序。51下一页上一页停止放映插入排序举例 设有数列 18，12，10，12，30，16 初始状态：18，12，10，12，30，16 比较次数 i=1 18，12，10，12，30，16 1 i=2 12，18，10，12，30，16 2 i=3 10，12，18，12，30，16 2 i=4 10，12，12，18，30，16 1 i=5 10，12，12，18，30，16 3 10，12，12，16，18，30 总计：9 次52下一页

33、上一页停止放映插入排序算法 insert_sort(int*item,int n)int i，j，t;for（i=1；i=0&titemj)/寻找插入位置寻找插入位置 itemj+1=itemj;/当前元素后移当前元素后移 j-;itemj+1=t;/插入该元素插入该元素 例子53下一页上一页停止放映选择排序算法基本思想：每次从待排序的记录中选出关键字最小（或最大）的记录，顺序放在已有序的记录序列的最后（或最前）面，直到全部数列有序。a1，a2，a3，a4，,an a1，a2，a3(1)，a4(1),an(1).a1(n-1)，a2(n-1)，,an(n-1)有序有序 无序无序54下一页上一页

34、停止放映选择排序算法步骤Step1 从原始数列a1,a2,a3,an开始进行排序，比较n-1次，从中选出最小关键字，放在有序数列中，形成a1、a2,a3,an有序数列和无序数列两部分，完成第1趟排序。Step2 处理第i趟排序时(i=2,3,n),从剩下的n-i+1个元素中找出最小关键字，放在有序数列的后面。Step3 重复Step2，共进行n-1趟的选择处理，数列全部有序。55下一页上一页停止放映选择排序举例 设有数列 18，12，10，12，30，16 初始状态：，18，12，10，12，30，16 比较次数 i=1 10，18，12，12，30，16 5 i=2 10，12，12，18，

35、30，16 4 i=3 10，12，12，18，30，16 3 i=4 10，12，12，16，18，30 2 i=5 10，12，12，16，18，30 1 总计：15 次56下一页上一页停止放映选择排序算法select_sort(int*item,int count)int i,j,k，t;for(i=0;icount-1;+i)/n-1n-1次循环次循环 k=i;/无序部分第无序部分第1 1个元素个元素 t=itemi;/及位置及位置 for(j=i+1;jcount;+j)/寻找最小值循环寻找最小值循环 if(itemjai+1(i=1,2,n-1),则交换ai和ai+1的位置,直到队

36、列尾部。一趟冒泡处理，将序列中的最大值交换到an的位置。step2 如法炮制，第k趟冒泡，从待排序队列的前端开始(a1)两两比较ai和ai+1（i=1，2，n-k)，并进行交换处理,选出序列中第k大的关键字值,放在有序队列的最前端。Step3 最多执行n-1趟的冒泡处理,序列变为有序。59下一页上一页停止放映冒泡排序算法举例设有数列 65,97,76,13,27,49,58 比较次数 第1趟 65，76，13，27，49，58，97 6 第2趟 65，13，27，49，58，76，97 5 第3趟 13，27，49，58，65，76，97 4 第4趟 13，27，49，58，65，76，97

37、3 第5趟 13，27，49，58，65，76，97 2 第6趟 13，27，49，58，65，76，97 1 总计：21 次60下一页上一页停止放映冒泡排序算法冒泡排序算法C+C+语言描述语言描述：void BubleSort(int v,int n)int temp;for(int i=1;in;i+)for(int i=1;in;i+)for(int j=0;jn-i;j+)for(int j=0;jvj+1)/交换两个相邻元素 temp=v j;vj=vj+1;vj+1=temp;/第i大的元素筛选结束61下一页上一页停止放映改进的冒泡排序算法从上述举例中可以看出，从第4趟冒泡起，序列

38、已有序，结果是空跑了3趟。若两次冒泡处理过程中，没有进行交换，说明序列已有序，则停止交换。这就是改进的冒泡算法的处理思想。用改进的冒泡算法进行处理，比较次数有所减少。对于数列 65,97,76,13,27,49,58 比较次数 第1趟 65，76，13，27，49，58，97 6 第2趟 65，13，27，49，58，76，97 5 第3趟 13，27，49，58，65，76，97 4 第4趟 13，27，49，58，65，76，97 3 总计：18 次62下一页上一页停止放映改进的冒泡排序算法bubble_a(int*item,int count)int a,b,t,c;for(a=1;ac

39、ount;+a)/n-1/n-1趟循环趟循环 c=1;/设置交换标志设置交换标志 for(b=1;bitemb)/若逆序，则若逆序，则 t=itemb-1;/交换位置交换位置 itemb-1=itemb;itemb=t;c=0;/若有交换，则改变交换标志若有交换，则改变交换标志 if(c)break;/若没有交换，则退出处理若没有交换，则退出处理 示例示例63下一页上一页停止放映快速排序快速排序法是一位计算机科学家C.A.R.Hoare推出并命名的。曾被认为是最好的一种排序方法。快速排序法是对冒泡排序法的一种改进，也是基于交换排序的一种算法。因此，被称为“分区交换排序”。64下一页上一页停止放

40、映快速排序基本思想在待排序序列中按某种方法选取一个元素K，以它为分界点，用交换的方法将序列分为两个部分：比该值小的放在左边，否则在右边。形成 左子序列K右子序列 再分别对左、右两部分实施上述分解过程，直到各子序列长度为1，即有序为止。分界点元素值K的选取方法不同，将构成不同的排序法，也将影响排序的效率：取左边第1个元素为分界点；取中点A（left+right）/2为分界点；选取最大和最小值的平均值为分界点等。设有序列a1，a2，,an,选取中点元素K为分界点,分别从序列两头分别与K进行比较,小于K的元素交换到左边,否则交换到右边;一趟处理后,左边子序列的元素均小于分界点值K,右边子序列元素均大

41、于等于K值。65下一页上一页停止放映快速排序算法Step1 分别从两端开始，指针i指向第一个元素Aleft，指针j指向最后一个元素Aright，分界点取K；Step2 循环（ij）从右边开始进行比较：若K Aj，则将Aj交换到左边；若K Aj，则 j=j-1，再进行比较；从左边开始进行比较：若K Ai，则 i=i+1，再进行比较；若K Ai，则将Ai交换到右边。当i=j时，一次分解操作完成。Step3 在对分解出的左、右两个子序列按上述步骤继续进行分解，直到子序列长度为1（不可再分）为止，也即序列全部有序。66下一页上一页停止放映快速排序算法举例对于数列49，38，60，90，70，15，30

42、，49，采用中点分界法：初始状态:49 38 60 90 70 15 30 49 比较次数 第1趟 49 38 60 90 70 15 30 49 49 38 60 90 70 15 30 49 5（i4、j1）49 38 60 49 70 15 30 90 5（i4、j1）49 38 60 49 70 15 30 90 小计：10 ik=90jij ji67下一页上一页停止放映快速排序算法举例（续一）初始状态:49 38 60 49 70 15 30 比较次数 第2趟 49 38 60 49 70 15 30 2（i1、j1）30 38 60 49 70 15 49 30 38 60 49

43、70 15 49 30 38 15 49 70 60 49 30 38 154949 70 60 49 小计：8ijk=49jiij3 3（i2i2、j1j1）ij3 3（i1i1、j2j2）68下一页上一页停止放映快速排序算法举例（续二）初始状态:30 38 15 比较次数 第3趟 30 38 15 3（i2、j1）30，15 38 小计：3 第4趟 70 60 49 2（i1、j1）49 6060 70 2（i1、j1）小计：4k=38ijjik=60jiji69下一页上一页停止放映快速排序算法举例（续三）初始状态:30 15 比较次数 第5趟 30 15 2（i1、j1）15 3030

44、小计：2 最后状态：15 30 38 49 49 60 70 90 总计：27 k=30ij70下一页上一页停止放映快速排序算法quick_sort(item,count)int*item,count;qs(item,0,count-1);71下一页上一页停止放映qs（）子函数qs(int*item,int left,int right)int i,j,x,y,k;i=left;j=right;x=item(left+right)/2;/*计算中点位置 */do /*ij 的循环处理 */while(itemix&iright)i+；/*确定i点交换位置 */while(xleft)j-;/*

45、确定j点交换位置 */if(i=j)/*如果i、j位置合法，则交换*/y=itemi;/*Ai和Aj的位置 */itemi=itemj;itemj=y;i+;j-;while(i=j);if(leftj)qs(item,left,j);/*对分割出的左部再处理*/if(iright)qs(item,i,right);/*对分割出的右部再处理*/72下一页上一页停止放映算法讨论分界点选取方法不同，排序效果差异很大；比较次数为nlogn，即为：O（nlogn），交换次数为n/6*logn。快速排序算法是不稳定的。示例示例73下一页上一页停止放映归并排序归并（Merge）排序法是将两个（或两个以上）

46、有序表合并成一个新的有序表；即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。74下一页上一页停止放映归并排序Step1 把待排序的n个记录看作是长度为1的有序序列。将相邻子序列两两归并为长度为2的有序序列；Step2 把得到的n/2个长度为2的有序子序列再归并为长度为 2*2 的有序序列；Step3 按Step2的方式，重复对相邻有序子序列进行归并操作，直到成为一个有序序列为止。75下一页上一页停止放映归并排序算法简述设有

47、待排序数列 49，38，65，97，76，12，27，第一趟处理，先将每个元素看成是有序的子序列，49 38 65 97 76 12 27第二趟处理，将长度为1的子序列合并为长度为2的子序列，38，49 65，97 12，76 27 第三趟处理，将长度为2的子序列合并为长度为4的子序列，38，49，65，97 12，27，76 第四趟处理，将长度为4的子序列合并为长度为8的序列，12，27，38，49，65，76，97 提示：将归并过程中贡献出的元素，送进工作单元（SWAPm）中。76下一页上一页停止放映归并排序算法举例设有数列6，202，100，301，38，8，1，初始状态：6 202 100 301 38 8 1 比较次数 i=1 6 202 100 301 8 38 1 3 i=2 6 100 202 301 1 8 38 4 i=3 1 6 8 38 100 202 301 4 总计：11 SWAPSWAP数组：数组：SWAPSWAP数组：数组：1001006 63013012022021 18 838381 16 68 88 83838100100202202301301示例示例77下一页上一页停止放映第2章 作业习题二、三、四实验 二叉排序树的生成和遍历（前、中、后序）下周安排两次上机（周一、周四）78