1、本章课件制作：吴虎统第三部分第三部分 数据结构基础数据结构基础本章内容本章内容 查找查找 排序排序14.1 查找查找1. 查找的基本概念查找的基本概念 查找：查找：在数据元素集合在数据元素集合(查找表查找表)中查找关键字与中查找关键字与给定值相等的数据元素。给定值相等的数据元素。 关键字关键字：数据元素中的一个或多个数据项值，它数据元素中的一个或多个数据项值，它可以惟一标识一个数据元素。可以惟一标识一个数据元素。 平均查找长度平均查找长度(ASL)：iniiCPASL1式中，式中，n为查找表的长度；为查找表的长度；pi为查找第为查找第i个元素的概个元素的概率，在等概率情况下率，在等概率情况下p
2、i等于等于1/n； Ci为找到第为找到第i个元个元素时的比较次数素时的比较次数2. 顺序查找顺序查找 基本思想：基本思想：用给定值依次与线性表中每个元素的用给定值依次与线性表中每个元素的关键字进行比较。如果某个元素的关键字与给定值关键字进行比较。如果某个元素的关键字与给定值相同，则查找成功；如果找遍全表也没有发现满足相同，则查找成功；如果找遍全表也没有发现满足条件的元素，则查找失败。条件的元素，则查找失败。 要求：要求： 查找表必须采用线性表。查找表必须采用线性表。 实现一：顺序表类中实现顺序查找的成员函数实现一：顺序表类中实现顺序查找的成员函数/找到值为找到值为item的元素并返回其下标，若
3、元素不存在，的元素并返回其下标，若元素不存在，/则返回则返回-1int Seqlist:Find(int item) int i=0; if(ListEmpty() return -1; while(isize & item != listi) i+; if(inext; while(p != NULL) if(p-data = item) break; p=p-next; return p; 顺序查找的平均查找长度顺序查找的平均查找长度)(21111nOninCPASLniinii 评价：评价：在用顺序查找方法完成查找时，每进行一在用顺序查找方法完成查找时，每进行一次成功查找需要的平均比较次
4、数约为表长度的一半，次成功查找需要的平均比较次数约为表长度的一半，因此，它的效率较低。适用于在查找表较小的情况因此，它的效率较低。适用于在查找表较小的情况下进行查找。下进行查找。3. 二分查找二分查找要求：要求： u查找表必须采用线性表；查找表必须采用线性表；u必须以顺序方式存储线性表；必须以顺序方式存储线性表；u线性表中所有数据元素必须按照关键字有序排列线性表中所有数据元素必须按照关键字有序排列 基本思想：基本思想：将给定值与处于顺序表将给定值与处于顺序表“中间位置中间位置”上的元素的关键字进行比较，若相等则查找成功，上的元素的关键字进行比较，若相等则查找成功，若给定值大于关键字则在表的后半
5、部分继续进行二若给定值大于关键字则在表的后半部分继续进行二分查找，否则在表的前半部分继续进行二分查找。分查找，否则在表的前半部分继续进行二分查找。如此进行下去直至找到满足条件的元素，或当前查如此进行下去直至找到满足条件的元素，或当前查找区为空，此时查找失败。找区为空，此时查找失败。演示：演示： 例子：例子：二分查找函数模板及其测试程序二分查找函数模板及其测试程序#include template int BinSearch(T A,int low,int high,T key)int mid;while(low=high)mid=(low+high)/2;if(key=Amid) return
6、 mid;/查找查找if(keyAmid)high=mid-1;/到表的前到表的前else low=mid+1;/到表的后半部到表的后半部return -1;/查找失败，返查找失败，返void main()int a=1,2,3,4,5,6,7,8,k=7,i;i=BinSearch(a,0,7,k);if(i=-1)cout”没找到！没找到！n”;else coutiendl;优点：优点： u查找效率高查找效率高u平均查找长度平均查找长度)(log1) 1(log12122111nOnnnjnCPASLjkjinii缺点：缺点： u查找前要将表中元素按关键字有序排列查找前要将表中元素按关键字
7、有序排列u只适用于线性表的顺序存储。适用于那种一经建只适用于线性表的顺序存储。适用于那种一经建立就很少改动而又经常需要查找的线性表。立就很少改动而又经常需要查找的线性表。4. 分块查找分块查找要求：要求： u查找表必须采用线性表；查找表必须采用线性表；u待查找的线性表分成若干块。在每一块内，元素待查找的线性表分成若干块。在每一块内，元素的存放是任意的，但在块与块之间元素的存放是有的存放是任意的，但在块与块之间元素的存放是有序的，即前一块中任意一个元素的关键字值都必须序的，即前一块中任意一个元素的关键字值都必须小于（或大于）后一块中所有元素的关键字值；小于（或大于）后一块中所有元素的关键字值；u
8、建立一个索引表，索引表中的每个索引项对应于建立一个索引表，索引表中的每个索引项对应于一块。一个索引项至少应含有两部分信息：一是对一块。一个索引项至少应含有两部分信息：一是对应块中最大的关键字值；二是指向对应块中第一个应块中最大的关键字值；二是指向对应块中第一个元素的指针元素的指针 基本思想：基本思想：首先在索引表中查找，确定出要查找首先在索引表中查找，确定出要查找的元素应该在哪一块中；然后在已确定的那一块内的元素应该在哪一块中；然后在已确定的那一块内进行顺序查找。进行顺序查找。 演示：演示： 优点：优点：块内元素是任意存放的，插入或删除运算块内元素是任意存放的，插入或删除运算不会造成元素的大量
9、移动。不会造成元素的大量移动。 缺点：缺点：u增加了存放索引表的辅助空间及初始时对线性表增加了存放索引表的辅助空间及初始时对线性表分块排序的运算分块排序的运算u大量的插入和删除运算可能会导致各块中元素的大量的插入和删除运算可能会导致各块中元素的数目很不均匀，这会降低查找速度数目很不均匀，这会降低查找速度 平均查找长度：平均查找长度：将长度为将长度为n的线性表均匀地划分的线性表均匀地划分成块，每块中有个结点，即。假定成块，每块中有个结点，即。假定对表中每个元素的查找概率相等，则查找某一块的对表中每个元素的查找概率相等，则查找某一块的概率为，查找块中某个结点的概率为概率为，查找块中某个结点的概率为
10、12212111211ssnsbisjbASLsibj 索引表使用顺序查找：索引表使用顺序查找： 索引表使用二分查找：索引表使用二分查找：2) 1(log2ssnASL5. 二叉排序树查找二叉排序树查找 二叉排序树的定义：二叉排序树的定义：二叉排序树或者是一棵空二叉树，或者是具有以下二叉排序树或者是一棵空二叉树，或者是具有以下性质的二叉树：性质的二叉树：1、若它的、若它的左子树左子树非空，则左子树上所有结点的值非空，则左子树上所有结点的值均均小于小于根结点的值；根结点的值；2、若它的、若它的右子树右子树非空，则右子树上所有结点的值非空，则右子树上所有结点的值均均不小于不小于根结点的值；根结点的
11、值；3、左、右子树本身又各是一棵二叉排序树。、左、右子树本身又各是一棵二叉排序树。 插入操作：插入操作：若二叉排序树为空，则新结点为二叉排序树的根若二叉排序树为空，则新结点为二叉排序树的根结点；否则将新结点的关键字值和根结点的关键结点；否则将新结点的关键字值和根结点的关键字值进行比较，若小于根结点的值，则将新结点字值进行比较，若小于根结点的值，则将新结点插入到左子树中去，否则，插入到右子树中去。插入到左子树中去，否则，插入到右子树中去。此插入过程是递归进行的。此插入过程是递归进行的。 设有整数序列设有整数序列47,23,56,15,26,89,将其中的值依次将其中的值依次插入二叉排序树插入二叉
12、排序树568947231526 删除操作：删除操作：一个结点被删除后，必须保证余下的结点仍然构成一一个结点被删除后，必须保证余下的结点仍然构成一棵二叉排序树。下面分两种情况讨论：棵二叉排序树。下面分两种情况讨论：u 情况一：被删除的结点至少有一棵空子树情况一：被删除的结点至少有一棵空子树方法：使被删结点的那棵非空子树的根成为其双方法：使被删结点的那棵非空子树的根成为其双亲结点的相应子女亲结点的相应子女50302510153533375362605553625550301015353337u 情况二：被删除的结点有两棵非空的子树情况二：被删除的结点有两棵非空的子树方法一：找到被删除结点在中序遍历
13、序列中的直方法一：找到被删除结点在中序遍历序列中的直接后继结点（它一定在被删除结点的右子树中）接后继结点（它一定在被删除结点的右子树中），用此后继结点的值取代被删除结点的值，然后，用此后继结点的值取代被删除结点的值，然后删除此后继结点，由于被删除的后继结点的左子删除此后继结点，由于被删除的后继结点的左子树一定是空子树，所以删除后继结点的过程同情树一定是空子树，所以删除后继结点的过程同情况一。况一。方法二：用被删除结点在中序遍历序列中的直接方法二：用被删除结点在中序遍历序列中的直接前驱结点（该结点的右子树也一定为空）代替被前驱结点（该结点的右子树也一定为空）代替被删除的结点，然后删除这个前驱结点
14、。删除的结点，然后删除这个前驱结点。 50301015353337536255533010153533376255373010153533536255后继结点后继结点前驱结点前驱结点 将结点将结点50删除删除 中序遍历：中序遍历：5030101535333753625510153033353750535562 查找操作：查找操作：对二叉排序树进行中序遍历可以得到一个数据元素由小对二叉排序树进行中序遍历可以得到一个数据元素由小到大的有序序列。构造二叉排序树的过程即为对无序序到大的有序序列。构造二叉排序树的过程即为对无序序列进行排序的过程。列进行排序的过程。u 查找查找思路：思路：当二叉排序树不为
15、空时，将给定值与根结点的值进行当二叉排序树不为空时，将给定值与根结点的值进行比较，若相等则查找成功。如果给定值小于根结点的比较，若相等则查找成功。如果给定值小于根结点的值，则在根结点的左子树中继续查找，否则在根结点值，则在根结点的左子树中继续查找，否则在根结点的右子树中继续查找。当待查找的二叉排序树为空时的右子树中继续查找。当待查找的二叉排序树为空时，查找失败。，查找失败。u 平均查找长度：平均查找长度：)(log2nOASL 在二叉排序树中查找成功时走过的是一条从根结点到所寻找结点的一条路径，因此，二叉排序树查找的平均查找长度取决于二叉排序树的深度。 二叉排序树的蜕变：二叉排序树的蜕变：二叉
16、排序树是动态生成的，它的形态与各结点插入二叉二叉排序树是动态生成的，它的形态与各结点插入二叉排序树时的先后顺序有关。当把一组有序值依次插入到排序树时的先后顺序有关。当把一组有序值依次插入到一棵二叉排序树时，生成的二叉排序树将蜕变成一棵单一棵二叉排序树时，生成的二叉排序树将蜕变成一棵单支树。例如，由整数序列支树。例如，由整数序列15,23,26,47,56,89 生成的二生成的二叉排序树就是一棵单支树。在单支树中查找时，平均查叉排序树就是一棵单支树。在单支树中查找时，平均查找长度与顺序查找相同。找长度与顺序查找相同。6. 哈希查找哈希查找 哈希存储哈希存储(哈希表哈希表)：以数据元素的关键字以数
17、据元素的关键字k为自变量，通过一定的函数关系为自变量，通过一定的函数关系h(称为哈希函数或散列函数称为哈希函数或散列函数)计算出对应的函数值计算出对应的函数值h(k)，把这个值解释为数据元素的存储地址并把数据元素存储把这个值解释为数据元素的存储地址并把数据元素存储到相应的存储单元内。到相应的存储单元内。h(k)称为哈希地址。称为哈希地址。 冲突：冲突：若有两个不同的关键字若有两个不同的关键字ki和和kj，即，即ki kj(i j)。但。但h(ki)=h(kj)，这种情况称为冲突。如上例的关键字，这种情况称为冲突。如上例的关键字85和和49，其对应的哈希地址都为，其对应的哈希地址都为1，即产生冲
18、突。，即产生冲突。例：设有一组关键字值例：设有一组关键字值85,72,49,58,15,70,90,38，哈，哈希函数希函数h(k) = k mod 12。则对应的哈希地址为。则对应的哈希地址为1,0,1,10,3,10,6,2 采用哈希技术要解决的两个主要问题：采用哈希技术要解决的两个主要问题：u 构造一个好的哈希函数，使出现冲突的机会尽可能构造一个好的哈希函数，使出现冲突的机会尽可能少些；少些；u 设计一个有效的解决冲突的办法设计一个有效的解决冲突的办法 哈希函数的构造方法哈希函数的构造方法u 构造哈希函数要考虑以下几点构造哈希函数要考虑以下几点1) 哈希函数的哈希函数的定义域定义域必须包
19、括要存储的数据元素必须包括要存储的数据元素的全部关键字的全部关键字; 而如果散列表允许有而如果散列表允许有 m 个地址，个地址，则哈希函数的则哈希函数的值域值域必须在必须在 0 到到 m-1 之间之间2)由哈希函数计算出的地址应由哈希函数计算出的地址应均匀分布均匀分布在散列地在散列地址空间内址空间内3)哈希函数应该是简单的，能在哈希函数应该是简单的，能在较短时间较短时间内计算内计算出结果出结果p 直接定位法直接定位法取关键字的某个线性函数作为哈希函数，即取关键字的某个线性函数作为哈希函数，即h(k)=ak+b。其中，。其中，k为关键字，为关键字，a、b为常数。为常数。u 常用哈希函数常用哈希函
20、数p 数学分析法数学分析法当关键字的位数比存储区域地址码的位数多时，可以当关键字的位数比存储区域地址码的位数多时，可以取关键字中位值分布比较均匀的若干位作为哈希函数取关键字中位值分布比较均匀的若干位作为哈希函数的值。这种方法适合于所有关键字为已知的情况。的值。这种方法适合于所有关键字为已知的情况。p 除留余数法除留余数法选择一个适当的正整数选择一个适当的正整数p (p通常选为不大于哈希表长通常选为不大于哈希表长度度 m 的最大素数），用的最大素数），用p去除关键字，取其余数作为去除关键字，取其余数作为哈希地址，即哈希地址，即h(k)=k%p (pm)。 解决冲突的方法：开放地址法和链地址法解决
21、冲突的方法：开放地址法和链地址法u 开放地址法开放地址法当冲突发生时形成一个地址序列，按序列顺序逐个当冲突发生时形成一个地址序列，按序列顺序逐个检查各地址单元，直至找到一个未被占用的单元为检查各地址单元，直至找到一个未被占用的单元为止，将发生冲突的数据元素存入该地址单元中。止，将发生冲突的数据元素存入该地址单元中。 线性探查序列线性探查序列 平方探查序列平方探查序列设哈希表的长度是设哈希表的长度是m，发生冲突的地址是，发生冲突的地址是dd+1, d+2, , m-1, 0, 1, , d-1(d+12)%m, (d-12)%m, (d+22)%m, (d-22)%m, p 例例1线性探查法建立
22、哈希表线性探查法建立哈希表设哈希表的长度设哈希表的长度11，哈希函数是，哈希函数是h(k) = k % 11，将，将整数序列整数序列54,77,94,89,14,45,76存入哈希表。按平存入哈希表。按平方探查法处理冲突方探查法处理冲突p 例例20123456789105477948954 % 11 = 1077 % 11 = 094 % 11 = 689 % 11 = 114 % 11 = 345 % 11 = 1 (冲突冲突)76 % 11 = 10 (冲突冲突)144576u 链地址法链地址法将哈希地址相同的数据元素存储到同一个单链表中，将哈希地址相同的数据元素存储到同一个单链表中，哈希
23、表中的每个存储单元中不再存放数据元素而是存哈希表中的每个存储单元中不再存放数据元素而是存放相应单链表的头指针放相应单链表的头指针14.2 排序排序1. 排序的基本概念排序的基本概念 排序：排序：将文件中的记录按排序码非递减将文件中的记录按排序码非递减(或非递增或非递增)的的顺序重新排列顺序重新排列 排序码排序码：数据元素中的一个或多个数据项。排序码可数据元素中的一个或多个数据项。排序码可以是关键字，也可以是其他若干数据项的组合。以是关键字，也可以是其他若干数据项的组合。 排序算法的稳定性排序算法的稳定性：如果在待排序的元素序列中，存如果在待排序的元素序列中，存在着多个排序码相同的元素，按照某种
24、排序算法排序在着多个排序码相同的元素，按照某种排序算法排序后，这些元素的相对位置仍保持不变，则称该排序算后，这些元素的相对位置仍保持不变，则称该排序算法是稳定的，否则就是不稳定的。法是稳定的，否则就是不稳定的。2. 插入排序插入排序 基本思想：基本思想：把元素把元素ei(0in) 依次插入到由依次插入到由S中前中前i个个元素组成的已经排好序的序列元素组成的已经排好序的序列e0, e1, ,ei-1的适当位的适当位置上，插入后置上，插入后S的前的前i+1个元素仍为有序。个元素仍为有序。 直接插入排序：直接插入排序：以顺序查找的办法找到要插入的元素在已排好以顺序查找的办法找到要插入的元素在已排好序
25、的元素序列中应处的位置。序的元素序列中应处的位置。所有元素分成所有元素分成2个集合：已排序记录集和待排序个集合：已排序记录集和待排序记录集。初始时，已排序记录集只有一个元素记录集。初始时，已排序记录集只有一个元素，即，即e0，待排序记录集是所有剩余元素。然后，待排序记录集是所有剩余元素。然后每次从待排序记录集中选取一个元素，使用顺每次从待排序记录集中选取一个元素，使用顺序查找的方法，找到其在已排序记录集中的位序查找的方法，找到其在已排序记录集中的位置，将其插入到该位置，直到待排序记录集为置，将其插入到该位置，直到待排序记录集为空。空。 例：例：待排序记录为待排序记录为50,20,75,34,4
26、03440752050 直接插入排序的函数示例：直接插入排序的函数示例：#include template void InsertionSort(T A,int n) /对对0Aint i,j;T temp;for(i=1;i0 & tempAj-1;j-)Aj=Aj-1;Aj=temp; 算法分析：算法分析： 直接插入排序的平均时间复杂度是直接插入排序的平均时间复杂度是O(n2) 直接插入排序是稳定的排序算法直接插入排序是稳定的排序算法 对于一个长度较短、接近有序的序列，直接插对于一个长度较短、接近有序的序列，直接插入排序是十分有效的入排序是十分有效的在插入在插入ei时，时，e0, e1,
27、, ei-1是一个有序序列，所是一个有序序列，所以可以用二分查找法寻找以可以用二分查找法寻找ei的插入位置，从而减的插入位置，从而减少比较次数。少比较次数。二分插入排序是稳定的排序算法，其平均时间复二分插入排序是稳定的排序算法，其平均时间复杂度仍是杂度仍是O(n2) 二分插入排序：二分插入排序：3. 选择排序选择排序 基本思想：基本思想：把元素把元素ei(0in) 依次插入到由依次插入到由S中前中前i个个元素组成的已经排好序的序列元素组成的已经排好序的序列e0, e1, ,ei-1的适当位的适当位置上，插入后置上，插入后S的前的前i+1个元素仍为有序。个元素仍为有序。在初始时，已排好序的元素序
28、列为空，待排序的元素在初始时，已排好序的元素序列为空，待排序的元素序列中包括了需要排序的所有元素序列中包括了需要排序的所有元素 直接选择排序：直接选择排序： 基本思想：基本思想：用逐个比较的办法从待排序的元素序列用逐个比较的办法从待排序的元素序列中选出最小的元素。依次对中选出最小的元素。依次对i=0, 1, 2, ,n-2分别执行分别执行如下的选择和交换步骤：在元素序列如下的选择和交换步骤：在元素序列ei, ei+1, , en-1中中选择出最小的元素选择出最小的元素ek；当；当ki时，交换时，交换ei与与ek的值。经的值。经上述上述n-1次的选择和交换后，排序工作即已完成。次的选择和交换后，
29、排序工作即已完成。 直接选择排序函数模板：直接选择排序函数模板：template void SelectionSort(T A,int n)/对对A0A int i,j,k,temp; for(i=0;in-1;i+) k=i;/假定假定Ai最小最小 for(j=i+1;jn;j+) if(AjAk) k=j; if(k!=i) temp=Ai; Ai=Ak; Ak=temp; 直接选择排序算法是不稳定算法，其平均时间复杂直接选择排序算法是不稳定算法，其平均时间复杂度为度为O(n2) 演示：演示： 树形选择排序：树形选择排序： 基本思想：基本思想：首先对首先对n个待排序元素的排序码两两进行比较
30、，个待排序元素的排序码两两进行比较，得到得到 个比较的优胜者（排序码较小者），然后对个比较的优胜者（排序码较小者），然后对这些优胜者再进行两两比较，如此反复，直至选出排这些优胜者再进行两两比较，如此反复，直至选出排序码最小的元素。序码最小的元素。在下一步选择排序码为次小的元素时，只需把在下一步选择排序码为次小的元素时，只需把树当中与已选出元素对应的叶结点的值设置为最大树当中与已选出元素对应的叶结点的值设置为最大（），并从该叶结点开始和其兄弟结点进行比较，修），并从该叶结点开始和其兄弟结点进行比较，修改从该叶结点到根结点路径上各结点的值，即可选出改从该叶结点到根结点路径上各结点的值，即可选出排序
31、码次小的元素。排序码次小的元素。2/n 算法的时间复杂度算法的时间复杂度O(nlog2n)，该算法是稳定的。，该算法是稳定的。 堆排序：堆排序： 基本思想：基本思想：首先，用需要排序的元素的排序码构造一个堆首先，用需要排序的元素的排序码构造一个堆（称为建堆），这样就可以找到排序码最小的元素，（称为建堆），这样就可以找到排序码最小的元素，将其取出；然后，用剩下的排序码继续建堆。如此反将其取出；然后，用剩下的排序码继续建堆。如此反复进行直至全部元素有序。复进行直至全部元素有序。堆是一棵完全二叉树，其中每个分支结点的值均小于或堆是一棵完全二叉树，其中每个分支结点的值均小于或等于左、右子女的值。位于堆
32、顶位置的结点（即完全二等于左、右子女的值。位于堆顶位置的结点（即完全二叉树的根结点）的值是最小的。叉树的根结点）的值是最小的。堆排序的关键步骤有两个：一是建立初始堆；堆排序的关键步骤有两个：一是建立初始堆；二是在取出堆顶后把剩余的结点调整为堆。二是在取出堆顶后把剩余的结点调整为堆。首先，把所有元素的排序码组织到一棵完全二叉树首先，把所有元素的排序码组织到一棵完全二叉树中。然后从完全二叉树中结点编号排在最后的那个中。然后从完全二叉树中结点编号排在最后的那个分支分支结结点点km( )开始，逐步地把以开始，逐步地把以km、km-1、km-2为根的子树建成堆，最后，当以为根的子树建成堆，最后，当以k0
33、（k0是完全二叉是完全二叉树的根结点）为根的完全二叉树也是堆时，整个建堆过程树的根结点）为根的完全二叉树也是堆时，整个建堆过程也就完成了。也就完成了。2/ )2( nm建立初始堆：建立初始堆：考虑以考虑以ki为根的子树，设为根的子树，设ki的左、右子树均已是堆。的左、右子树均已是堆。为将该子树也调整为堆，只需将为将该子树也调整为堆，只需将ki与其左子女与其左子女k2i+1和右子女和右子女k2i+2进行比较。如果进行比较。如果kik2i+1且且kik2i+2，则以，则以ki为根的子树为根的子树已经是堆。否则，将已经是堆。否则，将ki与其最小的那个子结点（不妨设为与其最小的那个子结点（不妨设为k2
34、i+1）交换位置。交换后，在以）交换位置。交换后，在以ki为根的子树中，除了与其为根的子树中，除了与其交换位置的子树外，其余部分均满足堆的定义，而以交换位置的子树外，其余部分均满足堆的定义，而以k2i+1（其值由于与（其值由于与ki交换已发生了变化）为根的子树的左、右交换已发生了变化）为根的子树的左、右子树原来已经是堆，这样可使用前述过程将以子树原来已经是堆，这样可使用前述过程将以k2i+1为根的为根的子树调整为堆。如此递推下去，即可完成建堆工作。子树调整为堆。如此递推下去，即可完成建堆工作。 建立初始堆示例：建立初始堆示例：无需交换取最小取出堆顶后将剩余结点调整为堆：取出堆顶后将剩余结点调整
35、为堆：堆建成后，从堆顶取走值最小的结点，然后将最堆建成后，从堆顶取走值最小的结点，然后将最后一个结点后一个结点kn-1提升到根结点的位置上，得到一棵新的提升到根结点的位置上，得到一棵新的完全二叉树。虽然这棵二叉树可能不是堆，但其左、右完全二叉树。虽然这棵二叉树可能不是堆，但其左、右子树都是堆。因此，当把此二叉树调整为堆时，只需从子树都是堆。因此，当把此二叉树调整为堆时，只需从根结点开始自上而下地进行调整即可。根结点开始自上而下地进行调整即可。具体示例见教材图具体示例见教材图14.10子树调整为堆的模板函数：子树调整为堆的模板函数：/假设有一棵完全二叉树，它有个结点且以顺序方式存储在假设有一棵完
36、全二叉树，它有个结点且以顺序方式存储在/一维数组一维数组A中。以编号的结点为根的子树不是堆，但该结点中。以编号的结点为根的子树不是堆，但该结点/的左、右子树都已是堆。将此子树调整为堆的左、右子树都已是堆。将此子树调整为堆template void FilterDown(T A,int i,int n) int current=i; int j=2*i+1; T temp=Ai; while(jn) if(jn-1 & Aj=Aj) break; else Acurrent=Aj; current=j; j=2*j+1; 演示演示 算法分析：算法分析： 堆排序算法的时间复杂度为堆排序算法的时间复
37、杂度为O(nlog2n) 堆排序算法是不稳定的堆排序算法是不稳定的 如果需要排序的元素数目较少一般并不提倡使如果需要排序的元素数目较少一般并不提倡使用堆排序算法，但如果元素数目较多，堆排序算用堆排序算法，但如果元素数目较多，堆排序算法还是很有效的法还是很有效的 冒泡排序：冒泡排序：设待排序的元素序列为设待排序的元素序列为S=e0, e1, , en-1，要求按升，要求按升序排列序排列 基本思想：基本思想：从待排序记录集的一端（这里假定为低端）对从待排序记录集的一端（这里假定为低端）对相邻的两个元素（相邻的两个元素（e0和和e1，e1和和e2，en-2和和en-1）依次比较它们的排序码，若不符合
38、排序的顺序要求，依次比较它们的排序码，若不符合排序的顺序要求，就将相应的两个元素互换，此过程称为一趟冒泡排序，就将相应的两个元素互换，此过程称为一趟冒泡排序，最多经过最多经过n-1趟冒泡排序，排序工作即可完成。趟冒泡排序，排序工作即可完成。每趟排序的结果是将待排序记录集中排序码最每趟排序的结果是将待排序记录集中排序码最大的元素交换到待排序记录集最后一个元素的位置。大的元素交换到待排序记录集最后一个元素的位置。假设在一趟冒泡排序时，从假设在一趟冒泡排序时，从ej+1以后没有发生元素的互以后没有发生元素的互换，则说明换，则说明ej+1以后的元素是已经排好序的，下面只需以后的元素是已经排好序的，下面
39、只需要在要在e0到到ej范围内进行新一趟的冒泡排序，即待排序范围内进行新一趟的冒泡排序，即待排序记录集是从记录集是从e0到到ej，下一趟只需从，下一趟只需从e0到到ej范围内进行。范围内进行。97275813496576待排序记录LastExchangeIndex279758134965762758971349657627581397496576275813499765762758134965977627581349657697待排序记录第一趟排序结束第一趟排序结束27581349657697待排序记录已排序记录27581349657697待排序记录2758134965769727135849
40、657697271349586576972713495865769727134958657697第二趟排序结束第二趟排序结束待排序记录27134958657697待排序记录已排序记录 冒泡排序函数模板：冒泡排序函数模板：template void BubbleSort(T A,int n) /对对A0An-1排序排序int i,j;int lastExchangeIndex;T temp;i=n-1; /i是待排序子表中最后一个元素的下标是待排序子表中最后一个元素的下标while(i0)lastExchangeIndex=0;for(j=0;ji;j+)if(Aj+1Aj)temp=Aj;Aj
41、=Aj+1;Aj+1=temp;lastExchangeIndex=j;i=lastExchangeIndex; 算法分析：算法分析： 最好情况下的时间复杂度为最好情况下的时间复杂度为O(n)。若待排序元素。若待排序元素序列已经有序，则排序工作经一趟处理就可结束。序列已经有序，则排序工作经一趟处理就可结束。此时，对元素排序码的比较次数为最小值此时，对元素排序码的比较次数为最小值n-1，且没，且没有元素的互换。有元素的互换。 最坏最坏情况下的情况下的时间复杂度为时间复杂度为O(n2)。若待排序元。若待排序元素序列为逆序，则需要进行素序列为逆序，则需要进行n-1趟冒泡。每趟要进行趟冒泡。每趟要进行
42、n-i-1次排序码的比较和次排序码的比较和n-i-1次元素的互换次元素的互换 冒泡排序算法是稳定的冒泡排序算法是稳定的 快速排序：快速排序： 基本思想：基本思想：从待排序的个元素中任取一个元素，以该元从待排序的个元素中任取一个元素，以该元素为基准，用交换的方法将剩下的元素分成两组。第素为基准，用交换的方法将剩下的元素分成两组。第组中各元素的排序码均小于或等于基准元素的排序组中各元素的排序码均小于或等于基准元素的排序码；第组中各元素的排序码均大于基准元素的排序码；第组中各元素的排序码均大于基准元素的排序码。把基准元素放到两组元素之间（这也是基准元素码。把基准元素放到两组元素之间（这也是基准元素在
43、最后排好序的元素序列中的最终位置）。以上过程在最后排好序的元素序列中的最终位置）。以上过程称为一趟快速排序（或一次划分）。称为一趟快速排序（或一次划分）。对划分出的两组元素重复上述过程，直到所有对划分出的两组元素重复上述过程，直到所有元素都排列到最终位置为止。元素都排列到最终位置为止。71381578基准2/ )(highlowmidScanUpScanDown614533694052一趟排序结束一趟排序结束 实现快速排序的函数模板：实现快速排序的函数模板：template void Swap(T &x,T &y)T temp=x;x=y;y=temp;template void QuickS
44、ort(T A,int low,int high)/对对AlowA T pivot;int scanUp,scanDown;int mid;if(high-low=0)return;elseif(high-low=1)if(AhighAlow)Swap(Alow,Ahigh);return; 算法分析：算法分析： 最坏的时间复杂度为最坏的时间复杂度为O(n2)，最好的时间复杂度为，最好的时间复杂度为O(nlog2n)。平均时间复杂度也是平均时间复杂度也是O(nlog2n)，具体，具体分析分析 见教材见教材 目前基于比较的排序算法中速度最快的目前基于比较的排序算法中速度最快的，快速排，快速排序算法是不稳定的序算法是不稳定的 C+标准库标准库中的函数模板采用的是快中的函数模板采用的是快速排序算法速排序算法
