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

第1页/81,第2章查找和排序,西安交通大学计教中心,第2页/81,查找基本概念,查找表:由同一类数据构成的用于查找的集合被称作查找表。查找表是具有一定存储结构的数据集合，比如顺序表结构、链式结构、树形结构等。查找往往根据数据元素的某个属性进行。例如根据学号查找某个学生记录。这种被用于查找的元素属性一般称为关键字，它往往可以唯一标识一个元素。,第3页/81,静态查找表:查找表一旦建立，在以后的查找过程中就不会改变。它所对应的查找算法属于静态查找技术。动态查找表：查找表建立后，在后来的查找过程中仍会改变查找表的内容。它所对应的查找算法属于动态查找技术。动态查找的例子词汇统计问题。就是统计一篇文章中使用了多少词汇以及每个词汇的使用次数。解决方法是先建立一个空的查找表，以后每读到一个词就在查找表中查询一下，如果该词汇存在则将其使用次数加一，否则将新词插入到查找表中并设使用次数为一次。显然，这个查找表是不断扩张的。,第4页/81,平均查找长度：为了确定数据元素在查找表中的位置，需要将给定值和表中的数据元素的关键字进行比较的次数的期望值。平均查找长度ASL的计算方法为：,n 为表长；Pi为查找第i个元素的概率。Ci为找到该记录时，曾和给定值比较过的数据元素的个数。在等概率条件下（Pi=1/n）这时平均查找长度为：,其中：,第5页/81,静态查找技术,假设静态顺序查找表的存储结构为：struct SSTableElemType*data;/存储空间地址int length;/表的长度;顺序查找表元素存放在data0至datalength-1中。,第6页/81,1顺序查找 顺序查找的方法是从表的一端开始，逐一比较给定的数据key和表中数据元素的关键字x的值，若两个数据一致则查找成功，同时给出该数据元素在表中的位置，否则查找失败。,第7页/81,算法描述,查找操作步骤：step1 从第1个元素开始查找；step2 用待查关键字值与各结点（记录）的关键字值逐个进行比较；若找到相等的结点，则查找成功；否则，查找失败。,第8页/81,顺序查找算法框图,i=0,seq_search(A，n，key)A 待查表n 元素个数key 要找的值,in&Ai!=key?,Y,N,查找key的循环,显示“查找失败”,返回,开始,i+,Ai=key?,Y,N,显示“查找成功”,第9页/81,顺序查找算法C+语言描述如下：int SqSearch(SSTable 该算法若查找成功，则函数返回值为目标元素在表中的位置，否则返回0。这里元素位置从1开始算起。,第10页/81,在上述算法中为了避免“出界”，需在循环中作kL.length 的判断，这使算法的执行时间几乎增加一倍。为提高效率，对查找表的结构改动如下：适当设置数组长度，将元素存于data1至datalength-1中，在0号单元预存待查找数据key作为监视哨。改写查找过程为从后往前查找。因为循环查找过程至少会在0号单元停止，这样就不必在每一次循环中都判别是否数组出界。,第11页/81,改进的顺序查找算法C+语言描述如下：int SqSearch(SSTable/找不到时，k为0 该算法若查找成功，则函数返回值为目标元素在表中的位置，否则返回0。,第12页/81,对于改进的顺序查找而言，找到第i个元素的比较次数Ci=n-i+1，所以在等概率查找的情况下，顺序表查找的平均查找长度为：,优点:对结点的逻辑次序(不必有序)和存储结构(顺序、链表均可）无要求；当序列中记录“基本有序”或N值较小时，是较好的算法；缺点：ASL较长讨论：能否减少比较次数，以提高效率。,算法讨论,例子,第13页/81,2折半查找(也称二分查找)算法思想：将有序数列的中点设置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。即通过一次比较，将查找区间缩小一半。二分查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，二分查找的先决条件是查找表中的数据元素必须有序。,第14页/81,算法步骤：step1 首先确定整个查找区间的中间位置，mid=（left+right）/2step2 用待查关键字值与中间位置的关键字值进行比较；若相等，则查找成功；若大于，则在后半区域继续进行二分查找；若小于，则在前半区域继续进行二分查找。Step3 对确定的缩小区域再按二分公式，重复上述步骤；最后，得到结果：要么，查找成功，要么，查找失败。,第15页/81,折半查找算法的C+语言描述如下：int BinSearch(SSTable/不存在待查元素,第16页/81,对给定有序数列 5，6，11，17，21，23，28，30，32，40进行半查找算法，查找关键字值为30的数据元素。则查找过程如下：第1次：5，6，11，17，21，23，28，30，32，40 low=0 mid=(0+9)/2=4 high=9,等概率情况下其平均查找长度为,，即 O(log2n),例子,第2次：5，6，11，17，21，23，28，30，32，40 low=5 mid=7 high=9,第17页/81,分块查找,分块查找又称索引顺序查找，这是顺序查找的一种改进方法。方法描述：将n个数据元素“按块有序”划分为m块（m n）。每一块中的结点不必有序，但块与块之间必须“按块有序”；即第1快中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，。每个块中元素不一定是有序的。,第18页/81,分块查找算法描述,step1 先选取各块中的最大关键字构成一个索引表；,step2 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；在已确定的块中用顺序法进行查找。,第19页/81,分块查找举例,有数列如下：22,12,13,9,8,33,42,44,38,24,48,60,58,75,47 按“块有序”分三块:(22,12,13,9,8),(33,42,44,38,24),(48,60,58,74,47)选取每块中最大的关键字组成索引表22,44,74,查找关键字值为60的元素。,用二分法，确定在索引表中的位置为 mid=2，key值60与a2比较，60a2,取第3个块;在第3块中用顺序法查找,比较两次,就可以找出60的元素来。,第20页/81,索引表结构定义,typedef struct int key;/*块最大值*/int link;/*指向块入口地址*/index;,示例,第21页/81,3、动态查找技术,前两种查找方法各有千秋。二分法查找效率高，顺序法可以采用链表存储结构，操作灵活。能否设计更好的算法？使其既有二分法的高效率，又有链表灵活性的查找方法？动态查找技术所依赖的查找表就是这样的算法，例如二叉排序树等。它们的共同特点是结构灵活，易于实现插入、删除等操作。这里主要介绍简单易用的二叉排序树。二叉排序树实际上就是将数据元素组织成二叉树形式，以达到与二分法相同的查找效率，而又具有链表的插入、删除操作的灵活性。,第22页/81,二叉排序树的定义：二叉排序树可能为一棵空的二叉树，若非空则必须满足以下特征：（1）根结点左子树中所有结点的关键字小于根结点的关键字；（2）根结点右子树中所有结点的关键字大于或等于根结点的关键字；（3）根结点的左右子树也都是二叉排序树。,一棵二叉排序树,第23页/81,算法描述：step1 首先建立起二叉排序树。,step2 将待查关键字值与树根结点进行比较，若相等，查找成功；,step3 否则根据比较结果确定查找路径：若小于根结点的关键字值，则与左子树的根结点的关键字值进行比较；若大于等于根结点的关键字值，则与右子树的根结点的关键字值进行比较。,step4 重复上述步骤，直到要么找到，查找成功；要么找不到，查找失败。,第24页/81,二叉排序树结点结构 typedef struct BinNode ElemType x;/关键字struct BinNode*left；/左子指针 struct BinNode*right;/右子指针*BinNodePtr;,第25页/81,二叉排序树生成算法,第26页/81,主程序框图,开始,初始化,输入结点数据循环,！ROOT,root=create_btee（）,create_btree(),结束?,N,Y,打印该树,查找指定结点,Print_btree(),Search_btree(),第27页/81,主程序,void main()char*s,*c,key=;struct tree*create_btree(),*search_btree(),*root=0;do/输入插入元素的循环 coutc;key=search_btree(root,c);/搜索二叉树 cout“press to continuen”;,第28页/81,生成二叉排序树程序,struct tree create_btree(struct tree*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,r-right,info);/插入右子树,二叉树生成,第29页/81,打印二叉排序树程序,print_btree(struct tree*r,int l)int i；if(r=0)return；print_tree(r-left,l+1)；/打印左子树 for(i=0;iinfo；/打印根结点 print_btree(r-right,l+1)；/打印右子树,第30页/81,struct tree*search_btree(struct tree*root,char key)if(!root)coutinfo!=key)/查找key循环 if(keyinfo)root=root-left;/沿左路查找 else root=root-right;/沿右路查找 if(root=0)/到叶结点也没找到 coutinfoendl;return root;,查询二叉排序树程序,第31页/81,举例,输入：输出：h b d d p e r h b p e r,例子,前序遍历序列：h d b e p r中序遍历序列：b d e h p r后序遍历序列：b e d r p h,第32页/81,动态查找过程也是生成二叉排序树的过程。假定由整数序列10，6，19，22，8，2生成一棵二叉排序树，可以采用逐个元素插入的方法实现。(1)首先将10作为根结点(2)然后插入6时，通过比较知610，所以将6作为10的左孩子插入；(3)同理将19作为10的右孩子插入；(4)整数22通过和10、19比较后，作为19的右孩子插入。(5)依次插入剩余的其他元素,第33页/81,哈希（hash）查找,哈希查找也称为散列查找。它不同于前面介绍的几种查找方法。上述方法都是把查找建立在比较的基础上，而哈希查找则是通过计算存储地址的方法进行查找的。计算是计算机的特点之一，因此，建立在计算基础上的哈希查找是一种快速查找方法。,第34页/81,哈希查找的基本概念,哈希表 由哈希函数的值组成的表。哈希查找是建立在哈希表的基础上，它是线性表的一种重要存储方式和检索方法。在哈希表中可以实现对数据元素的快速检索。哈希函数 哈希表中元素是由哈希函数确定的。将数据元素的关键字K作为自变量，通过一定的函数关系（称为哈希函数），计算出的值，即为该元素的存储地址。表示为：Addr=H（key）建立哈希函数的原则均匀性 H（key）的值均匀分布在哈希表中；简单 以提高地址计算的速度。,第35页/81,冲突及冲突处理,在哈希元素求解过程中，不同关键字值对应到同一个存储地址的现象称为冲突。即关键字K1 K2，但哈希函数值 H（K1）=H（K2）。均匀的哈希函数可以减少冲突，但不能避免冲突。发生冲突后，必须解决；也即必须寻找下一个可用地址。处理冲突是建立哈希表过程中不可缺少的一部分。,第36页/81,处理冲突 开放地址法,当发生地址冲突后，求解下一个地址用 Hi=(H（key）+di）MOD m i=1,2,k(k m-1)其中:H(key)为哈希函数,m为哈希表长度,di为增量序列。增量序列的不同取法，又构成不同的开放地址法。线性探测再散列 di=1,2,m-1二次探测再散列,di=12,-12,22,-22,+k2,-k2(k m/2),第37页/81,处理冲突 链地址法,当发生地址冲突后,将所有函数值相同的记录连成一个单链表。,第38页/81,链地址法处理冲突,对给定数列 22,41,53,46,30,13,1,67,建立哈希表。表长取9,即08。哈希函数设定为:H(key)=key MOD 8。,1234567,41,1,46,13,30,22,53,67,H(22)=H(46)=H(30)=6,H(53)=H(13)=5,H(67)=3,H(41)=H(1)=1,第39页/81,哈希查找操作步骤,用给定的哈希函数构造哈希表根据选择的冲突处理方法解决地址冲突在哈希表的基础上执行哈希查找,第40页/81,建立哈希表,建立哈希表操作步骤：step1 取数据元素的关键字key，计算其哈希函数值（地址）。若该地址对应的存储空间还没有被占用，则将该元素存入；否则执行step2解决冲突。step2 根据选择的冲突处理方法，计算关键字key的下一个存储地址。若下一个存储地址仍被占用，则继续执行step2，直到找到能用的存储地址为止。,第41页/81,举例,对给定数列 22,41,53,46,30,13,1,67,建立哈希表。表长取9,即08。哈希函数设定为:H(key)=key MOD 8,用线性探测解决冲突 Hi=(H(key)+di)MOD m,di=1,2,m-1。,取41，计算H（41）=1，该地址空，可用；,取22，计算H（22）=6，该地址空，可用；,第42页/81,举例（续一）,取53，计算 H（53）=5，该地址空，可用；,取46，计算 H（46）=6，该地址冲突，用线性探测法计算下一个可用地址 Hi=（6+1）MOD 8=7，该地址空，可用；,第43页/81,举例（续二）,取30，计算 H（30）=6，该地址冲突，用线性探测法计算下一个可用地址 Hi=（6+1）MOD 8=7，该地址冲突，再用线性探测法计算下一个可用地址；Hi=0，地址空，可用；,取13，计算 H（13）=5，依法解决冲突，得出：,第44页/81,举例（续三）,取1，计算 H（1）=1，该地址冲突，解决冲突可得：,取67，计算 H（67）=3，冲突，解决冲突，得出：,第45页/81,哈希查找,哈希查找的过程和建立哈希表的过程是一致的。设哈希表为HST0M-1，哈希函数取H（key），解决冲突的方法为R（x），则哈希查找步骤为：Step1 对给定k值，计算哈希地址 Di=H（k）；若HSTi为空，则查找失败；若HSTi=k，则查找成功；否则，执行step2（处理冲突）。Step2 重复计算处理冲突的下一个存储地址 Dk=R（Dk-1），直到HSTDk为空，或HSTDk=k为止。若HSTDk=K，则查找成功，否则查找失败。,第46页/81,查找举例,以上述哈希表为例。哈希函数为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,22,41,53,46,30,13,1,67,平均查找长度ASL=(3+1+6+3+2+1+1+2)=查找key=67 比较两次找到,查找成功;查找key=21 比较8次找不到,查找失败。,示例,第47页/81,排序基本概念,排序是计算机内经常进行的一种操作，其目的是将一组同类型的记录序列调整为按照元素关键字有序的记录序列。例如将学生记录按学号排序，将课程记录按课程编码排序。排序的形式化定义为：假设含n个记录的序列为 R1,R2,，Rn，其相应的关键字序列为 K1,K2,，Kn。这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系Kp1Kp2Kpn，按此固有关系将最初的记录序列重新排列为 Rp1,Rp2,，Rpn 的操作称作排序。,第48页/81,排序分为内部排序和外部排序。若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。本节只讨论内部排序的若干方法,第49页/81,内部排序分类方法按方法实现特点可分为插入排序、选择排序、交换排序、归并排序等等；按方法效率可分为简单的排序法、先进的排序法等等。简单的排序法包括插入排序、选择排序、冒泡排序等，它们的时间复杂度为O(n2)。而先进的排序法包括快速排序、归并排序等，它们的时间复杂度大约为O(nlog2n)。,第50页/81,插入排序算法,基本思想：将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),有序 无序,每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较,找出插入位置,将该元素插入到有序数列的合适位置中。,第51页/81,插入排序算法步骤,Step1 从有序数列a1和无序数列a2,a3,an开始进行排序;Step2 处理第i个元素时(i=2,3,n),数列 a1,a2,ai-1是已有序的,而数列ai,ai+1,an是无序的。用ai与ai-1、a i-2,a1进行比较,找出合适的位置将ai插入。Step3 重复Step2，共进行n-1的插入处理，数列全部有序。,第52页/81,插入排序举例,设有数列 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 次,第53页/81,插入排序算法,insert_sort(int*item,int n)int i，j，t;for（i=1；i=0/插入该元素,例子,第54页/81,选择排序算法,基本思想：每次从待排序的记录中选出关键字最小（或最大）的记录，顺序放在已有序的记录序列的最后（或最前）面，直到全部数列有序。a1，a2，a3，a4，,an a1，a2，a3(1)，a4(1),an(1).a1(n-1)，a2(n-1)，,an(n-1),有序 无序,第55页/81,选择排序算法步骤,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趟的选择处理，数列全部有序。,第56页/81,选择排序举例,设有数列 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，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 次,第57页/81,选择排序算法,select_sort(int*item,int count)int i,j,k，t;for(i=0;icount-1;+i)/n-1次循环 k=i;/无序部分第1个元素 t=itemi;/及位置 for(j=i+1;jcount;+j)/寻找最小值循环 if(itemjt)k=j;t=itemj;/记录最小值及位置 itemk=itemi;/交换最小值与无序 itemi=t;/部分最后1个元素位置,例子,第58页/81,交换排序（冒泡排序）,指导思想：两两比较待排序记录的关键字，并交换不满足顺序要求的那些偶对元素，直到全部数列满足有序为止。冒泡排序（Bubble sort）是基于交换排序的一种算法。它是依次两两比较待排序元素；若为逆序（递增或递减）则进行交换，将待排序元素从左至右比较一遍称为一趟“冒泡”。每趟冒泡都将待排序列中的最大关键字交换到最后（或最前）位置。直到全部元素有序为止。,a1 a2 a3 an-1 an,第59页/81,冒泡排序算法,step1 从待排序队列的前端开始(a1)两两比较记录的关键字值,若aiai+1(i=1,2,n-1),则交换ai和ai+1的位置,直到队列尾部。一趟冒泡处理，将序列中的最大值交换到an的位置。step2 如法炮制，第k趟冒泡，从待排序队列的前端开始(a1)两两比较ai和ai+1（i=1，2，n-k)，并进行交换处理,选出序列中第k大的关键字值,放在有序队列的最前端。Step3 最多执行n-1趟的冒泡处理,序列变为有序。,第60页/81,冒泡排序算法举例,设有数列 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 第5趟 13，27，49，58，65，76，97 2 第6趟 13，27，49，58，65，76，97 1 总计：21 次,第61页/81,冒泡排序算法C+语言描述：void BubleSort(int v,int n)int temp;for(int i=1;ivj+1)/交换两个相邻元素 temp=v j;vj=vj+1;vj+1=temp;/第i大的元素筛选结束,第62页/81,改进的冒泡排序算法,从上述举例中可以看出，从第4趟冒泡起，序列已有序，结果是空跑了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 次,第63页/81,改进的冒泡排序算法,bubble_a(int*item,int count)int a,b,t,c;for(a=1;aitemb)/若逆序，则 t=itemb-1;/交换位置 itemb-1=itemb;itemb=t;c=0;/若有交换，则改变交换标志 if(c)break;/若没有交换，则退出处理,示例,第64页/81,快速排序,快速排序法是一位计算机科学家C.A.R.Hoare推出并命名的。曾被认为是最好的一种排序方法。快速排序法是对冒泡排序法的一种改进，也是基于交换排序的一种算法。因此，被称为“分区交换排序”。,第65页/81,快速排序基本思想,在待排序序列中按某种方法选取一个元素K，以它为分界点，用交换的方法将序列分为两个部分：比该值小的放在左边，否则在右边。形成 左子序列K右子序列 再分别对左、右两部分实施上述分解过程，直到各子序列长度为1，即有序为止。分界点元素值K的选取方法不同，将构成不同的排序法，也将影响排序的效率：取左边第1个元素为分界点；取中点A（left+right）/2为分界点；选取最大和最小值的平均值为分界点等。设有序列a1，a2，,an,选取中点元素K为分界点,分别从序列两头分别与K进行比较,小于K的元素交换到左边,否则交换到右边;一趟处理后,左边子序列的元素均小于分界点值K,右边子序列元素均大于等于K值。,第66页/81,快速排序算法,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（不可再分）为止，也即序列全部有序。,第67页/81,快速排序算法举例,对于数列49，38，60，90，70，15，30，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,i,k=90,j,i,j,j,i,第68页/81,快速排序算法举例（续一）,初始状态: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 70 15 49 30 38 15 49 70 60 49 30 38 1549 70 60 49 小计：8,i,j,k=49,j,i,i,j,3（i2、j1）,i,j,3（i1、j2）,第69页/81,快速排序算法举例（续二）,初始状态:30 38 15 比较次数 第3趟 30 38 15 3（i2、j1）30，15 38 小计：3 第4趟 70 60 49 2（i1、j1）49 60 70 2（i1、j1）小计：4,k=38,i,j,j,i,k=60,j,i,j,i,第70页/81,快速排序算法举例（续三）,初始状态:30 15 比较次数 第5趟 30 15 2（i1、j1）15 30 小计：2 最后状态：15 30 38 49 49 60 70 90 总计：27,k=30,i,j,第71页/81,快速排序算法,quick_sort(item,count)int*item,count;qs(item,0,count-1);,第72页/81,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(itemileft)j-;/*确定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);/*对分割出的右部再处理*/,第73页/81,算法讨论,分界点选取方法不同，排序效果差异很大；比较次数为nlogn，即为：O（nlogn），交换次数为n/6*logn。快速排序算法是不稳定的。,示例,第74页/81,归并排序,归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表；即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。,第75页/81,归并排序,Step1 把待排序的n个记录看作是长度为1的有序序列。将相邻子序列两两归并为长度为2的有序序列；Step2 把得到的n/2个长度为2的有序子序列再归并为长度为 2*2 的有序序列；Step3 按Step2的方式，重复对相邻有序子序列进行归并操作，直到成为一个有序序列为止。,第76页/81,归并排序算法简述,设有待排序数列 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）中。,第77页/81,归并排序算法举例,设有数列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,SWAP数组：,SWAP数组：,100,6,301,202,1,8,38,1,6,8,8,38,100,202,301,示例,第78页/81,第2章 作业,习题二、三、四实验 二叉排序树的生成和遍历（前、中、后序）下周安排两次上机（周一、周四）,