1、1数据结构数据结构(下下)2第第8章查找章查找第第9章章 排序排序第第10章章 索引与散列索引与散列3第8章 查找4 查找，也称为检索。查找某人的地址、电话号码；查某单位45岁以上职工等，都属于查找范畴。本书中，我们规定查找是按关键字进行的，所谓关键字(key)是数据元素(或记录)中某个数据项的值，用它可以标识(或识别)一个数据元素。例如，描述一个考生的信息，可以包含：考号、姓名、性别、年龄、家庭住址、电话号码、成绩等关键字。但有些关键字不能唯一标识一个数据元素，而有的关键字可以唯一标识一个数据元素。如刚才的考生信息中，姓名不能唯一标识一个数据元素(因有同名同姓的人)，而考号可以唯一标识一个数
2、据元素(每个考生考号是唯一的，不能相同)。我们将能唯一标识一个数据元素的关键字称为主关键字，而其它关键字称为次关键字。一、查找的基本概念一、查找的基本概念5 有了主关键字及关键字后，我们可以给查找下一个完整的定义。所谓查找，就所谓查找，就是根据给定的值，在一个表中查找出其关是根据给定的值，在一个表中查找出其关键字等于给定值的数据元素键字等于给定值的数据元素(即记录即记录)，若表中有这样的元素，则称查找是成功的，此时查找的信息为给定整个数据元素的输出或指出该元素在表中的位置；若表中不存在这样的记录，则称查找是不成功的，或称查找失败，并可给出相应的提示。6 要衡量一种查找算法的优劣，主要是看要找的
3、值与关键字的比较次数，但我们将找到给定值与关键字的比较次数的平均值(平均查找长度平均查找长度)来作为衡量一个查找算法好坏的标准，对于一个含有n个元素的表，查找成功时的平均查找长度可表示为ASL=，其中i为查找第i个元素的概率，且 =1。一般情形下我们认为查找每个元素的概率相等，i为查找第i个元素所用到的比较次数。niiicp1niip171、顺序查找顺序查找二、二、静态查找表静态查找表 顺序查找的基本思想 顺序查找是一种最简单的查找方法，它的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和待找的值相比较，若相等，则查找成功，若整个表扫描完毕，仍末找到关键字等于的元素，则查
4、找失败。顺序查找既适用于顺序表，也适用于链表。若用顺序表，查找可从前往后扫描，也可从后往前扫描，但若采用单链表，则只能从前往后扫描。另外，顺序查找的表中元素可以是无序的。8 顺序查找性能分析(1)在最坏的情况下，顺序查找需要比较n次，即最大查找长度MSL=n。(2)假设在每个记录查找的概率相等，即有pi=1/n，由于查找第i个记录需要比较i次，即Ci=i，于是，查找成功的平均查找长度 ASL=从ASL可知，当n较大时，ASL值较大，查找的效率较低。niiicp1ninin11)1(21n 顺序查找的优点是算法简单。顺序查找的缺点顺序查找的缺点是查找效率低，当当n n较大时，不宜采用顺序查找较大
5、时，不宜采用顺序查找。92 2、折半查找、折半查找 首先将待查值K与有序表R1到Rn的中点mid上的关键字Rmid.key进行比较，若相等，则查找成功；否则，若Rmid.keyk，则在R1到Rmid-1中继续查找，若有Rmid.keyk,则在Rmid+1到Rn中继续查找。每通过一次关键字的比较，区间的长度就缩小一半，区间的个数就增加一倍，如此不断进行下去，直到找到关键字为K的元素；若当前的查找区间为空(表示查找失败)。折半查找的基本思想 折半查找，也称二分查找，它是一种高效查找方法。10从上述查找思想可知，每进行一次关键字比较，区间长度缩小一半，故称为折半（查找的范围缩小一半）。而区间数目增加
6、一倍，故也称为二分（区间一分为二），mid=(low+high)/2注：折半查找的结束条件是(1)区间中间位置记录的关键字等于给定的值，区间中间位置记录的关键字等于给定的值，则表明查找成功。则表明查找成功。(2)查找区间的大小差小于查找区间的大小差小于0，表明查找不成功。，表明查找不成功。11例：假 设 给 定 有 序 表 中 关 键 字 为8,17,25,44,68,77,98,100,115,125，将查找K=17和和K=120的情况描述为图8-1及图8-2所示。8 17 25 44 68 77 98 10 115 125 low high (a)初始情形 8 17 25 44 68 44
7、 98 100 115 125 low high mid (b)经过一次比较后的情形 12 8 17 25 44 68 77 98 100 115 125(c)经过二次比较后的情形 (Rmid.key=17)low mid high 图 8-1 查找 K=17 的示意图(查找成功)8 17 25 44 68 77 98 100 115 125 (a)初始情形 low high 13 8 17 25 44 68 77 98 100 115 125 (b)经过一次比较后的情形 mid low high 8 17 25 44 68 77 98 100 115 125 (c)经过二次比较后的情形 mi
8、d low high 14 8 17 25 44 68 77 98 100 115 125 (d)经过三次比较后的情形 mid low high 17 25 44 77 98 100 115 125 high low m id (e)经 过 四 次 比 较 后 的 情 形(highlow)图 8-2 查 找 K=120 的 示 意 图 (查 找 不 成 功)15折半查找的性能分析 可用二叉树来描述折半查找过程。把当前查找区间的中点作为根结点，左子区间和右子区间分别作为根的左子树和右子树，左子区间和右子区间再按类似的方法，由此得到的二叉树称为二分查找的判定树。例如，图8-1给定的关键字序列的判定
9、树见图8-3。44 8 25 17 98 77 68 100 115 125 图 8-3 具有 10 个关键字序列的二分查找判定树 16 从图8-3可知，查找根结点68，需一次查找，查找17和100，各需二次查找，查找8、25、77、115各需三次查找，查找44、98、125各需四次查找。于是，可以得到结论：二叉树第k层结点的查找次数各为k次(根结点为第1层)，而第k层结点数最多为2k-1个。假设该二叉树的深度为h，则折半查找的成功的平均查找长度为（假设每个结点的查找概率相等）：ASL=1/n 1/n（1+22+322+h2h-1）niiicp1niic117三、动态查找表三、动态查找表 1
10、1、二叉排序树、二叉排序树二叉排序树的概述 二叉排序树或者是一棵空树，或者是一棵具有如下特征的非空二叉树：(1)若它的左子树非空，则左子树上所有结点的关键字均小于根结点的关键字；(2)若它的右子树非空，则右子树上所有结点的关键字均大于等于根结点的关键字；(3)左、右子树本身又都是一棵二叉排序树。18二叉排序树的数据类型描述可用一个二叉链表来描述一棵二叉排序树，具体为：struct Btreenode elemtype key;/代表关键字 Btreenode *lch,*rch;/代表左、右孩子 ;二叉排序树的插入运算 若二叉排序树为空，则作为根结点插入，否则，若待插入的值小于根结点值，则作为
11、左子树插入，否则作为右子树插入。19例：给定关键字序列79，62，68，90，88，89，17，5，100，120，生成二叉排序树过程如图8-4所示。(注：二叉排序树与关键字排列顺序有关，排列顺序不一样，得到的二叉排序树也不一样)79 62 79 68 62 79 68 62 79 90 88 68 62 79 90(a)(b)(c)(d)(e)20 88 68 62 79 90 89 89 17 88 68 62 79 90 17 5 88 68 62 79 90 89(f)(g)(h)89 17 5 88 68 62 79 90 100 89 17 5 88 68 62 79 90 100
12、 120 图 8-4 二叉排序树的生成过程(i)(j)21二叉排序树上的查找 若二叉排树为空，则查找失败，否则，先拿根结点值与待查值进行比较，若相等，则查找成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤，若在查找过程中遇到二叉排序树的叶子结点时，还没有找到待找结点，则查找不成功。二叉排序树查找的性能分析 在二叉排序树查找中，成功的查找次数不会超过二叉树的深度，而具有n个结点的二叉排序树的深度，最好为log2n，最坏为n。因此，二叉排序树查找的最好时间复杂度为O(log2n)，最坏的时间复杂度为O(n)。222 2、平衡二叉树查找、平衡二叉树查找平衡二叉树概述 由
13、阿德尔森一维尔斯和兰迪斯(Adelson-Velskii and Landis)于1962年首先提出的，所以又称为AVL树。若一棵二叉树中每个结点的左、右子树的深度之差的绝对值不超过1，则称这样的二叉树为平衡二叉树。将该结点的左子树深度减去右子树深度的值，称为该结点的平衡因子(balance factor)。即，一棵二叉排序树中，所有结点的平衡因子只能为0、1、-1时，则该二叉排序树就是一棵平衡二叉树，否则就不是一棵平衡二叉树。23 5 2 3 4 16 7 图 8-5 一棵平衡二叉树 6 1 2 3 4 8 5 7 图 8-6 一 棵 非 平 衡 二 叉 树 非平衡二叉树的平衡处理 LL型的
14、处理(左左型)24 如图8-7所示，在C的左孩子B上插入一个左孩子结点A，使C的平衡因子由1变成了2，成为不平衡的二叉树序树。这时的平衡处理为：将C顺时针旋转，成为B的右子树，而原来B的右子树则变成C的左子树，待插入结点A作为B的左子树。平 衡外 理 1 A B C 0 2 C B A 0 0 0 图 8-7 LL 型 平 衡 外 理 25LR型的处理(左右型)如图8-8所示，在C的左孩子A上插入一个右孩子B，使的C的平衡因子由1变成了2，成为不平衡的二叉排序树。这是的平衡处理为：将B变到A与C 之间，使之成为LL型，然后按第(1)种情形LL型处理。0-1 C A B 2 0 1 C A B
15、2 B 0 0 C A 0 平衡处理 旋转 图 8-8 LR 型平衡处理 26RR型的处理(右右型)如图8-9所示，在A的右孩子B上插入一个右孩子C，使A的平衡因子由-1变成-2，成为不平衡的二叉排序树。这时的平衡处理为：将A逆时针旋转，成为B的左子树，而原来B的左子树则变成A的右子树，待插入结点C成为B的右子树。平衡处理 a-1 C B A 0-2 C B A 0 0 0 图 8-9 RR 型平衡处理 27RL型的处理(右左型)如图8-10所示，在A的右孩子B上插入一个右孩子C，使A的平衡因子由-1变成-2，成为不平衡的二叉排序树。这时的平衡处理为：将A逆时针旋转，成为B的左子树，而原来B的
16、左子树则变成A的右子树，待插入结点C成为B的右子树。平衡处理 a-1 C B A 0-2 C B A 0 0 0 图 8-10 RR 型平衡处理 28例：设一组记录的关键字按以下次序进行插入：4、5、7，2、1、3、6，其生成及调整成二叉平衡树的过程示于图8-11。图8-11 二叉平衡树插入结点(结点旁的数字为其平衡因子)29平衡二叉树的查找及性能分析 平衡二叉树本身就是一棵二叉排序树，故它的查找与二叉排序树完全相同。但它的查找 性能优于二叉排序树，不像二叉排序树一样，会出现最坏的时间复杂度O(n)，它的时间复杂度与二叉排序树的最好时间复杂相同，都为O(log2n)。例：对关键字序列4,5,7
17、,2,1,3,6，试用二叉排序树和平衡二叉树两种方法查找，给出查找6的次数及成功的平均查找长度。分析：由于关键字序列的顺序己经确定，故得到的二叉排序树和平衡二叉树都是唯一的。得到的平衡二叉树见图8-12，得到的二叉排序树见图8-13。30 0 6 2 1 4 3 7 0 0 0 0 0 5 0 4 2 3 1 5 7 6 图8-13 由关键字序列4,5,7,2,1,3,6生成的二叉排序树 图8-12 由关键字序列4,5,7,2,1,3,6生成的平衡二叉树从图8-13的二叉排序树可知，查找6需4次，平均查找长度ASL=(1+2+2+3+3+3+4)/7=18/72.57。从图8-12的平衡二叉树
18、可知，查找6需2次，平均查找长度ASL=(1+2+2+3+3+3+3)=17/72.43。从结果可知，平衡二叉树的查找性能优于二叉排序树。31第第9章章 排序排序 32学习重点：排序的基本概念和术语 插入排序：直接插入排序和希尔排序 交换排序：冒泡排序和快速排序 选择排序：简单选择排序和堆排序 归并排序 基数排序 各种排序方法的比较分析339.1 排序的基本概念排序的基本概念9.2 插入排序插入排序9.3 交换排序交换排序9.4选择排序选择排序9.5 归并排序归并排序9.6 基数排序基数排序9.7 小结小结34 排序（排序（SortingSorting）排序又称分类，是把一组记排序又称分类，是
19、把一组记录（元素）按照某个域的值的递增（即由小到大）录（元素）按照某个域的值的递增（即由小到大）或递减（即由大到小）的次序重新排列的过程。或递减（即由大到小）的次序重新排列的过程。可以使杂乱无章的数据序列重新排列成有序序列。可以使杂乱无章的数据序列重新排列成有序序列。35排序方法的分类排序方法的分类 内部排序是指待排序的记录存放在计算机内存之中；外部排序是指待排序的记录数量很大，以至于内存容纳不下而存放在外存储器之中，排序过程需要访问外存。本章主要讨论内部排序本章主要讨论内部排序 36 排序的依据可以是记录的主关键字，也可以是次关键字，甚至是若干数据项的组合。为了方便讨论，把排序所依据的数据项
20、统称排序关键字，简称关键字。假设含有n个记录的序列为R1,R2,Rn，其相应的关键字序列为K1，K2，Kn，所谓排序就是将记录Ri按关键字Ki非递减(或非递增)的顺序重新排列起来。37内部排序的方法内部排序的方法插入类插入类交换类交换类选择类选择类 归并类归并类其它方法其它方法38 将要排序的记录集合，在本章中选用顺序存储方法。为了讨论方便，在此把排序关键字假设为整型。假设排序依据的关键字为整型。记录的结构定义如下：const MAXSIZE=1000;/*数组最大容量*/typedef int ElemType;/*关键字的类型*/typedef struct /*记录结构 *ElemTyp
21、e key;/*排序关键字域*/int oth;/*其它域，根据需要自己设定*/node;399.2 插入排序插入排序 插入排序（插入排序（Insertion Sort）又可分）又可分几种不同的方法，这里仅介绍三种几种不同的方法，这里仅介绍三种方法：方法：直接插入排序直接插入排序 折半插入排序折半插入排序 希尔排序希尔排序409.2.1 直接插入排序直接插入排序 直接插入排序（直接插入排序（Straight Insertion Sort）是一种最简单的排序方法。是一种最简单的排序方法。它的基本操作是将一个记录插入到一个它的基本操作是将一个记录插入到一个长度为长度为m（假设）的有序表中，使之仍（
22、假设）的有序表中，使之仍保持有序，从而得到一个新的长度为保持有序，从而得到一个新的长度为m1的有序表。的有序表。41算法思路：设有一组关键字设有一组关键字K1，K2，Kn；排序；排序一开始就认为一开始就认为K1是一个有序序列；让是一个有序序列；让K2插入上插入上述表长为述表长为1的有序序列，使之成为一个表长为的有序序列，使之成为一个表长为2的有序序列；然后让的有序序列；然后让K3插入上述表长为插入上述表长为2的有的有序序列，使之成为一个表长为序序列，使之成为一个表长为3的有序序列；的有序序列；依次类推，最后让依次类推，最后让Kn插入上述表长为插入上述表长为n-1的有的有序序列，得一个表长为序序
23、列，得一个表长为n的有序序列。的有序序列。42例例9.1设有一组关键字序列设有一组关键字序列55，22，44，11，33，这里，这里n=5，即有，即有5个记录。请将其按由小个记录。请将其按由小到大的顺序排序。到大的顺序排序。43直接插入排序算法如下：直接插入排序算法如下：void stinsort(node rMAXSIZE，int n)for(i=2；i r0.key)rj+1=rj；j-；rj+1=r0；/*将r0即原ri记录内容，插到rj后一位置*/*sinsort*/44 此算法外循环n-1次，在一般情况下内循环平均比较次数的数量级为(n)，所以算法总时间复杂度为(n2)。由于比较过程
24、中，当Kj 与K0 相等时并不移动记录，因此直接插入排序方法是稳定的。直接插入排序也可用单链表做存储结构 459.2.2 折半插入排序折半插入排序 当直接插入排序进行到某一趟时，对于当直接插入排序进行到某一趟时，对于ri.key来讲，前边来讲，前边i-1个记录已经按关键个记录已经按关键字有序。此时不用直接插入排序的方法，字有序。此时不用直接插入排序的方法，而改为折半查找，找出而改为折半查找，找出ri.key应插的位应插的位置，然后插入。这种方法就是折半插入置，然后插入。这种方法就是折半插入排序（排序（Binary insertion sort）。）。算法如下：算法如下：46 void bina
25、sort(struct node rMAXSIZE，int n)for(i=2；i=n；i+)r0=ri；l=1；h=i-1；/*认为在认为在rlow和和ri-1之间已经有序之间已经有序*/whil(l=h)/*对有序表进行折半查找对有序表进行折半查找*/mid=(l+h)/2；if(r0.key=l；j-)rj+1=rj；rl=r0；/*此处可以改为此处可以改为rh=r0；吗？；吗？*/*binasort*/47 折半插入排序，关键字的比较次数折半插入排序，关键字的比较次数由于采用了折半查找而减少，数量由于采用了折半查找而减少，数量级为级为(nlog2n)，但是元素移动次数，但是元素移动次数
26、仍为仍为(n2)。故折半插入排序时间。故折半插入排序时间复杂度仍为复杂度仍为(n2)。折半插入排序方法是稳定的。折半插入排序方法是稳定的。489.2.3 希尔排序希尔排序 希尔排序（shell sort）是D.希尔（D.L.Shell）提出的“缩小增量”的排序方法。它的作法不是每次一个元素挨一个元素的比较。而是初期选用大跨步（增量较大）间隔比较，使记录跳跃式接近它的排序位置；然后增量缩小；最后增量为 1，这样记录移动次数大大减少，提高了排序效率。希尔排序对增量序列的选择没有严格规定。49算法思路：算法思路：1先取一个正整数先取一个正整数d1(d1 n)，把全部记录分成，把全部记录分成d1 个组
27、，所有距离为个组，所有距离为d1 的倍数的记录看成一的倍数的记录看成一组，假设组，假设d1=4，那么记录共分，那么记录共分4组：组：第第1组：组：r1,r5,r9,;第第2组：组：r2,r6,r10;第第3组：组：r3,r7,;第第4组：组：r4,r8,;在各组内部进行插入排序，使得数据在每组内在各组内部进行插入排序，使得数据在每组内是有序的，但整个记录表仍然无序；是有序的，但整个记录表仍然无序；502.然后取然后取d2(d2=1)，即所有记录成为一个大组为止。，即所有记录成为一个大组为止。此时整个记录表有序，排序完成。此时整个记录表有序，排序完成。一般选d1 约为n/2，d2 为d1/2，d
28、3为d2/2，di=151 例例9.2有一组关键字76，81，60，22，98，33，12，79，将其按由小到大的顺序排序。这里n=8，取d1=4，d2=2，d3=1，其排序过程如图9.2所示。52算法如下：算法如下：void shellsort(struct node rMAXSIZE，int n)k=n/2；/*k值代表前文中的d值*/while(k=1)/*循环*/for(i=k+1；ir0.key)&(j=0)rj+k=rj；j=j-k；rj+k=r0；k=k/2；/*shellsort*/53 希尔排序的分析是一个复杂的问题，因为它的时间是所选定的“增量序列”的函数，这涉及到数学上一
29、些尚未解决的难题。到目前为止没有人找到一种最好的增量序列。有人在大量实验基础上推出，它的时间复杂度约为O(n1.3)。如果对关键字序列6,7,51,2,52,8进行希尔排序，可以看出希尔排序是不稳定的。549.3 交换排序 交换排序主要是根据记录的关键字的大小，将记录进行交换来排序的。交换排序的特点是：将关键字值较大的记录向序列的后部移动，关键字较小的记录向前移动。55 两种交换排序方法：冒泡排序和快速排序。为了方便理解算法，本小节使用数组时均从下标1开始。假设数组名是a，第一个数据元素放在a1 之中。569.3.1 冒泡排序冒泡排序 冒泡排序(Bubble Sort)是一种人们熟知的、最简单
30、的交换排序方法。在排序过程中，关键字较小的记录经过与其他记录的对比交换，好像水中的气泡向上冒出一样，移到数据序列的首部，故称此方法为冒泡排序法。57排序的算法思路是：排序的算法思路是：(1)让j取n至2，将rj.key与rj-1.key比较，如果rj.keyi;j-)if(rj.keyrj-1.key)x=rj;rj=rj-1;rj-1=x;tag=1;i+;while(tag=1&i=n);/*bubblesort*/62 该算法的时间复杂度为O(n2)。但是，当原始关键字序列已有序时，只进行一趟比较就结束，此时时间复杂度为O(n)。639.3.2 快速排序快速排序 快速排序由霍尔(Hoar
31、e)提出，它是一种对冒泡排序的改进。由于其排序速度快故称快速排序(Quick Sort)。快速排序方法的实质是将一组关键字K1,K2,Kn进行分区交换排序。64算法思路：（1）以第一个关键字K1为控制字，将K1,K2,Kn分成两个子区，使左区所有关键字小于等于K1，右区所有关键字大于等于K1，最后控制字K1居两个子区中间的适当位置。但在子区内数据尚处于无序状态。（2）将右区首、尾指针(记录的下标号)保存入栈。对左区进行与第（1）步相类似的处理，又得到它的左子区和右子区，控制字居中。（3）重复第（1）、（2）步，直到左区处理完毕。然后退栈对一个个子区进行相类似的处理，直到栈空为止。换句话讲，就是
32、直到分区的大小为一个记录为止。65例例9.4设有一组关键字46,56,14,43,95,19,18,72，这里n=8。试用快速排序方法由小到大进行排序。66算法实现算法实现：先设计一个算法hoare()，它仅对某一待排序文件进行左、右子区的划分，使控制字居中；再设计一个主体框架算法quicksort()，在这里多次调用hoare()函数以实现对整个文件的排序 两个算法如下：67分区处理算法分区处理算法hoare()：int hoare(struct node rMAXSIZE,int l,int h)i=1;j=h;x=ri;do while(i=x.key)j-;if(ij)ri=rj;i+
33、;while(ij)&(ri.key=x.key)i+;if(ij)rj=ri;j-;while(ij);ri=x;return(i);/*控制字放在两个子文件的中间*/return(i);/*i 是控制字的位置*/*hoare*/68void quicksort2(struct node rMAXSIZE,int l,int h)/*递归的快速排序主体函数*/if(lh)i=hoare(r,l,h);/*划分两个区，调用分区处理函数hoare()*/quicksort2(r,l,i-1);/*对左分区快速排序*/quicksort2(r,i+1,h);/*对右分区快速排序*/*quickso
34、rt2*/快速排序主体框架算法：快速排序主体框架算法：69 快速排序主体算法时间运算量约O(log2n)，划分子区函数运算量约O(n)，所以总的时间复杂度为O(n.log2n)，它显然优于冒泡排序O(n2)。可是算法的优势并不是绝对的。当原文件关键字有序时，快速排序时间复杂度就是O(n2),这种情况下快速排序不快。而这种情况的冒泡排序是O(n),反而很快。在原文件记录关键字无序时的多种排序方法中，快速排序被认为是最好的一种排序方法。70例例9.5试用6,7,51,2,52,8进行快速排序。排序过程简述如下：6 7 51 2 52 8 初始状态52 7 51 6 7 82 52 51 6 7 8
35、2 52 51 6 7 8 最后状态从结果中可以看出原先位于51之后的52在排序之后移到了51的前面，所以说快速排序是不稳定的 719.4选择排序 选择排序也有几种不同的方法，这里仅介绍简单选择排序和堆排序。为了方便理解算法，本小节使用数组时均从下标1开始。假设数组名是a，第一个数据元素放在a1 之中。729.4.1简单选择排序简单选择排序 简单排序的具体思路是：对于一组关键字 K1,K2,Kn，首先从K1,K2,Kn中选择最小值，假如它是Kz，则将Kz与K1对换；然后从K2，K3，Kn中选择最小值Kz，再将Kz与K2对换。如此进行选择和调换n-2趟，第(n-1)趟，从Kn-1、Kn中选择最小
36、值Kz，将Kz与Kn-1对换，最后剩下的就是该序列中的最大值，一个由小到大的有序序列就这样形成。7374算法如下：算法如下：void sisort(struct node rMAXSIZE,int n)for(i=1;in;i+)z=i;for(j=i+1;j=n;j+)if(rj.keyrz.key)z=j;if(zi)x=ri;ri=rz;rz=x;/*sisort*/其时间复杂度为O(n2)。并且排序是稳定的。759.4.2堆排序堆排序 堆是n个元素的有限序列 K1,K2,Kn，当且仅当满足如下关系：称为堆。)2,2,1(122nikkkkiiii这是一个上小、底大的堆。若是一个上大、底
37、小的堆，只需把“=”即可。堆是一种数据元素之间的逻辑关系，常用向量做存储结构 76 用堆的概念分析向量中的数据，它显然满足（上小、底大）堆的关系。不难看出满足堆的逻辑关系的一组数据，可画成二叉树的形状，并且它是一棵完全二叉树树形.77781堆排序思路堆排序思路 把n个记录存于向量r之中，把它看成完全二叉树，此时关键字序列不一定满足堆的关系。堆排序大体分两步处理。(1)初建堆。初建堆。从堆的定义出发，当i=1,2,n/2时应满足ki=k2i和ki=k2i+1。所以先取i=n/2(它一定是第n个结点双亲的编号)，将以i结点为根的子树调整为堆；然后令i=i-1，将以i结点为根的子树调整为堆。此时可能
38、会反复调整某些结点，直到i=1为止，堆初步建成。79(2)堆排序堆排序。首先输出堆顶元素（一般是最小值），让堆中最后一个元素上移到原堆顶位置，然后恢复成堆。因为经过第一步输出堆顶元素的操作后，往往破坏了堆关系，所以要将其恢复成堆。重复执行输出堆顶元素、堆尾元素上移和恢复堆的步骤，直到全部元素输出完为止。80例例9.6设有设有n个记录个记录(n=8)的关键字是的关键字是46,55,13,42,94,17,5,80，试对它们进行堆排序。，试对它们进行堆排序。第一步：初建堆。因为n=8，所以从i=4开始。81 第二步：堆排序。这是一个反复输出堆顶元素，将堆尾元素移至堆顶，再调整恢复堆的过程。注意：每
39、输出一次堆顶元素，所谓堆尾元素移至堆顶位置，实质上是堆尾元素与堆顶元素进行交换。同时，堆尾的逻辑位置退1，直到堆中剩下一个元素为止。82排序过程（1）83排序过程（2）84排序过程（3）85排序过程（4）86排序过程（5）87排序过程（6）88堆排序算法实现堆排序算法实现（1）由上述可知，调整恢复堆调整恢复堆要被多次反复调用，为此专门设计算法heap()完成此功能。（2）另外，需再设计一个主体算法，使在初建堆阶段，让i从n/2变化到1，循环调用函数heap()，而在堆排序阶段，每输出一次堆顶元素将堆尾元素移至堆顶之后，就调用一次heap()函数来恢复堆。主体算法由函数heapsort()实现。
40、89(1)以编号为i的结点为根，调整为堆的算法：void heap(struct node rMAXSIZE,int i,int m)x=ri;j=2*i;/*x保存根记录内容，j为左孩子编号*/while(j=m&bol=0)if(jrj+1.key)j+;/*当结点i有左、右两个孩子时，j取关键字较小的孩子结点编号*/if(rj.keyx.key)bol=1;/*已是堆关系*/else ri=rj;i=j;j=2*i;/*较小数上移,向下一层探测*/ri=x;/*heap*/90(2)堆排序主体算法：void heapsort(struct node rMAXSIZE,int n)/*n为
41、文件的实际记录数,r0没有使用*/for(i=n/2;i=1;i-)heap(r,i,n);/*初建堆*/*以下For语句为输出堆顶元素，调整堆操作*/for(v=n;v=2;v-)/*逻辑堆尾下标m不断变小*/printf(“%5d”,r1.key);/*输出堆顶元素*/x=r1;r1=rv;rv=x;/*堆顶与堆尾元素交换*/heap(r,1,v-1);/*本次比上次少处理一个记录*/printf(“%5d”,r1.key);/*heapsort*/919.5 归并排序 归并的含义是将两个或两个以上的有序表合并成一个新的有序表。归并排序(Merge Sort)有多路归并排序、两路归并排序。
42、可用于内排序，也可以用于外排序。这里仅对内排序的两路归并方法进行讨论这里仅对内排序的两路归并方法进行讨论92两路归并排序算法思路两路归并排序算法思路(1)把n个记录看成n个长度为l的有序子表；(2)进行两两归并使记录关键字有序，得到 个长度为2的有序子表；(3)重复第（2）步直到所有记录归并成一个长度n为的有序表为止。2n93例9.7 有一组关键字有一组关键字4,7,5,3,2,8,6,1,n=8,将其按由将其按由小到大的顺序排序。小到大的顺序排序。两路归并排序操作过程如图9.12所示，其中 l为子表长度。94算法实现算法实现 分三步来讨论：首先，让子表表长L=1进行处理；不断地使L=2*L，
43、进行子表处理，直到L=n为止，把这一过程写成一个主体框架函数mergesort()。其次，对于某确定的子表表长L，将n个记录分成若干组子表，两两归并，这里显然要循环若干次，把这一步写成一个函数mergepass()，可由mergesort()调用。最后，再看每一组（一对）子表的归并。归并操作作为核心算法写成函数merge()，由mergepass()来调用。95(1)主体框架算法描述如下：主体框架算法描述如下：void mergesort(struct node rMAXSIZE,int n)/*r是包含有n个记录的原文件，归并过程中另需一个r2作为辅助存储空间*/l=1;/*子表初始长度*/
44、while(l=2*l)/*剩下的记录数目大于两个子表长度时*/h1=i;mid=h1+l-1;h2=i+2*l-1;merge(r,r2,h1,mid,h2);/*调用归并核心算法*/i=i+2*l;/*跳过两个子表，指向新的一对子表的首记录*/if(n-i+1)=l)/*剩下的记录数目小于一个子表时*/for(j=i;j=n;j+)r2j=rj else /*剩下的记录数目大于一个，小于两个子表时*/h1=i;mid=h1+l-1;h2=n;merge(r,r2,h1,mid,h2);/*调用归并核心算法*/*mergesort*/97(3)归并排序核心算法描述如下：归并排序核心算法描述如
45、下：void merge(struct node rMAXSIZE,struct node r2MAXSIZE,int h1,int mid,int h2)/*h1为第一个子表首元素的下标，mid 为第一个子表末元素的下标，*/*h2为第二个子表末元素的下标 */i=h1;j=mid+1;k=h1-1;/*k是r2的初始指针*/while(i=mid)&(j=h2)k=k+1;if(ri.key=rj.key)r2k=ri;i+;else r2k=rj;j+;while(i=mid)k+;r2k=ri;i+;while(j=h2)k+;r2=rj;j+;/*merge*/98 主体算法调用me
46、rgepass约log2n趟。每一趟处理考虑两两子表归并，其运算数量级为O(n)。故归并排序时间复杂度为O(nlog2n)归并排序是稳定的 999.6 基数排序 前几节所介绍的排序方法主要是通过比较记录的关键字来实现，基数排序(Radix Sort)是与前面所介绍的各类排序方法完全不同的一种排序方法。基数排序法不必经过关键字的比较来实现排序，而是根据关键字每个位上的有效数字的值，借助于“分配”和“收集”两种操作来实现排序。100基数排序有两种方法：基数排序有两种方法：一种方法是首先根据最高位有效数字进行排序，然后根据次高位有效数字进行排序，依次类推，直到根据最低位（个位）有效数字进行排序，产生
47、一个有序序列，这种方法称最高位优先法(Most Significant Digit first)，简称MSD法。101 另一方法是首先根据关键字最低位（个位）有效数字进行排序，然后根据次低位（十位）有效数字进行排序，依次类推，直到根据最高位有效数字进行排序，产生一个有序序列，这种方法称最低位优先法(Least Significant Digit)，简称LSD法。102算法实现：算法实现：第一趟“分配”，根据关键字个位有效数字，把所有记录分配到相应的10个队列中去。用f0,e0表示3号队列的头、尾指针，f9，e9表示9号队列的头、尾指针。例如，关键字为184的记录就分配到4号队列中去。第一趟“收
48、集”把所有非空队列（10个队列中可能有空队）按队列号由小到大的顺序头、尾相接，收集成一个新的序列。此序列若观察其关键字的个位，则它是有序的；若观察其关键字的高位，则它尚处于无序状态。以后各趟，分别根据关键字的十位、百位有效数字重复类同第（1）、（2）步的“分配”与“收集”操作，最终得到一个按关键字由小到大的序列。103例例9.8 有一组关键字有一组关键字278,109,063,930,589,184,505,269,008,083,将它们按由小到大的顺序将它们按由小到大的顺序排序。排序。操作的具体过程见图9.13104105106107int radixsort(struct node rMA
49、XSIZE,int n)int f10,e10;for(i=1;in;i+)ri.point=i+1;rn.point=0;p=1;/*建立静态链表，p指向链表的第一个元素*/for(i=1;i=d;i+)/*下面是分配队列*/for(j=0;j10;j+)fj=0;ej=0;while(p!=0)k=yx(rp.key,i);/*取关键字倒数第i位有效数字*/if(fk=0)fk=p;ek=p;/*让头尾指针指向同一元素*/else l=ek;rl.point=p;ek=p;/*在k号队列尾部入队*/p=rp.point;/*在r向量中，p指针向后移*/*下面是收集*/108 j=0;whi
50、le(fj=0)j+;/*找第一个非空队列*/p=fj;t=ej;/*p记下队头做收集后的静态链表头指针/while(j10)j+;while(j10)&(fj=0)j+;if(fj!=0)rt.point=fj;t=ej;/*将前边一个非空队列的队尾元素指针指向现在队头元素并记下现在队尾位置*/rt.point=0;/*这是一趟分配与收集之后的链表最后一个元素*/*for i */return(p);/*基数排序结果p指向静态链表的第一个元素，即关键字最小的记录*/*radixsort*/109 radixsort()算法中基数为10，这里用rd表示它，最高有效数字位是4，这里用d表示，记录
