《数据结构ppt课件》由会员分享，可在线阅读，更多相关《数据结构ppt课件（64页珍藏版）》请在金锄头文库上搜索。
1、西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图第第9章章排序排序9.1排序的基本概念排序的基本概念9.2简单排序方法简单排序方法9.3先进排序方法先进排序方法9.4各种排序方法的综合比较各种排序方法的综合比较9.5外排序简介外排序简介西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图9.1排序的基本概念排序的基本概念1.排序排序是按关键字的非递减或非递增顺序对一组记录重新进行排列是按关键字的非递减或非递增顺序对一组记录重新进行排列的操作。的操作。描述如下：描述如下：假设含有假设含有n个记录的序列为个记录的序列为r1，r2，rn它们的关键字相应为它们的关键字相应为k1，k
2、2，kn使其关键字满足如下非递减（或非递增）关系：使其关键字满足如下非递减（或非递增）关系：也就是使记录序列重新排列成一个按关键字有序的序列也就是使记录序列重新排列成一个按关键字有序的序列西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图2.排序的稳定性排序的稳定性假设假设Ki=Kj(1in，1jn，ij)，若在排序前的序列中若在排序前的序列中Ri领先领先于于Rj(即即ij)，排序后，排序后Ri仍领先于仍领先于Rj，称排序方法是稳定的；称排序方法是稳定的；若相同关键字的领先关系在排序过程中发生变化，称为不稳若相同关键字的领先关系在排序过程中发生变化，称为不稳定的排序。定的排序。证明一
3、种排序方法是稳定的，要从算法本身的步骤中加以证明一种排序方法是稳定的，要从算法本身的步骤中加以证明。证明。证明排序方法是不稳定的，只需给出一个反例说明证明排序方法是不稳定的，只需给出一个反例说明西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图在排序过程中，一般进行在排序过程中，一般进行两种基本操作两种基本操作：比较两个关键字的大小；比较两个关键字的大小；将记录从一个位置移动到另一个位置。将记录从一个位置移动到另一个位置。三种常见的三种常见的存储方法存储方法：向量结构向量结构：将待排序的记录存放在一组地址连续的存储单：将待排序的记录存放在一组地址连续的存储单元中。由于在这种存储方式中
4、，记录之间的次序关系由其存储元中。由于在这种存储方式中，记录之间的次序关系由其存储位置来决定，所以排序过程中一定要移动记录才行。位置来决定，所以排序过程中一定要移动记录才行。链表结构链表结构：采用链表结构时，记录之间逻辑上的相邻性：采用链表结构时，记录之间逻辑上的相邻性是靠指针来维持的，这样在排序时，就不用移动记录元素，而是靠指针来维持的，这样在排序时，就不用移动记录元素，而只需要修改指针。只需要修改指针。这种排序方式被称为链表排序。这种排序方式被称为链表排序。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图 记录向量与地址向量结合记录向量与地址向量结合：将待排序记录存放在一组地：
5、将待排序记录存放在一组地址连续的存储单元中，同时另设一个指示各个记录位置的地址址连续的存储单元中，同时另设一个指示各个记录位置的地址向量。在排序过程中不移动记录本身，而修改地址向量中的向量。在排序过程中不移动记录本身，而修改地址向量中的“地址地址”，排序结束后，再按照地址向量中的值调整记录的存储，排序结束后，再按照地址向量中的值调整记录的存储位置。这种排序方式被称为地址排序。位置。这种排序方式被称为地址排序。 为了讨论方便，为了讨论方便，假设待排记录的关键字均为整数，从数组假设待排记录的关键字均为整数，从数组下标为下标为1 1的位置开始存储，下标为的位置开始存储，下标为0 0的位置存储监视哨，
6、或空闲的位置存储监视哨，或空闲不用。不用。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图#defineMAXSIZE20/*一个用作示例的小顺序表的最大长度一个用作示例的小顺序表的最大长度*/typedefintKeyType;typedefstructKeyTypekey;OtherTypeotherdata;RecordType;typedefstructRecordTyperMAXSIZE+1;/*r0闲置或作为判别标志的闲置或作为判别标志的“哨兵哨兵”单元单元*/intlength;/*顺序表长度顺序表长度*/SqList;/*顺序表类型顺序表类型*/西安科技大学精品课程
7、西安科技大学精品课程第第7 7章章 图图根据在排序中涉及的存储器不同，将排序方法分为两大类：根据在排序中涉及的存储器不同，将排序方法分为两大类：（1）内部排序内部排序：整个排序过程完全在内存中进行。：整个排序过程完全在内存中进行。（2）外部排序外部排序：由于待排序记录数据量太大，在排序过程中需：由于待排序记录数据量太大，在排序过程中需要对外存进行访问的排序过程。要对外存进行访问的排序过程。按排序算法的时间复杂度来分，可分为三类：按排序算法的时间复杂度来分，可分为三类：（1）简单的排序方法，其时间复杂度为）简单的排序方法，其时间复杂度为O（n2）；）；（2）先进的排序方法，其时间复杂度为）先进的
8、排序方法，其时间复杂度为O（nlogn）；）；（3）基数排序，其时间复杂度为）基数排序，其时间复杂度为O（d*n）。）。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图9.2.1简单选择排序（简单选择排序（selectionsort）在简单选择排序的过程中，待排记录序列的状态为：在简单选择排序的过程中，待排记录序列的状态为：基本思想：基本思想：第第i趟排序操作：从无序序列趟排序操作：从无序序列Ri.n的的n-i+1记录中选出关键记录中选出关键字最小的记录字最小的记录Rj和和Ri交换，从而使有序序列区从交换，从而使有序序列区从R1.i-1扩大扩大至至R1.i，如图，如图9.1所示。所
9、示。有序序列有序序列R1i-1无序序列无序序列Ri.n9.2简单排序方法简单排序方法常用的有常用的有简单选择排序简单选择排序、插入排序插入排序和和起泡排序起泡排序。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图一趟简单选择排序算法一趟简单选择排序算法voidSelectPass(SqList*L,inti)RecordTypetemp;j=i;/*j指示关键字最小记录的位置，初值设为指示关键字最小记录的位置，初值设为i*/for(k=i+1;klength;k+)if(L-rk.keyrj.key)j=k;/*暂不进行记
10、录交换，只记录位置暂不进行记录交换，只记录位置*/if(i!=j)/*最后交换记录最后交换记录Rj和和Ri*/temp=L-rj;L-rj=L-ri;L-ri=temp;/*SelectPass西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图整个选择排序是一趟选择排序过程的多次重复，其算法如下：整个选择排序是一趟选择排序过程的多次重复，其算法如下：voidSelectSort(SqList*L)/*对顺序表对顺序表L作简单选择排序作简单选择排序*/RecordTypetemp;for(i=1;ilength;+i)/*选择第选择第i个小的记录，并交换到位个小的记录，并交换到位*/j
11、=i;for(k=i+1;klength;k+)/*在在L.ri.L.length中选择中选择key最小的记录最小的记录*/if(L-rk.keyrj.key)j=k;if(i!=j)temp=L-rj;L-rj=L-ri;L-.ri=temp;/*与第与第i个记录交换个记录交换*/*SelectSort西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图例如，对下列一组关键字：例如，对下列一组关键字：（491，38，65，492，76，13，27，52）西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图算法分析：算法分析：时间复杂度：时间复杂度：移动次数：移动次数：最小最小
12、0最大最大3（n-1）比较次数：比较次数：n-1,n-2,n-3,1时间复杂度时间复杂度为为O(n2)空间复杂度为空间复杂度为O(1)就选择排序方法本身讲，它是一种稳定的排序方法，但图就选择排序方法本身讲，它是一种稳定的排序方法，但图9.2所表现出来的现象是不稳定的，这是由于上述实现选择排序所表现出来的现象是不稳定的，这是由于上述实现选择排序的算法采用的的算法采用的“交换记录交换记录”的策略所造成的，若改变这个策略，的策略所造成的，若改变这个策略，可以写出不产生可以写出不产生“不稳定现象不稳定现象”的选择排序算法。的选择排序算法。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图9.
13、2.2插入排序插入排序1直接插入排序（直接插入排序（insertionsort）基本思想：基本思想：在一个已排好序的记录子集的基础上，每一步将下一个待排在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序地插入到已排好序的记录子集中，直到将所有待排序的记录有序地插入到已排好序的记录子集中，直到将所有待排记录全部插入为止。记录全部插入为止。例如：打扑克牌时的抓牌，每抓一张牌，插入到合适位置，例如：打扑克牌时的抓牌，每抓一张牌，插入到合适位置，直到抓完牌为止，即可得到一个有序序列。直到抓完牌为止，即可得到一个有序序列。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图基本操作
14、：基本操作：将当前无序序列区将当前无序序列区Ri.n中的记录中的记录Ri“插入插入”到有序序列区到有序序列区R1.i-1中，中，i=2,3,n。使有序序列区的长度增。使有序序列区的长度增1。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图例如：对一组关键字序列例如：对一组关键字序列49,38,65,492,76,13,27,52进行进行插入排序过程中，每一趟排序之后的状况如图插入排序过程中，每一趟排序之后的状况如图9.4所示。所示。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图假假设设待待排排序序记记录录存存放放在在r1.n之之中中。为为了了提提高高效效率率，附附设设
15、一一个监视哨个监视哨r0，使得，使得r0存放待插入的记录。存放待插入的记录。监视哨作用：监视哨作用：一是备份待插入的记录，以便前面关键字较大的记录后移；一是备份待插入的记录，以便前面关键字较大的记录后移；二是防止越界。二是防止越界。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图voidInsertPass(SqList*L,inti)L-r0=L-ri;/*复制为哨兵复制为哨兵*/j=i-1;while(L-r0.keyrj.key)L-rj+1=L-rj;/*记录后移记录后移*/j-;L-rj+1=L-r0/*插入到正确位置插入到正确位置*/*InsertPass*/具体算具体
16、算法描述如下：法描述如下：整个插入排序需进行整个插入排序需进行n-1趟趟“插入插入”。只含一个记录的序列必。只含一个记录的序列必定是个有序序列，因此插入应从定是个有序序列，因此插入应从i=2起进行。此外，若第起进行。此外，若第i个记录的个记录的关键字不小于第关键字不小于第i-1个记录的关键字，个记录的关键字，“插入插入”也就不需要进行了。也就不需要进行了。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图插入排序的算法如下：插入排序的算法如下：voidInsertSort(SqList*L)for(i=2;ilength;+i)if(L-ri.keyri-1.key)/*当当“r0=
17、L-ri;/*复制为哨兵复制为哨兵*/j=i-1;while(L-r0.key.rj.key)L-rj+1=L-rj;/*记录后移记录后移*/j-;L-rj+1=L-r0;/*插入到正确位置插入到正确位置*/*if*/InsertPass*/西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图算法性能分析：算法性能分析：从空间角度看，需一个辅助空间从空间角度看，需一个辅助空间r0。空间复杂度为空间复杂度为S(n)=O(1)。从时间耗费角度看，主要时间耗费在关键字比较和移动元素上。从时间耗费角度看，主要时间耗费在关键字比较和移动元素上。最好情况：（记录有序）最好情况：（记录有序）总的比较
18、次数为总的比较次数为n-1次次移动记录的次数也达到最小值移动记录的次数也达到最小值2（n-1）最坏情况：（记录逆序）最坏情况：（记录逆序）总的比较次数达到最大值为总的比较次数达到最大值为(n+2)(n-1)/2，记录移动的记录移动的次数也达到最大值次数也达到最大值(n+4)(n-1)/2。时间复杂度为时间复杂度为T(n)=O(n2)直接插入排序是稳定的排序方法直接插入排序是稳定的排序方法。适用：待排序记录数目较少且基本有序的情况。适用：待排序记录数目较少且基本有序的情况。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图 2折半插入排序折半插入排序在有序表中确定插入位置，采用折半查找
19、确定插入位置，即在有序表中确定插入位置，采用折半查找确定插入位置，即在有序表在有序表r1.i-1中用折半查找确定第中用折半查找确定第i个元素的插入位置。个元素的插入位置。时间复杂度：时间复杂度：比较次数减少了，比较次数减少了，最大为折半判定树的深度最大为折半判定树的深度。但移动次数。但移动次数不变。不变。故为故为O(n2)西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图 voidBinSort(RecordTyper,intlength)/*对记录数组对记录数组r进行折半插入排序，进行折半插入排序，length为数组的长度为数组的长度*/for(i=2;i=length;+i)x=
20、ri;low=1;high=i-1;while(low=high)/*确定插入位置确定插入位置*/mid=(low+high)/2;if(x.key=low;-j)rj+1=rj;/*记录依次向后移动记录依次向后移动*/rlow=x;/*插入记录插入记录*/西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图 3表插入排序表插入排序*直接插入排序、折半插入排序均要大量移动记录，时间开销直接插入排序、折半插入排序均要大量移动记录，时间开销大。大。表插入排序是采用链表存储结构进行插入排序的方法。表插入排序是采用链表存储结构进行插入排序的方法。基本思想：基本思想：先在待插入记录之前的有序子链
21、表中查找应插入位置，然先在待插入记录之前的有序子链表中查找应插入位置，然后将待插入记录插入链表。后将待插入记录插入链表。由于链表的插入操作只修改指针域，不移动记录，所以表由于链表的插入操作只修改指针域，不移动记录，所以表插入排序可提高排序效率。插入排序可提高排序效率。在算法的具体实现上，我们可以采用静态链表作为存储结构。在算法的具体实现上，我们可以采用静态链表作为存储结构。表插入排序示例如图表插入排序示例如图9.5所示。所示。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图首先给出类型说明如下：首先给出类型说明如下：typedefintKeyType;typedefstructKe
22、yTypekey;OtherTypeother-data;intnext;RecordType1;设设r为用为用RecordType1类型数组表示的静态链表，为了插入方类型数组表示的静态链表，为了插入方便，用便，用r0做为表头结点，并构成循环链表，即做为表头结点，并构成循环链表，即r0.next指向静指向静态循环链表的第一个结点，态循环链表的第一个结点，rn.next=0。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图 voidSLinkListSort(RecordType1r,intlength)intn=lengt
23、h;r0.next=n;r1.next=0;/*构造只有一个元素的有序静态循环链表构造只有一个元素的有序静态循环链表*/for(i=2;i=n-1;-i)p=r0.next;q=0;while(p0&rp.keytj，tk=1；ir做一趟希尔插入排序，做一趟希尔插入排序，delta为增量为增量*/for(i=1+delta;ilength;i+)/*1+delta为第一个子序列的第二个元素的下标为第一个子序列的第二个元素的下标*/if(L-ri.keyri-delta.key)L-r0=L-ri；/*备份备份ri(不做监视哨不做监视哨)*/for(j=i-delta；j0&L-r0.keyrj
24、.key；j-=delta)L-rj+delta=L-rj；L-rj+delta=L-r0；voidShellSort(SqList*L)/*对记录数组对记录数组r做希尔排序做希尔排序*/for(i=0；ir做冒泡排序做冒泡排序*/RecordTypetemp;n=L-length;change=TRUE；for(i=1;i=n-1&change;+i)change=FALSE；for(j=1;jrj.keyL-rj+1.key)temp=L-rj;L-rj=L-rj+1;L-rj+1=temp;change=TRUE；/*BubbleSort*/西安科技大学精品课程西安科技大学精品课程第第7
25、 7章章 图图， 效率度量：效率度量：最好情况（正序）：需进行一趟排序（即最好情况（正序）：需进行一趟排序（即n-1次比较）次比较）最坏情况（逆序）：最坏情况（逆序）：需进行需进行n-1趟排序（每趟冒泡排序需进行趟排序（每趟冒泡排序需进行i次比较，次比较，3i次移动次移动)。经过经过n-1趟冒泡排序后，总的比较次数为趟冒泡排序后，总的比较次数为(n-i)=n(n-1)/2总的移动次数为总的移动次数为3n(n-1)/2次次该算法的时间复杂度为该算法的时间复杂度为O(n2)，空间复杂度为，空间复杂度为O(1)。冒泡排序法是一种稳定的排序方法。冒泡排序法是一种稳定的排序方法。西安科技大学精品课程西安
26、科技大学精品课程第第7 7章章 图图9.3先进排序方法先进排序方法9.3.1快速排序快速排序快速排序（快速排序（quicksort）是从起泡排序改进而得的一种）是从起泡排序改进而得的一种“交交换换”排序方法。排序方法。基本思想：基本思想：通过一趟排序将记录分割成两部分，一部分记录的关键字通过一趟排序将记录分割成两部分，一部分记录的关键字均比另一部分记录的关键字小，再分别对两部分排序。（递归）均比另一部分记录的关键字小，再分别对两部分排序。（递归）西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图假设待排序的原始记录序列为（假设待排序的原始记录序列为（Rs，Rs+1，Rt-1，Rt）一
27、趟快速排序的基本操作：一趟快速排序的基本操作：任选一个记录（通常选记录任选一个记录（通常选记录Rs），以它的关键字作为），以它的关键字作为“枢枢轴轴”，序列中关键字小于枢轴的记录均移动至该记录之前；序，序列中关键字小于枢轴的记录均移动至该记录之前；序列中关键字大于枢轴的记录均移动至该记录之后。列中关键字大于枢轴的记录均移动至该记录之后。初始关键码：初始关键码：4914387496658495527西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图intPartiti
28、on(RecordTypeR,intlow,inthigh)R0=Rlow;/*将枢轴记录移至数组的闲置分量将枢轴记录移至数组的闲置分量*/Pivotkey=Rlow.key;/*枢轴记录关键字枢轴记录关键字*/while(lowhigh)/*从表的两端交替的向中间扫描从表的两端交替的向中间扫描*/while(low=pivotkey)-high;Rlow+=Rhigh;while(lowhigh&Rlow.key=pivotkey)+low;Rhigh-=Rlow;/*将比枢轴记录大的记录移到高端将比枢轴记录大的记录移到高端*/*whileRlow=R0;/*枢轴记录移到正确位置枢轴记录移到
29、正确位置*/returnlow;/*返回枢轴位置返回枢轴位置*/*Partition西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图voidQSort(RecordTypeR,ints,intt)/*对记录序列对记录序列Rs.t进行快速排序进行快速排序*/if(st-1)/*长度大于长度大于1*/pivotloc=Partition(R,s,t);QSort(R,s,pivotloc-1);QSort(R,pivotloc-1,t);/*对高端子序列递归排序对高端子序列递归排序*/if/Qsort西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图性能分析：性能分析：分分析
30、析快快速速排排序序的的时时间间耗耗费费,共共需需进进行行多多少少趟趟排排序序，取取决决于于递递归调用深度。归调用深度。最大特点：平均性能很好最大特点：平均性能很好最坏情况：单支形式最坏情况：单支形式时间复杂度为时间复杂度为O(n2)。平均性能：平均性能：O(nlogn)快速排序为一种不稳定的排序方法快速排序为一种不稳定的排序方法西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图9.3.2归并排序归并排序归并排序法：把两个有序序列归并为一个有序序列。归并排序法：把两个有序序列归并为一个有序序列。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图voidMerge(Record
31、TypeSR,RcdTypeTR,inti,intm,intn)/*将有序的将有序的SRi.m和和SRm+1.n归并为有序的归并为有序的TRi.n*/for(j=m+1,k=i;i=m&j=n;+k)/*将将SR中记录由小到大的并入中记录由小到大的并入TR*/if(SRi.key=SRj.key)TRk=SRi+;elseTRk=SRj+;while(i=m)TRk+=SRi+;/*将剩余的将剩余的SRi.m复制到复制到TR*/while(j=n)TRk+=SRj+;/*将剩余的将剩余的SRj.n复制到复制到TR*/Merge西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图归并排序
32、算法也是一个递归调用的算法，如算法归并排序算法也是一个递归调用的算法，如算法9.13所示。所示。voidMsort(RecordTypeSR,RecordTypeTR1,ints,intt)if(s=t)TR1s=SRs;elsem=(s+t)/2;/*将将SRs.t平分为平分为SRs.m和和SRm+1.t*/Msort(SR,TR2,s,m);/*递归地将递归地将SRs.m归并为有序的归并为有序的TR2s.m*/Msort(SR,TR2,m+1,t);/*将将SRm+1.t归并为有序的归并为有序的TR2m+1.t*/Merge(TR2,TR1,s,m,t);/else/Msort时间复杂度为
33、时间复杂度为O(nlogn)，空间复杂度为，空间复杂度为O(n)。与快速排序。与快速排序相比，归并排序的最大特点是它为一种稳定的排序方法。相比，归并排序的最大特点是它为一种稳定的排序方法。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图9.3.3堆排序堆排序一一.树形选择排序树形选择排序树形选择排序也称作锦标赛排序。树形选择排序也称作锦标赛排序。基本思想：基本思想：先把待排序的先把待排序的n个记录的关键字两两进行比较，取出较小个记录的关键字两两进行比较，取出较小的。然后再在个较小的记录中，采用同样的方法进行比较。选的。然后再在个较小的记录中，采用同样的方法进行比较。选出每两个中较小
34、的，如此反复，直到选出最小关键字记录为止。出每两个中较小的，如此反复，直到选出最小关键字记录为止。在输出最小记录后，为再次选出次小记录，将根结点即最小记在输出最小记录后，为再次选出次小记录，将根结点即最小记录所对应的叶子结点的关键字的值置为录所对应的叶子结点的关键字的值置为，再进行上述的过程，再进行上述的过程，直到所有的记录全部输出为止。如图直到所有的记录全部输出为止。如图9.10所示。所示。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图二二堆排序堆排序1.什么是堆什么是堆?n个元素个元素k1,k2,kn满足：满足：或：
35、完全二叉树中所有非终端结点的值均不大于（或不小于）或：完全二叉树中所有非终端结点的值均不大于（或不小于）其左右孩子结点的值。其左右孩子结点的值。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图2堆排序堆排序输输出出堆堆顶顶的的最最小小值值之之后后，将将剩剩余余n-1个个元元素素重重新新建建成成一一个个堆堆，则得则得n个元素的次小值，反复执行，便能的到一个有序序列。个元素的次小值，反复执行，便能的到一个有序序列。需要解决两个问题：需要解决两个问题：如何建初始堆；如何建初始堆；如何调整为堆如何调整为堆。问题问题1:当堆顶元素改
36、变时，如何调整为堆当堆顶元素改变时，如何调整为堆?西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图问题二：对问题二：对n个元素初始建堆的过程。个元素初始建堆的过程。建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。过程。n个结点的完全二叉树，则最后一个结点是第个结点的完全二叉树，则最后一个结点是第个个结点的孩子结点。对第结点的孩子结点。对第个结点为根的子树筛选，使该子个结点为根的子树筛选，使该子树成为堆，之后向前依次对各结点为根的子树进行筛选，使树成为堆，之后
37、向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。图之成为堆，直到根结点。图9.13给出了给出了“建堆建堆”过程示例。过程示例。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图voidsift（RecordTyper,int,int）t=rk；/*暂存暂存“根根”记录记录rk*/x=rk.key；i=k；j=2*i；finished=FALSE；while(j=m&!finished)if(jrj+1.key)j=j+1；/*若存在右子树，若存在右子树，且右子树根的关键字大，且右子树根的关键字大，则沿右分支则沿右
38、分支“筛选筛选”*/if(x=1;-i)/*自第个记录开始进行筛选建堆自第个记录开始进行筛选建堆*/sift(r，i，n)；堆排序的算法如下：堆排序的算法如下：voidHeapSort（RecordTyper,intlength）crt-heap（r,length）；）；n=length;for(i=n;i=2;-i)b=r1;/*将堆顶记录和堆中的最后一个记录互换将堆顶记录和堆中的最后一个记录互换*/r1=riri=b;sift(r，1，i-1)；/*进行调整，进行调整，使使r1.i-1变成堆变成堆*/*HeapSort*/西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图堆排序在
39、最坏情况下，其时间复杂度也为堆排序在最坏情况下，其时间复杂度也为O(nlog2n)，这是这是堆排序的最大优点。堆排序的最大优点。堆排序与树形排序相比较，排序中只需要存放一个记录的堆排序与树形排序相比较，排序中只需要存放一个记录的辅助空间，因此也将堆排序称作原地排序。辅助空间，因此也将堆排序称作原地排序。堆排序是一种不稳定的排序方法。堆排序是一种不稳定的排序方法。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图9.3.4基数排序基数排序*基数排序（基数排序（radixsorting）是和前几节讨论的排序方法完）是和前几节讨论的排序方法完全不同的一种排序方法。全不同的一种排序方法。从前
40、几节的讨论可见，实现排序主要是通过关键字之间从前几节的讨论可见，实现排序主要是通过关键字之间的比较和移动记录这两种操作来完成的的比较和移动记录这两种操作来完成的;实现基数排序不需要进行关键字间的比较，而基数排序实现基数排序不需要进行关键字间的比较，而基数排序是一种借助于多关键码排序的思想，是将单关键码按基数分是一种借助于多关键码排序的思想，是将单关键码按基数分成成“多关键码多关键码”进行排序的方法。进行排序的方法。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图1.多关键码排序多关键码排序例如，可以用分配和收集的方法来对扑克牌进行例如，可以用分配和收集的方法来对扑克牌进行“排序排序
41、”。扑克牌中扑克牌中52张牌，按花色和面值分成两个字段，大小关系为：张牌，按花色和面值分成两个字段，大小关系为：花色：花色：梅花梅花方块方块红心红心黑桃黑桃面值：面值：2345678910JQKA方法方法1：先对花色排序，再对每个组分别按面值进行排序。：先对花色排序，再对每个组分别按面值进行排序。方法方法2：先按面值给出：先按面值给出13个编号组个编号组(2号，号，3号，号，.，A号号)，再，再按花色给出按花色给出4个编号组个编号组(梅花、方块、红心、黑桃梅花、方块、红心、黑桃)。这两种理牌的方法便是两种多关键字的排序方法。这两种理牌的方法便是两种多关键字的排序方法。西安科技大学精品课程西安科
42、技大学精品课程第第7 7章章 图图一般情况下，设一般情况下，设n个元素的待排序列个元素的待排序列R1，R2，Rn，且，且每个记录包含每个记录包含d个关键码个关键码k1，k2，kd，则称序列对关键码，则称序列对关键码k1，k2，kd有序是指：对于序列中任两个记录有序是指：对于序列中任两个记录Ri和和Rj(1ijn)都满足下列有序关系：都满足下列有序关系：其中其中k1称为最主位关键码，称为最主位关键码，kd称为最次位关键码称为最次位关键码西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图分两种方法分两种方法最高位优先最高位优先(MostSignificantDigitfirst)法，简称
43、法，简称MSD法：法：先按先按k1排序分组，同一组中记录，关键码排序分组，同一组中记录，关键码k1相等，再对各组相等，再对各组按按k2排序分成子组，之后，对后面的关键码继续这样的排序排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码分组，直到按最次位关键码kd对各子组排序后。再将各组连对各子组排序后。再将各组连接起来，便得到一个有序序列。扑克牌按花色、面值排序中接起来，便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法一即是介绍的方法一即是MSD法。法。最低位优先最低位优先(LeastSignificantDigitfirst)法，简称法，简称LSD法：法：先从先从k
44、d开始排序，再对开始排序，再对kd-1进行排序，依次重复，直到对进行排序，依次重复，直到对k1排序后便得到一个有序序列。扑克牌按花色、面值排序中介排序后便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法二即是绍的方法二即是LSD法。法。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图1链式基数排序链式基数排序基基数数排排序序属属于于上上述述“低低位位优优先先”排排序序法法，通通过过反反复复进进行行分分配配与收集操作完成排序。与收集操作完成排序。假假设设记记录录ri的的关关键键字字为为keyi，keyi是是由由d位位十十进进制制数数字字构构成成的的，即即keyi=Ki1Ki2Ki
45、d，则则每每一一位位可可以以视视为为一一个个子子关关键键字字，其其中中Ki1是是最最高高位位，Kid是是最最低低位位，每每一一位位的的值值都都在在0Kij9的的范范围围内内，此此时时基基数数rd=10。如如果果keyi是是由由d个个英英文文字字母母构构成成的的，即即keyi=Ki1Ki2Kid，其中其中aKijz，则基数则基数rd=26。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图图9.13 链式基数排序示例 西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图图9.13 链式基数排序示例 西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图图9.13 链式基数排序示例 西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图
