c与数据结构实用.pptx

《c与数据结构实用.pptx》由会员分享，可在线阅读，更多相关《c与数据结构实用.pptx（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、本章内容本章内容 查找查找 排序排序第1页/共61页14.1 查找查找1.查找的基本概念查找的基本概念 查找：查找：在数据元素集合在数据元素集合(查找表查找表)中查找关键字与中查找关键字与给定值相等的数据元素。给定值相等的数据元素。关键字关键字：数据元素中的一个或多个数据项值，它数据元素中的一个或多个数据项值，它可以惟一标识一个数据元素。可以惟一标识一个数据元素。平均查找长度平均查找长度(ASL)：式中，式中，n为查找表的长度；为查找表的长度；pi为查找第为查找第i个元素的概个元素的概率，在等概率情况下率，在等概率情况下pi等于等于1/n；Ci为找到第为找到第i个元个元素时的比较次数素时的比较

2、次数第2页/共61页2.顺序查找顺序查找 基本思想：基本思想：用给定值依次与线性表中每个元素的用给定值依次与线性表中每个元素的关键字进行比较。如果某个元素的关键字与给定值关键字进行比较。如果某个元素的关键字与给定值相同，则查找成功；如果找遍全表也没有发现满足相同，则查找成功；如果找遍全表也没有发现满足条件的元素，则查找失败。条件的元素，则查找失败。要求：要求：查找表必须采用线性表。查找表必须采用线性表。第3页/共61页 实现一：顺序表类中实现顺序查找的成员函数实现一：顺序表类中实现顺序查找的成员函数第4页/共61页 实现二：单链表类中实现顺序查找的成员函数实现二：单链表类中实现顺序查找的成员函

3、数第5页/共61页 顺序查找的平均查找长度顺序查找的平均查找长度 评价：评价：在用顺序查找方法完成查找时，每进行一在用顺序查找方法完成查找时，每进行一次成功查找需要的平均比较次数约为表长度的一半，次成功查找需要的平均比较次数约为表长度的一半，因此，它的效率较低。适用于在查找表较小的情况因此，它的效率较低。适用于在查找表较小的情况下进行查找。下进行查找。第6页/共61页3.二分查找二分查找要求：要求：u查找表必须采用线性表；查找表必须采用线性表；u必须以顺序方式存储线性表；必须以顺序方式存储线性表；u线性表中所有数据元素必须按照关键字有序排列线性表中所有数据元素必须按照关键字有序排列 基本思想：

4、基本思想：将给定值与处于顺序表将给定值与处于顺序表“中间位置中间位置”上的元素的关键字进行比较，若相等则查找成功，上的元素的关键字进行比较，若相等则查找成功，若给定值大于关键字则在表的后半部分继续进行二若给定值大于关键字则在表的后半部分继续进行二分查找，否则在表的前半部分继续进行二分查找。分查找，否则在表的前半部分继续进行二分查找。如此进行下去直至找到满足条件的元素，或当前查如此进行下去直至找到满足条件的元素，或当前查找区为空，此时查找失败。找区为空，此时查找失败。第7页/共61页演示：演示：第8页/共61页例子：例子：二分查找函数模板及其测试程序二分查找函数模板及其测试程序第9页/共61页优

5、点：优点：u查找效率高查找效率高u平均查找长度平均查找长度缺点：缺点：u查找前要将表中元素按关键字有序排列查找前要将表中元素按关键字有序排列u只适用于线性表的顺序存储。适用于那种一经建只适用于线性表的顺序存储。适用于那种一经建立就很少改动而又经常需要查找的线性表。立就很少改动而又经常需要查找的线性表。第10页/共61页4.分块查找分块查找要求：要求：u查找表必须采用线性表；查找表必须采用线性表；u待查找的线性表分成若干块。在每一块内，元素待查找的线性表分成若干块。在每一块内，元素的存放是任意的，但在块与块之间元素的存放是有的存放是任意的，但在块与块之间元素的存放是有序的，即前一块中任意一个元素

