第二十讲.ppt

第二十讲,一、第九章知识回顾,二、排序,2,19.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作()型调整以使其平衡。LL B.LR C.RL D.RR27.设有一组记录的关键字为19，14，23，1，68，20，84，27，55，11，10，79，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（）个记录。A1 B.2 C.3 D.431.设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是()A8 B3 C5 D9 32.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？()Ak-1次 B.k次 C.k+1次 D.k（k+1）/2次,C,D,D,D,3,34.散列函数有一个共同的性质，即函数值应当以()取其值域的每个值。最大概率 B.最小概率 C.平均概率 D.同等概率35.散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。（）元素59存放在散列表中的A 8 B.9 C.10 D.11（2）存放元素59需要搜索的次数是（）。A 2 B.3 C.4 D.536.将10个元素散列到100000个单元的哈希表中，则（）产生冲突。A.一定会 B.一定不会 C.仍可能会,D,D,C,C,4,第10章 排序,排序的概念及种类 插入法排序的各种具体实现方法及算法分析 选择法排序的各种具体方法的实现及时间性能分析 交换法排序的具体实现及性能分析 归并排序和基数排序的各自实现算法,本章导读,排序是日常工作和软件设计中常用的运算之一。为了提高查询速度需要将无序序列按照一定的顺序组织成有序序列。由于需要排序的数据表的基本特性可能存在差异，使得排序方法也不同。如何合理地组织数据的逻辑顺序，按照何种方式排出的序列最有效？这是本章要讨论的主题。本章主要介绍排序的概念及几种最常见的排序方法，讨论其性能和特点，并在此基础上进一步讨论各种方法的适用场合，以便在实际应用中能根据具体的问题选择合适的排序方法。,10.1 排序的基本概念,10.1.1 排序及其分类,1排序概念,排序（sorting）又称分类，是数据处理领域中一种很常用的运算。排序就是把一组记录或数据元素的无序序列按照某个关键字值（关键字）递增或递减的次序重新排列的过程。,排序的主要目的就是实现快速查找。日常生活中通过排序以后进行检索的例子屡见不鲜。如电话簿、病历、档案室中的档案、图书馆和各种词典的目录表等，几乎都需要对有序数据进行操作。,假设含有n个记录的序列为：R1，R2，Rn(1)其相应的关键字序列为：K1，K2，Kn需确定1，2，n的一种排序p1，p2，pn，使其相应的关键字满足如下关系：Kp1Kp2Kpn(2)即使得式（1）的序列成为一个按关键字有序的序列R p1，R p2，Rpn(3)这个将原有表中任意顺序的记录变成一个按关键字有序排列的过程称为排序。,2排序分类,增排序和减排序：如果排序的结果是按关键字从小到大的次序排列的，就是增排序，否则就是减排序。,（2）稳定排序和不稳定排序：假设Ki=Kj（1in，1jn，ij），且在排序前的序列中Ri领先于Rj（即ij）。若在排序后的排序中Ri仍领先于Rj，即那些具有相同关键字的记录，经过排序后它们的相对次序仍然保持不变，则称这种排序方法是稳定的；反之，若Rj领先于Ri，则称所用的方法是不稳定的。,(3)内部排序与外部排序：在排序中，若数据表中的所有记录的排列过程都是在内存中进行的，称为内部排序。由于待排序的记录数量太多，在排序过程中不能同时把全部记录放在内存，需要不断地通过在内存和外存之间交换数据元素来完成整个排序的过程，称为外部排序。在外部排序情况下，只有部分记录进入内存，在内存中进行内部排序，待排序完成后再交换到外部存储器中加以保存。然后再将其它待排序的记录调入内存继续排序。这一过程需要反复进行，直到全部记录排出次序为止。显然，内部排序是外部排序的基础，本章主要介绍内部排序的各种方法。,10.1.2 排序算法的效率分析,与许多算法一样，对各种排序算法性能的评价主要从两个方面来考虑，一是时间性能；二是空间性能。,1 时间复杂度分析,排序算法的时间复杂度可用排序过程中记录之间关键字的比较次数与记录的移动次数来衡量。,在本章各节中讨论算法的时间复杂度时，一般都按平均时间复杂度进行估算；对于那些受数据表中记录的初始排列及记录数目影响较大的算法，按最好情况和最坏情况分别进行估算。,2空间复杂度分析,排序算法的空间复杂度是指算法在执行时所需的附加存储空间，也就是用来临时存储数据的内存使用情况。在以后的排序算法中，若无特别说明，均假定待排序的记录序列采用顺序表结构来存储，即数组存储方式，并假定是按关键字递增方式排序。为简单起见，假设关键字类型为整型。待排序的顺序表类型的类型定义如下：typedef int KeyType/定义关键字类型 typedef struct dataType/记录类型 keytype key;/关键字项 elemtype otherelement;/其他数据项 RecType;,10.2 插入排序,插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子表中的适当位置，直到全部记录插入完成为止。也就是说，将待序列表分成左右两部分，左边为有序表（有序序列），右边为无序表（无序序列）。整个排序过程就是将右边无序表中的记录逐个插入到左边的有序表中，构成新的有序序列。,根据不同的插入方法，插入排序算法主要包括：直接插入排序、折半插入排序、表插入排序和希尔排序等。本章重点介绍直接插入排序、折半插入排序和希尔排序。,10.2.1 直接插入排序,直接插入排序(Insertion Sort)是所有排序方法中最简单的一种排序方法。其基本原理是顺次地从无序表中取出记录Ri(1in)，与有序表中记录的关键字逐个进行比较，找出其应该插入的位置，再将此位置及其之后的所有记录依次向后顺移一个位置，将记录Ri插入其中。假设待排序的n个记录为R1，R2，Rn，初始有序表为R1，初始无序表为R2 Rn。当插入第i个记录Ri(2in)时，有序表为R1Ri-1，无序表为Ri Rn。将关键字K i依次与Ki-1，Ki-2，K1进行比较，找出其应该插入的位置，将该位置及其以后的记录向后顺移，插入记录Ri，完成序列中第i个记录的插入排序。当完成序列中第n个记录Rn的插入后，整个序列排序完毕。,向有序表中插入记录，主要完成如下操作：(1)搜索插入位置。(2)移动插入点及其以后的记录空出插入位置。(3)插入记录。,假设将n个待排序的记录顺序存放在长度为n+1的数组R1Rn 中。R0作为辅助空间，用来暂时存储需要插入的记录，起监视哨的作用。直接插入排序算法如下:,void Insert_Sort(int R,int n)int i,j;for(i=2;i=n;i+)/表示待插入元素的下标 R0=Ri;/设置监视哨保存待插入元素，腾出Ri空间 j=i-1;/j指示当前空位置的前一个元素 while(R0.keyRj.key)/搜索插入位置并后移腾出空 Rj+1=Rj;j-;Rj+1=R0;/插入元素,显然，开始时有序表中只有1个记录R1，然后需要将R2Rn的记录依次插入到有序表中，总共要进行n-1次插入操作。首先从无序表中取出待插入的第i个记录Ri，暂存在R0中；然后将R0.key依次与Ri-1.key，Ri-2.key，进行比较，如果R0.keyRi-j.key（1ji-1），则将Ri-j后移一个单元；如果R0.keyRi-j.key，则找到R0插入的位置i-j+1，此位置已经空出，将R0(即Ri)记录直接插入即可。然后采用同样的方法完成下一个记录Ri+1的插入排序。如此不断进行，直到完成记录Rn的插入排序，整个序列变成按关键字非递减的有序序列为止。在搜索插入位置的过程中，R0.key与Ri-j.key进行比较时，如果j=i，则循环条件 R0.keyRi-j.key不成立，从而退出while 循环。由此可见R0起到了监视哨的作用，避免了数组下标的出界。,【例10-1】假设有7个待排序的记录，它们的关键字分别为23，4，15，8，19，24，15，用直接插入法进行排序。,【解】直接插入排序过程如图10-1所示。方括号 中为已排好序的记录的关键字，有两个记录的关键字都为15，为表示区别，将后一个15加下划线。,空间性能：该算法仅需要一个记录的辅助存储空间，空间复杂度为O(1)。,稳定性：由于该算法在搜索插入位置时遇到关键字值相等的记录时就停止操作，不会把关键字值相等的两个数据交换位置，所以该算法是稳定的。,时间性能：整个算法执行for循环n-1次，每次循环中的基本操作是比较和移动，其总次数取决于数据表的初始特性，可能有以下几种情况：（1）当初始记录序列的关键字已是递增排列时，这是最好的情况。算法中while语句的循环体执行次数为0，因此，在一趟排序中关键字的比较次数为1，即R0的关键字与Rj的关键字比较。而移动次数为2，即Ri移动到R0中，R0移动到Rj+1中。所以，整个排序过程中的比较次数和移动次数分别为(n-1)和2(n-1)，因而其时间复杂度为O(n)。,（2）当初始数据序列的关键字序列是递减排列时，这是最坏的情况。在第i次排序时，while语句内的循环体执行次数为i。因此，关键字的比较次数为i，而移动次数为i+1。所以，整个排序过程中的比较次数和移动次数分别为：,（3）一般情况下，可认为出现各种排列的概率相同，因此取上述两种情况的平均值，作为直接插入排序关键字的比较次数和记录移动次数，约为n2/4。所以其时间复杂度为O(n2)。,根据上述分析得知：当原始序列越接近有序时，该算法的执行效率就越高。,10.2.2 折半插入排序,直接插入排序的基本操作是在有序表中进行查找和插入，而在有序表中查找插入位置，可以通过折半查找的方法实现，由此进行的插入排序称之为折半插入排序。所谓折半查找，就是在插入Ri时（此时R1，R2，Ri-1已排序），取Ri/2的关键字Ki/2 与Ki进行比较（i/2 表示取不大于i/2的最大整数），如果KiKi/2，Ri的插入位置只能在R1和Ri/2 之间，则在R1和Ri/2-1之间继续进行折半查找，否则在Ri/2+1和Ri-1 之间进行折半查找。如此反复直到最后确定插入位置为止。折半查找的过程是以处于有序表中间位置记录的关键字和Ki比较，经过一次比较，便可排除一半记录，把可插入的区间缩小一半，故称为折半。,设置始指针low，指向有序表的第一个记录，尾指针high，指向有序表的最后一个记录，中间指针mid指向有序表中间位置的记录。每次将待插入记录的关键字与mid位置记录的关键字进行比较，从而确定待插入记录的插入位置。折半插入排序算法如下：,typedef int keytype;void Insert_halfSort(RecType R,int n)/*对顺序表R作折半插入排序*/int i,j,low,high,mid;for(i=2;i=n;i+)R0=Ri;/保存待插入元素 low=1;high=i-1;/设置初始区间,while(lowRmid.key)low=mid+1;插入位置在后半部分中 else high=mid-1;/插入位置在前半部分中 for(j=i-1;j=high+1;-j)/high+1为插入位置 Rj+1=Rj;/后移元素，空出插入位置 Rhigh+1=R0;/将元素插入,【例10-2】待排序记录的关键字为：28，13，72，85，39，41，6，20，在前7个记录都已排好序的基础上，采用折半插入第8个记录的比较过程如图10-2所示。,折半插入排序仅减少了关键字间的比较次数，但记录的移动次数不变。因此折半插入排序的时间复杂度仍为O(n2)。折半插入排序的空间复杂度与直接插入排序相同。折半插入排序也是一个稳定的排序方法。,2.2路插入排序,2路插入排序是在折半插入排序的基础上再改进，其目的是减少排序过程中移动记录的次数，但为此需要n个记录的辅助空间。,具体做法如下：设一个和L.r同类型的数组d，然后从L.r中第2个记录起依次插入到d1之前和之后的有序序列中。先将待插入记录的关键字和d1的关键字相比较，若L.ri.keyd1.key，则将L.ri插入到d1之前的有序表中。反之，将L.ri插入到d1之后的有序表中。,在实现算法时，可将d看成一个循环向量，并设两个指针first和final分别指示排序过程中得到的有序序列中的第一个记录和最后一个记录在d中的位置。,2-路插入排序只能减少移动记录的次数，而不能绝对避免移动记录。当L.r1的待排序记录中关键字最小或最大的记录时，2-路插入排序就完全失去它的优越性。,因此，若希望在排序过程中不移动记录，只有改变存储结构，进行表插入排序,3.表插入排序,#define SIZE 100/静态链表容量Typedef struct RcdType rc;/记录项int next;/指针项SLNode;/表结点类型,typedef structSLNode rSIZE;/0号单元为表头结点int length;/链表当前长度；SLinkListType;/静态链表类型,设数组下标为“0”的分量为表头结点，并令表头结点记录的关键字区最大整数MAXINT。,表插入排序的过程描述如下：首先将静态链表中数组下标为“1”的分量（结点）和表头结点构成一个循环链表，然后依次将下标为“2”至“n”的分量（结点）按记录关键字非递减有序插入到循环链表中,表插入排序的基本操作仍为将一个记录插入到已经排好序的有序表中，和直接插入排序相比，不同之处仅是以修改2n次指针代替移动记录，排序过程中所需进行的关键字之间的比较次数相同。因此，表插入排序的时间复杂度仍为O(n2)。,表插入排序的结果只是求得一个有序表，则只能进行对它顺序查找，不能进行随机查找，为了实现有序表的折半查找，尚需对记录进行重新排列。,10.2.3 希尔排序,希尔排序（shells sort）又称缩小增量排序(Diminishing Increment Sort)。它是希尔（D.L.Shell）于1959年提出的插入排序的改进算法。如前所述，直接插入排序算法的时间性能取决于数据的初始特性，一般情况下，它的时间复杂度为O(n2)。但是当待排序列为正序或基本有序时，时间复杂度则为O(n)。因此，若能在一次排序前将排序序列调整为基本有序，则排序的效率就会大大提高。正是基于这样的考虑，希尔提出了改进的插入排序方法。,希尔排序的基本思想是：先将整个待排记录序列分割成若干小组（子序列），分别在组内进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。希尔排序的具体步骤如下：,（1）首先取一个整数d1n，称之为增量，将待排序的记录分成d1个组，凡是距离为d1倍数的记录都放在同一个组，在各组内进行直接插入排序，这样的一次分组和排序过程称为一趟希尔排序。,【例10-3】设有一个待排序的序列有10个记录，它们的关键字分别为58，46，72，95，84，25，37，58，63，12，用希尔排序法进行排序。【解】图10-3给出了希尔排序的整个过程，用同一连线上的关键字表示其所属的记录在同一组。为区别具有相同关键字58的不同记录，用下划线标记后一个记录的关键字。,（2）再设置另一个新的增量d2d1，采用与上述相同的方法继续进行分组和排序过程。,（3）继续取di+1di，重复步骤(2)，直到增量d=1，即所有记录都放在同一个组中。,d1=5;,(58,25);(46,37);(72,58);(95,63);(84,12);,(25,58);(37,46);(58,72,);(63,95);(12,84);,按照递增的顺序得到：,d2=3;,25，63，46，84,37，12，72,58，58，95,按照递增的顺序得到：,25，46，63，84,12，37，72,58，58，95,d3=1;,12，25，37，46，58，58，63，72，84，95,按照递增的顺序得到：,25，12，58，46，37，58，63，72，95，84,第一趟排序时，取d1=5，整个序列被划分成5组，分别为58，25，46，37，72，58，95，63，84，12。对各组内的记录进行直接插入排序，得到第一趟排序结果如图10-3(a)所示。第二趟排序时，取d2=3，将第一趟排序的结果分成3组，分别为25，63，46，84,37，12，72,58，58，95。再对各组内记录进行直接插入排序，得到第二趟排序结果如图10-3(b)所示。25 12 58 46 37 58 63 72 95 84第三趟排序时，取d3=1，所有的数据记录分成1组25，12，58，46，37，58，63，72，95，84，此时序列基本“有序”，对其进行直接插入排序，最后得到希尔排序的结果如图10-3(c)所示。12 25 37 46 58 58 63 72 86 95。,希尔排序的算法如下：void Shell_Sort(RecType R,int n)int i,j,d;RecType temp;d=n2;/初始增量 while(d0)/通过增量控制排序的执行过程 for(i=d;i=0)if(Rj.keyRj+d.key)temp=Rj;/Rj与Rj+d交换 Rj=Rj+d;Rj+d=temp;j=j-d;/j前移 else j=-1;d=d2;/递减增量d,从希尔排序过程可以看到：（1）算法中约定初始增量d1为已知；,（2）算法中采用简单的取增量值的方法，从第二次起取增量值为其前次增量值的一半。在实际应用中，可能有多种取增量的方法，并且不同的取值方法对算法的时间性能有一定的影响，因而一种好的取增量的方法是改进希尔排序算法时间性能的关键。,（3）希尔排序开始时增量较大，分组较多，每组的记录数较少，故各组内直接插入过程较快。随着每一趟中增量di逐渐缩小，分组数逐渐减少，虽各组的记录数目逐渐增多，但由于已经按di-1作为增量排过序，使序列表较接近有序状态，所以新的一趟排序过程也较快。因此，希尔排序在效率上较直接插入排序有较大的改进。希尔排序的时间复杂度约为O(n 1.3)，它实际所需的时间取决于各次排序时增量的取值。大量研究证明，若增量序列取值较合理，希尔排序时关键字比较次数和记录移动次数约为O(nlog2n)2。由于其时间复杂度分析较复杂，在此不做讨论。,注：希尔排序会使关键字相同的记录交换相对位置，所以希尔排序是不稳定的。,