6、的关键字值都必须序的，即前一块中任意一个元素的关键字值都必须小于（或大于）后一块中所有元素的关键字值；小于（或大于）后一块中所有元素的关键字值；u建立一个索引表，索引表中的每个索引项对应于建立一个索引表，索引表中的每个索引项对应于一块。一个索引项至少应含有两部分信息：一是对一块。一个索引项至少应含有两部分信息：一是对应块中最大的关键字值；二是指向对应块中第一个应块中最大的关键字值；二是指向对应块中第一个元素的指针元素的指针第11页/共61页 基本思想：基本思想：首先在索引表中查找，确定出要查找首先在索引表中查找，确定出要查找的元素应该在哪一块中；然后在已确定的那一块内的元素应该在哪一块中；然后

7、在已确定的那一块内进行顺序查找。进行顺序查找。第12页/共61页 演示：演示：第13页/共61页 优点：优点：块内元素是任意存放的，插入或删除运算块内元素是任意存放的，插入或删除运算不会造成元素的大量移动。不会造成元素的大量移动。缺点：缺点：u增加了存放索引表的辅助空间及初始时对线性表增加了存放索引表的辅助空间及初始时对线性表分块排序的运算分块排序的运算u大量的插入和删除运算可能会导致各块中元素的大量的插入和删除运算可能会导致各块中元素的数目很不均匀，这会降低查找速度数目很不均匀，这会降低查找速度第14页/共61页 平均查找长度：平均查找长度：将长度为将长度为n的线性表均匀地划分的线性表均匀地

8、划分成块，每块中有个结点，即。假定成块，每块中有个结点，即。假定对表中每个元素的查找概率相等，则查找某一块的对表中每个元素的查找概率相等，则查找某一块的概率为，查找块中某个结点的概率为概率为，查找块中某个结点的概率为 索引表使用顺序查找：索引表使用顺序查找：索引表使用二分查找：索引表使用二分查找：第15页/共61页5.二叉排序树查找二叉排序树查找 二叉排序树的定义：二叉排序树的定义：二叉排序树或者是一棵空二叉树，或者是具有以下二叉排序树或者是一棵空二叉树，或者是具有以下性质的二叉树：性质的二叉树：1、若它的、若它的左子树左子树非空，则左子树上所有结点的值非空，则左子树上所有结点的值均均小于小于

9、根结点的值；根结点的值；2、若它的、若它的右子树右子树非空，则右子树上所有结点的值非空，则右子树上所有结点的值均均不小于不小于根结点的值；根结点的值；3、左、右子树本身又各是一棵二叉排序树。、左、右子树本身又各是一棵二叉排序树。第16页/共61页 插入操作：插入操作：若二叉排序树为空，则新结点为二叉排序树的根若二叉排序树为空，则新结点为二叉排序树的根结点；否则将新结点的关键字值和根结点的关键结点；否则将新结点的关键字值和根结点的关键字值进行比较，若小于根结点的值，则将新结点字值进行比较，若小于根结点的值，则将新结点插入到左子树中去，否则，插入到右子树中去。插入到左子树中去，否则，插入到右子树中

10、去。此插入过程是递归进行的。此插入过程是递归进行的。第17页/共61页 设有整数序列设有整数序列47,23,56,15,26,89,将其中的值依次将其中的值依次插入二叉排序树插入二叉排序树568947231526第18页/共61页 删除操作：删除操作：一个结点被删除后，必须保证余下的结点仍然构成一一个结点被删除后，必须保证余下的结点仍然构成一棵二叉排序树。下面分两种情况讨论：棵二叉排序树。下面分两种情况讨论：u 情况一：被删除的结点至少有一棵空子树情况一：被删除的结点至少有一棵空子树方法：使被删结点的那棵非空子树的根成为其双方法：使被删结点的那棵非空子树的根成为其双亲结点的相应子女亲结点的相应

11、子女50302510153533375362605553625550301015353337第19页/共61页u 情况二：被删除的结点有两棵非空的子树情况二：被删除的结点有两棵非空的子树方法一：找到被删除结点在中序遍历序列中的直接方法一：找到被删除结点在中序遍历序列中的直接后继结点（它一定在被删除结点的右子树中），用后继结点（它一定在被删除结点的右子树中），用此后继结点的值取代被删除结点的值，然后删除此此后继结点的值取代被删除结点的值，然后删除此后继结点，由于被删除的后继结点的左子树一定是后继结点，由于被删除的后继结点的左子树一定是空子树，所以删除后继结点的过程同情况一。空子树，所以删除后继结

12、点的过程同情况一。方法二：用被删除结点在中序遍历序列中的直接方法二：用被删除结点在中序遍历序列中的直接前驱结点（该结点的右子树也一定为空）代替被前驱结点（该结点的右子树也一定为空）代替被删除的结点，然后删除这个前驱结点。删除的结点，然后删除这个前驱结点。第20页/共61页50301015353337536255533010153533376255373010153533536255后继结点后继结点前驱结点前驱结点 将结点将结点50删除删除第21页/共61页 中序遍历：中序遍历：5030101535333753625510153033353750535562第22页/共61页 查找操作：查找操作

13、：对二叉排序树进行中序遍历可以得到一个数据元素由小对二叉排序树进行中序遍历可以得到一个数据元素由小到大的有序序列。构造二叉排序树的过程即为对无序序到大的有序序列。构造二叉排序树的过程即为对无序序列进行排序的过程。列进行排序的过程。u 查找查找思路：思路：当二叉排序树不为空时，将给定值与根结点的值进行当二叉排序树不为空时，将给定值与根结点的值进行比较，若相等则查找成功。如果给定值小于根结点的比较，若相等则查找成功。如果给定值小于根结点的值，则在根结点的左子树中继续查找，否则在根结点值，则在根结点的左子树中继续查找，否则在根结点的右子树中继续查找。当待查找的二叉排序树为空时，的右子树中继续查找。当

14、待查找的二叉排序树为空时，查找失败。查找失败。u 平均查找长度：平均查找长度：在二叉排序树中查找成功时走过的是一条从根结点到所寻找结点的一条路径，因此，二叉排序树查找的平均查找长度取决于二叉排序树的深度。第23页/共61页 二叉排序树的蜕变：二叉排序树的蜕变：二叉排序树是动态生成的，它的形态与各结点插入二叉二叉排序树是动态生成的，它的形态与各结点插入二叉排序树时的先后顺序有关。当把一组有序值依次插入到排序树时的先后顺序有关。当把一组有序值依次插入到一棵二叉排序树时，生成的二叉排序树将蜕变成一棵单一棵二叉排序树时，生成的二叉排序树将蜕变成一棵单支树。例如，由整数序列支树。例如，由整数序列15,2

15、3,26,47,56,89 生成的二生成的二叉排序树就是一棵单支树。在单支树中查找时，平均查叉排序树就是一棵单支树。在单支树中查找时，平均查找长度与顺序查找相同。找长度与顺序查找相同。第24页/共61页6.哈希查找哈希查找 哈希存储哈希存储(哈希表哈希表)：以数据元素的关键字以数据元素的关键字k为自变量，通过一定的函数关系为自变量，通过一定的函数关系h(称为哈希函数或散列函数称为哈希函数或散列函数)计算出对应的函数值计算出对应的函数值h(k)，把这个值解释为数据元素的存储地址并把数据元素存储把这个值解释为数据元素的存储地址并把数据元素存储到相应的存储单元内。到相应的存储单元内。h(k)称为哈希

16、地址。称为哈希地址。冲突：冲突：若有两个不同的关键字若有两个不同的关键字ki和和kj，即，即ki kj(i j)。但。但h(ki)=h(kj)，这种情况称为冲突。如上例的关键字，这种情况称为冲突。如上例的关键字85和和49，其，其对应的哈希地址都为对应的哈希地址都为1，即产生冲突。，即产生冲突。例：设有一组关键字值例：设有一组关键字值85,72,49,58,15,70,90,38，哈，哈希函数希函数h(k)=k mod 12。则对应的哈希地址为。则对应的哈希地址为1,0,1,10,3,10,6,2第25页/共61页 采用哈希技术要解决的两个主要问题：采用哈希技术要解决的两个主要问题：u 构造一

17、个好的哈希函数，使出现冲突的机会尽可能构造一个好的哈希函数，使出现冲突的机会尽可能少些；少些；u 设计一个有效的解决冲突的办法设计一个有效的解决冲突的办法第26页/共61页 哈希函数的构造方法哈希函数的构造方法u 构造哈希函数要考虑以下几点构造哈希函数要考虑以下几点1)哈希函数的哈希函数的定义域定义域必须包括要存储的数据元素必须包括要存储的数据元素的全部关键字的全部关键字;而如果散列表允许有而如果散列表允许有 m 个地址，个地址，则哈希函数的则哈希函数的值域值域必须在必须在 0 到到 m-1 之间之间2)由哈希函数计算出的地址应由哈希函数计算出的地址应均匀分布均匀分布在散列地在散列地址空间内址

18、空间内3)哈希函数应该是简单的，能在哈希函数应该是简单的，能在较短时间较短时间内计算内计算出结果出结果第27页/共61页p 直接定位法直接定位法取关键字的某个线性函数作为哈希函数，即取关键字的某个线性函数作为哈希函数，即h(k)=ak+b。其中，。其中，k为关键字，为关键字，a、b为常数。为常数。u 常用哈希函数常用哈希函数p 数学分析法数学分析法当关键字的位数比存储区域地址码的位数多时，可以当关键字的位数比存储区域地址码的位数多时，可以取关键字中位值分布比较均匀的若干位作为哈希函数取关键字中位值分布比较均匀的若干位作为哈希函数的值。这种方法适合于所有关键字为已知的情况。的值。这种方法适合于所

19、有关键字为已知的情况。p 除留余数法除留余数法选择一个适当的正整数选择一个适当的正整数p(p通常选为不大于哈希表长通常选为不大于哈希表长度度 m 的最大素数），用的最大素数），用p去除关键字，取其余数作为去除关键字，取其余数作为哈希地址，即哈希地址，即h(k)=k%p(pm)。第28页/共61页 解决冲突的方法：开放地址法和链地址法解决冲突的方法：开放地址法和链地址法u 开放地址法开放地址法当冲突发生时形成一个地址序列，按序列顺序逐个检当冲突发生时形成一个地址序列，按序列顺序逐个检查各地址单元，直至找到一个未被占用的单元为止，查各地址单元，直至找到一个未被占用的单元为止，将发生冲突的数据元素存

20、入该地址单元中。将发生冲突的数据元素存入该地址单元中。线性探查序列线性探查序列 平方探查序列平方探查序列设哈希表的长度是设哈希表的长度是m，发生冲突的地址是，发生冲突的地址是dd+1,d+2,m-1,0,1,d-1(d+12)%m,(d-12)%m,(d+22)%m,(d-22)%m,第29页/共61页p 例例1线性探查法建立哈希表线性探查法建立哈希表第30页/共61页设哈希表的长度设哈希表的长度11，哈希函数是，哈希函数是h(k)=k%11，将，将整数序列整数序列54,77,94,89,14,45,76存入哈希表。按平存入哈希表。按平方探查法处理冲突方探查法处理冲突p 例例201234567

21、89105477948954%11=1077%11=094%11=689%11=114%11=345%11=1(冲突)76%11=10(冲突)144576第31页/共61页u 链地址法链地址法将哈希地址相同的数据元素存储到同一个单链表中，将哈希地址相同的数据元素存储到同一个单链表中，哈希表中的每个存储单元中不再存放数据元素而是存哈希表中的每个存储单元中不再存放数据元素而是存放相应单链表的头指针放相应单链表的头指针第32页/共61页14.2 排序排序1.排序的基本概念排序的基本概念 排序：排序：将文件中的记录按排序码非递减将文件中的记录按排序码非递减(或非递增或非递增)的的顺序重新排列顺序重新排

22、列 排序码排序码：数据元素中的一个或多个数据项。排序码可数据元素中的一个或多个数据项。排序码可以是关键字，也可以是其他若干数据项的组合。以是关键字，也可以是其他若干数据项的组合。排序算法的稳定性排序算法的稳定性：如果在待排序的元素序列中，存如果在待排序的元素序列中，存在着多个排序码相同的元素，按照某种排序算法排序在着多个排序码相同的元素，按照某种排序算法排序后，这些元素的相对位置仍保持不变，则称该排序算后，这些元素的相对位置仍保持不变，则称该排序算法是稳定的，否则就是不稳定的。法是稳定的，否则就是不稳定的。第33页/共61页2.插入排序插入排序 基本思想：基本思想：把元素把元素ei(0in)依

23、次插入到由依次插入到由S中前中前i个个元素组成的已经排好序的序列元素组成的已经排好序的序列e0,e1,ei-1的适当位的适当位置上，插入后置上，插入后S的前的前i+1个元素仍为有序。个元素仍为有序。第34页/共61页 直接插入排序：直接插入排序：以顺序查找的办法找到要插入的元素在已排好以顺序查找的办法找到要插入的元素在已排好序的元素序列中应处的位置。序的元素序列中应处的位置。所有元素分成所有元素分成2个集合：已排序记录集和待排序个集合：已排序记录集和待排序记录集。初始时，已排序记录集只有一个元素，记录集。初始时，已排序记录集只有一个元素，即即e0，待排序记录集是所有剩余元素。然后每，待排序记录

24、集是所有剩余元素。然后每次从待排序记录集中选取一个元素，使用顺序次从待排序记录集中选取一个元素，使用顺序查找的方法，找到其在已排序记录集中的位置，查找的方法，找到其在已排序记录集中的位置，将其插入到该位置，直到待排序记录集为空。将其插入到该位置，直到待排序记录集为空。第35页/共61页 例：例：待排序记录为待排序记录为50,20,75,34,403440752050第36页/共61页 直接插入排序的函数示例：直接插入排序的函数示例：第37页/共61页 算法分析：算法分析：直接插入排序的平均时间复杂度是直接插入排序的平均时间复杂度是O(n2)直接插入排序是稳定的排序算法直接插入排序是稳定的排序算

25、法 对于一个长度较短、接近有序的序列，直接插对于一个长度较短、接近有序的序列，直接插入排序是十分有效的入排序是十分有效的在插入在插入ei时，时，e0,e1,ei-1是一个有序序列，所是一个有序序列，所以可以用二分查找法寻找以可以用二分查找法寻找ei的插入位置，从而减的插入位置，从而减少比较次数。少比较次数。二分插入排序是稳定的排序算法，其平均时间复二分插入排序是稳定的排序算法，其平均时间复杂度仍是杂度仍是O(n2)二分插入排序：二分插入排序：第38页/共61页3.选择排序选择排序 基本思想：基本思想：把元素把元素ei(0in)依次插入到由依次插入到由S中前中前i个个元素组成的已经排好序的序列元

26、素组成的已经排好序的序列e0,e1,ei-1的适当位的适当位置上，插入后置上，插入后S的前的前i+1个元素仍为有序。个元素仍为有序。在初始时，已排好序的元素序列为空，待排序的元素在初始时，已排好序的元素序列为空，待排序的元素序列中包括了需要排序的所有元素序列中包括了需要排序的所有元素第39页/共61页 直接选择排序：直接选择排序：基本思想：基本思想：用逐个比较的办法从待排序的元素序列用逐个比较的办法从待排序的元素序列中选出最小的元素。依次对中选出最小的元素。依次对i=0,1,2,n-2分别执行分别执行如下的选择和交换步骤：在元素序列如下的选择和交换步骤：在元素序列ei,ei+1,en-1中中选

27、择出最小的元素选择出最小的元素ek；当；当ki时，交换时，交换ei与与ek的值。经上的值。经上述述n-1次的选择和交换后，排序工作即已完成。次的选择和交换后，排序工作即已完成。第40页/共61页 直接选择排序函数模板：直接选择排序函数模板：直接选择排序算法是不稳定算法，其平均时间复杂直接选择排序算法是不稳定算法，其平均时间复杂度为度为O(n2)第41页/共61页 演示：演示：第42页/共61页 树形选择排序：树形选择排序：基本思想：基本思想：首先对首先对n个待排序元素的排序码两两进行比较，个待排序元素的排序码两两进行比较，得到得到 个比较的优胜者（排序码较小者），然后对个比较的优胜者（排序码较

28、小者），然后对这些优胜者再进行两两比较，如此反复，直至选出排这些优胜者再进行两两比较，如此反复，直至选出排序码最小的元素。序码最小的元素。在下一步选择排序码为次小的元素时，只需把在下一步选择排序码为次小的元素时，只需把树当中与已选出元素对应的叶结点的值设置为最大树当中与已选出元素对应的叶结点的值设置为最大（），并从该叶结点开始和其兄弟结点进行比较，修），并从该叶结点开始和其兄弟结点进行比较，修改从该叶结点到根结点路径上各结点的值，即可选出改从该叶结点到根结点路径上各结点的值，即可选出排序码次小的元素。排序码次小的元素。算法的时间复杂度算法的时间复杂度O(nlog2n)，该算法是稳定的。，该算法

29、是稳定的。第43页/共61页 堆排序：堆排序：基本思想：基本思想：首先，用需要排序的元素的排序码构造一个堆首先，用需要排序的元素的排序码构造一个堆（称为建堆），这样就可以找到排序码最小的元素，（称为建堆），这样就可以找到排序码最小的元素，将其取出；然后，用剩下的排序码继续建堆。如此反将其取出；然后，用剩下的排序码继续建堆。如此反复进行直至全部元素有序。复进行直至全部元素有序。堆是一棵完全二叉树，其中每个分支结点的值均小于或堆是一棵完全二叉树，其中每个分支结点的值均小于或等于左、右子女的值。位于堆顶位置的结点（即完全二等于左、右子女的值。位于堆顶位置的结点（即完全二叉树的根结点）的值是最小的。叉

30、树的根结点）的值是最小的。堆排序的关键步骤有两个：一是建立初始堆；堆排序的关键步骤有两个：一是建立初始堆；二是在取出堆顶后把剩余的结点调整为堆。二是在取出堆顶后把剩余的结点调整为堆。第44页/共61页首先，把所有元素的排序码组织到一棵完全二叉树首先，把所有元素的排序码组织到一棵完全二叉树中。然后从完全二叉树中结点编号排在最后的那个中。然后从完全二叉树中结点编号排在最后的那个分支分支结结点点km()开始，逐步地把以开始，逐步地把以km、km-1、km-2为根的子树建成堆，最后，当以为根的子树建成堆，最后，当以k0（k0是完全二叉树是完全二叉树的根结点）为根的完全二叉树也是堆时，整个建堆过程也的根

31、结点）为根的完全二叉树也是堆时，整个建堆过程也就完成了。就完成了。建立初始堆：建立初始堆：考虑以考虑以ki为根的子树，设为根的子树，设ki的左、右子树均已是堆。的左、右子树均已是堆。为将该子树也调整为堆，只需将为将该子树也调整为堆，只需将ki与其左子女与其左子女k2i+1和右子女和右子女k2i+2进行比较。如果进行比较。如果kik2i+1且且kik2i+2，则以，则以ki为根的子树为根的子树已经是堆。否则，将已经是堆。否则，将ki与其最小的那个子结点（不妨设为与其最小的那个子结点（不妨设为k2i+1）交换位置。交换后，在以）交换位置。交换后，在以ki为根的子树中，除了与其为根的子树中，除了与其

32、交换位置的子树外，其余部分均满足堆的定义，而以交换位置的子树外，其余部分均满足堆的定义，而以k2i+1（其值由于与（其值由于与ki交换已发生了变化）为根的子树的左、右子交换已发生了变化）为根的子树的左、右子树原来已经是堆，这样可使用前述过程将以树原来已经是堆，这样可使用前述过程将以k2i+1为根的子为根的子树调整为堆。如此递推下去，即可完成建堆工作。树调整为堆。如此递推下去，即可完成建堆工作。第45页/共61页 建立初始堆示例：建立初始堆示例：无需交换取最小第46页/共61页取出堆顶后将剩余结点调整为堆：取出堆顶后将剩余结点调整为堆：堆建成后，从堆顶取走值最小的结点，然后将最堆建成后，从堆顶取

33、走值最小的结点，然后将最后一个结点后一个结点kn-1提升到根结点的位置上，得到一棵新的完提升到根结点的位置上，得到一棵新的完全二叉树。虽然这棵二叉树可能不是堆，但其左、右子全二叉树。虽然这棵二叉树可能不是堆，但其左、右子树都是堆。因此，当把此二叉树调整为堆时，只需从根树都是堆。因此，当把此二叉树调整为堆时，只需从根结点开始自上而下地进行调整即可。结点开始自上而下地进行调整即可。具体示例见教材图具体示例见教材图14.10第47页/共61页子树调整为堆的模板函数：子树调整为堆的模板函数：第48页/共61页演示演示第49页/共61页 算法分析：算法分析：堆排序算法的时间复杂度为堆排序算法的时间复杂度

34、为O(nlog2n)堆排序算法是不稳定的堆排序算法是不稳定的 如果需要排序的元素数目较少一般并不提倡使如果需要排序的元素数目较少一般并不提倡使用堆排序算法，但如果元素数目较多，堆排序算用堆排序算法，但如果元素数目较多，堆排序算法还是很有效的法还是很有效的第50页/共61页 冒泡排序：冒泡排序：设待排序的元素序列为设待排序的元素序列为S=e0,e1,en-1，要求按升，要求按升序排列序排列 基本思想：基本思想：从待排序记录集的一端（这里假定为低端）对从待排序记录集的一端（这里假定为低端）对相邻的两个元素（相邻的两个元素（e0和和e1，e1和和e2，en-2和和en-1）依次比较它们的排序码，若不

35、符合排序的顺序要求，依次比较它们的排序码，若不符合排序的顺序要求，就将相应的两个元素互换，此过程称为一趟冒泡排序，就将相应的两个元素互换，此过程称为一趟冒泡排序，最多经过最多经过n-1趟冒泡排序，排序工作即可完成。趟冒泡排序，排序工作即可完成。每趟排序的结果是将待排序记录集中排序码最每趟排序的结果是将待排序记录集中排序码最大的元素交换到待排序记录集最后一个元素的位置。大的元素交换到待排序记录集最后一个元素的位置。假设在一趟冒泡排序时，从假设在一趟冒泡排序时，从ej+1以后没有发生元素的互以后没有发生元素的互换，则说明换，则说明ej+1以后的元素是已经排好序的，下面只需以后的元素是已经排好序的，

36、下面只需要在要在e0到到ej范围内进行新一趟的冒泡排序，即待排序记范围内进行新一趟的冒泡排序，即待排序记录集是从录集是从e0到到ej，下一趟只需从，下一趟只需从e0到到ej范围内进行。范围内进行。第51页/共61页97275813496576待排序记录LastExchangeIndex279758134965762758971349657627581397496576275813499765762758134965977627581349657697待排序记录第一趟排序结束27581349657697待排序记录已排序记录第52页/共61页27581349657697待排序记录275813496

37、5769727135849657697271349586576972713495865769727134958657697第二趟排序结束待排序记录27134958657697待排序记录已排序记录第53页/共61页 冒泡排序函数模板：冒泡排序函数模板：第54页/共61页 算法分析：算法分析：最好情况下的时间复杂度为最好情况下的时间复杂度为O(n)。若待排序元素。若待排序元素序列已经有序，则排序工作经一趟处理就可结束。此序列已经有序，则排序工作经一趟处理就可结束。此时，对元素排序码的比较次数为最小值时，对元素排序码的比较次数为最小值n-1，且没有，且没有元素的互换。元素的互换。最坏最坏情况下的情况

38、下的时间复杂度为时间复杂度为O(n2)。若待排序元。若待排序元素序列为逆序，则需要进行素序列为逆序，则需要进行n-1趟冒泡。每趟要进行趟冒泡。每趟要进行n-i-1次排序码的比较和次排序码的比较和n-i-1次元素的互换次元素的互换 冒泡排序算法是稳定的冒泡排序算法是稳定的第55页/共61页 快速排序：快速排序：基本思想：基本思想：从待排序的个元素中任取一个元素，以该元从待排序的个元素中任取一个元素，以该元素为基准，用交换的方法将剩下的元素分成两组。第素为基准，用交换的方法将剩下的元素分成两组。第组中各元素的排序码均小于或等于基准元素的排序组中各元素的排序码均小于或等于基准元素的排序码；第组中各元

39、素的排序码均大于基准元素的排序码；第组中各元素的排序码均大于基准元素的排序码。把基准元素放到两组元素之间（这也是基准元素码。把基准元素放到两组元素之间（这也是基准元素在最后排好序的元素序列中的最终位置）。以上过程在最后排好序的元素序列中的最终位置）。以上过程称为一趟快速排序（或一次划分）。称为一趟快速排序（或一次划分）。对划分出的两组元素重复上述过程，直到所有对划分出的两组元素重复上述过程，直到所有元素都排列到最终位置为止。元素都排列到最终位置为止。第56页/共61页71381578基准ScanUpScanDown614533694052一趟排序结束第57页/共61页 实现快速排序的函数模板：实现快速排序的函数模板：第58页/共61页 算法分析：算法分析：最坏的时间复杂度为最坏的时间复杂度为O(n2)，最好的时间复杂度为，最好的时间复杂度为O(nlog2n)。平均时间复杂度也是平均时间复杂度也是O(nlog2n)，具体，具体分析分析 见教材见教材 目前基于比较的排序算法中速度最快的目前基于比较的排序算法中速度最快的，快速排，快速排序算法是不稳定的序算法是不稳定的 C+标准库标准库中的函数模板采用的是快中的函数模板采用的是快速排序算法速排序算法第59页/共61页第60页/共61页感谢您的欣赏！第61页/共61页