数据结构课件9.ppt

1、西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图第第9章章 排序排序 9.1 排序的基本概念排序的基本概念9.2 简单排序方法简单排序方法 9.3 先进排序方法先进排序方法 9.4 各种排序方法的综合比较各种排序方法的综合比较 9.5 外排序简介外排序简介西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图9.1 排序的基本概念排序的基本概念 1. 排序排序 是按关键字的非递减或非递增顺序对一组记录重新进行排列是按关键字的非递减或非递增顺序对一组记录重新进行排列的操作。的操作。描述如下：描述如下： 假设含有假设含有n个记录的序列为个记录的序列为 r1，r2，rn 它们的关键

2、字相应为它们的关键字相应为 k1，k2，kn 使其关键字满足如下非递减（或非递增）关系：使其关键字满足如下非递减（或非递增）关系： 也就是使记录序列重新排列成一个按关键字有序的序列也就是使记录序列重新排列成一个按关键字有序的序列 pnppkkk2121pnpprrr西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图 2. 排序的稳定性排序的稳定性 假设假设Ki=Kj(1in，1jn，ij)， 若在排序前的序列中若在排序前的序列中Ri领先领先于于Rj(即即ij)，排序后，排序后Ri仍领先于仍领先于Rj， 称排序方法是稳定的；称排序方法是稳定的； 若相同关键字的领先关系在排序过程中发生变

3、化，称为不稳若相同关键字的领先关系在排序过程中发生变化，称为不稳定的排序。定的排序。 证明一种排序方法是稳定的，要从算法本身的步骤中加以证明一种排序方法是稳定的，要从算法本身的步骤中加以证明。证明。 证明排序方法是不稳定的，只需给出一个反例说明证明排序方法是不稳定的，只需给出一个反例说明西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图在排序过程中，一般进行在排序过程中，一般进行两种基本操作两种基本操作： 比较两个关键字的大小；比较两个关键字的大小； 将记录从一个位置移动到另一个位置。将记录从一个位置移动到另一个位置。三种常见的三种常见的存储方法存储方法： 向量结构向量结构：将待排序

4、的记录存放在一组地址连续的存储单：将待排序的记录存放在一组地址连续的存储单元中。由于在这种存储方式中，记录之间的次序关系由其存储元中。由于在这种存储方式中，记录之间的次序关系由其存储位置来决定，所以排序过程中一定要移动记录才行。位置来决定，所以排序过程中一定要移动记录才行。 链表结构链表结构：采用链表结构时，记录之间逻辑上的相邻性：采用链表结构时，记录之间逻辑上的相邻性是靠指针来维持的，这样在排序时，就不用移动记录元素，而是靠指针来维持的，这样在排序时，就不用移动记录元素，而只需要修改指针。只需要修改指针。 这种排序方式被称为链表排序。这种排序方式被称为链表排序。西安科技大学精品课程西安科技大

5、学精品课程第第7 7章章 图图 记录向量与地址向量结合记录向量与地址向量结合：将待排序记录存放在一组地：将待排序记录存放在一组地址连续的存储单元中，同时另设一个指示各个记录位置的地址址连续的存储单元中，同时另设一个指示各个记录位置的地址向量。在排序过程中不移动记录本身，而修改地址向量中的向量。在排序过程中不移动记录本身，而修改地址向量中的“地址地址”，排序结束后，再按照地址向量中的值调整记录的存，排序结束后，再按照地址向量中的值调整记录的存储位置。这种排序方式被称为地址排序。储位置。这种排序方式被称为地址排序。 为了讨论方便，为了讨论方便，假设待排记录的关键字均为整数，从数组假设待排记录的关键

6、字均为整数，从数组下标为下标为1 1的位置开始存储，下标为的位置开始存储，下标为0 0的位置存储监视哨，或空闲的位置存储监视哨，或空闲不用。不用。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图#define MAXSIZE 20 /*一个用作示例的小顺序表的最大长度一个用作示例的小顺序表的最大长度*/typedef int KeyType;typedef struct KeyType key; OtherType otherdata; RecordType; typedef struct RecordType rMAXSIZE+1; /*r0闲置或作为判别标志的闲置或作为判别标志

7、的“哨兵哨兵”单元单元*/ int length; /*顺序表长度顺序表长度*/SqList; /*顺序表类型顺序表类型*/西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图根据在排序中涉及的存储器不同，将排序方法分为两大类：根据在排序中涉及的存储器不同，将排序方法分为两大类：（1）内部排序内部排序：整个排序过程完全在内存中进行。：整个排序过程完全在内存中进行。（2）外部排序外部排序：由于待排序记录数据量太大，在排序过程中需：由于待排序记录数据量太大，在排序过程中需要对外存进行访问的排序过程。要对外存进行访问的排序过程。按排序算法的时间复杂度来分，可分为三类：按排序算法的时间复杂度来

8、分，可分为三类：（1）简单的排序方法，其时间复杂度为）简单的排序方法，其时间复杂度为O（n2）；）；（2）先进的排序方法，其时间复杂度为）先进的排序方法，其时间复杂度为O（nlogn）；）；（3）基数排序，其时间复杂度为）基数排序，其时间复杂度为O（d*n）。）。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图9.2.1简单选择排序（简单选择排序（selection sort） 在简单选择排序的过程中，待排记录序列的状态为：在简单选择排序的过程中，待排记录序列的状态为：基本思想：基本思想： 第第i趟排序操作：从无序序列趟排序操作：从无序序列Ri.n的的n-i+1记录中选出关键记录中

9、选出关键字最小的记录字最小的记录Rj和和Ri交换，从而使有序序列区从交换，从而使有序序列区从R1.i-1扩大扩大至至R1.i，如图，如图9.1所示。所示。有序序列有序序列R1i-1无序序列无序序列Ri.n9.2 简单排序方法简单排序方法 常用的有常用的有简单选择排序简单选择排序、插入排序插入排序和和起泡排序起泡排序。 西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图一趟简单选择排序算法一趟简单选择排序算法void SelectPass(SqList *L, int i) RecordType temp; j=i; / *j

10、指示关键字最小记录的位置，初值设为指示关键字最小记录的位置，初值设为i*/ for(k=i+1; klength; k+) if (L-rk.keyrj.key) j=k; /*暂不进行记录交换，只记录位置暂不进行记录交换，只记录位置*/ if (i!=j) /*最后交换记录最后交换记录Rj和和Ri*/ temp =L-rj; L-rj=L-ri; L-ri= temp; /*SelectPass 西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图整个选择排序是一趟选择排序过程的多次重复，其算法如下：整个选择排序是一趟选择排序过程的多次重复，其算法如下：void SelectSort

11、 (SqList *L) /*对顺序表对顺序表L作简单选择排序作简单选择排序*/RecordType temp; for(i=1; ilength; +i) /*选择第选择第i个小的记录，并交换到位个小的记录，并交换到位*/ j=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西安科技大学精品课程西安科技大学精品课

12、程第第7 7章章 图图例如，对下列一组关键字：例如，对下列一组关键字： （491，38，65，492，76，13，27，52）西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图2/ ) 1(12.)2() 1()(11nnnninni算法分析：算法分析：时间复杂度：时间复杂度：移动次数：移动次数： 最小最小 0 最大最大3（n-1）比较次数：比较次数：n-1, n-2, n-3,1 时间复杂度时间复杂度为为O(n2) 空间复杂度为空间复杂度为O(1) 就选择排序方法本身讲，它是一种稳定的排序方法，但图就选择排序方法本身讲，它是一种稳定的排序方法，但图9.2所表现出来的现象是不稳定的，

13、这是由于上述实现选择排序所表现出来的现象是不稳定的，这是由于上述实现选择排序的算法采用的的算法采用的“交换记录交换记录”的策略所造成的，若改变这个策略，的策略所造成的，若改变这个策略，可以写出不产生可以写出不产生“不稳定现象不稳定现象”的选择排序算法。的选择排序算法。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图9.2.2插入排序插入排序 1直接插入排序（直接插入排序（insertion sort） 基本思想：基本思想： 在一个已排好序的记录子集的基础上，每一步将下一个待在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序地插入到已排好序的记录子集中，直到将所有待排序

14、的记录有序地插入到已排好序的记录子集中，直到将所有待排记录全部插入为止。排记录全部插入为止。 例如：打扑克牌时的抓牌，每抓一张牌，插入到合适位置，例如：打扑克牌时的抓牌，每抓一张牌，插入到合适位置，直到抓完牌为止，即可得到一个有序序列。直到抓完牌为止，即可得到一个有序序列。 西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图基本操作：基本操作： 将当前无序序列区将当前无序序列区Ri.n中的记录中的记录Ri“插入插入”到有序序列区到有序序列区R1.i-1中，中，i=2,3,n。使有序序列区的长度增。使有序序列区的长度增1。 西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图

15、例如：对一组关键字序列例如：对一组关键字序列49,38,65,492,76,13,27,52进行插入进行插入排序过程中，每一趟排序之后的状况如图排序过程中，每一趟排序之后的状况如图9.4所示。所示。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图 假设待排序记录存放在假设待排序记录存放在r1.n之中。为了提高效率，附设一之中。为了提高效率，附设一个监视哨个监视哨r0，使得，使得r0 存放待插入的记录。存放待插入的记录。 监视哨作用：监视哨作用： 一是备份待插入的记录，以便前面关键字较大的记录后移；一是备份待插入的记录，以便前面关键字较大的记录后移； 二是防止越界。二是防止越界。西安

16、科技大学精品课程西安科技大学精品课程第第7 7章章 图图void InsertPass(SqList *L, int i) L-r0=L-ri; /*复制为哨兵复制为哨兵*/ j=i-1; while (L-r0.key rj.key ) L-rj+1=L-rj; /*记录后移记录后移*/ j-; L-rj+1=L-r0 /*插入到正确位置插入到正确位置*/ /*InsertPass*/具体算具体算法描述如下：法描述如下： 整个插入排序需进行整个插入排序需进行n-1趟趟“插入插入”。只含一个记录的序列必。只含一个记录的序列必定是个有序序列，因此插入应从定是个有序序列，因此插入应从i=2起进行。

17、此外，若第起进行。此外，若第i个记录的个记录的关键字不小于第关键字不小于第i-1个记录的关键字，个记录的关键字，“插入插入”也就不需要进行了。也就不需要进行了。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图插入排序的算法如下：插入排序的算法如下：void InsertSort (SqList *L) for (i=2; ilength; +i) if (L-ri.keyri-1.key) /*当当“r0=L-ri; /*复制为哨兵复制为哨兵*/ j=i-1; while (L-r0.key.rj.key) L-rj+1=L-rj; /*记录后移记录后移*/ j-; L-rj+1=

18、L-r0; /*插入到正确位置插入到正确位置*/ /* if*/ /InsertPass*/西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图算法性能分析：算法性能分析：从空间角度看，需一个辅助空间从空间角度看，需一个辅助空间r0。空间复杂度为空间复杂度为S(n)=O(1)。从时间耗费角度看，主要时间耗费在关键字比较和移动元素上。从时间耗费角度看，主要时间耗费在关键字比较和移动元素上。 最好情况：（记录有序）最好情况：（记录有序） 总的比较次数为总的比较次数为n-1次次 移动记录的次数也达到最小值移动记录的次数也达到最小值2（n-1）最坏情况：（记录逆序）最坏情况：（记录逆序） 总的

19、比较次数达到最大值为总的比较次数达到最大值为(n+2)(n-1)/2， 记录移动的记录移动的次数也达到最大值次数也达到最大值(n+4)(n-1)/2。 时间复杂度为时间复杂度为T(n)=O(n2) 直接插入排序是稳定的排序方法直接插入排序是稳定的排序方法。 适用：待排序记录数目较少且基本有序的情况。适用：待排序记录数目较少且基本有序的情况。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图 2折半插入排序折半插入排序 在有序表中确定插入位置，采用折半查找确定插入位置，即在有序表中确定插入位置，采用折半查找确定插入位置，即在有序表在有序表r1.i-1中用折半查找确定第中用折半查找确定第

20、i个元素的插入位置。个元素的插入位置。时间复杂度：时间复杂度： 比较次数减少了，最大为折半判定树的深度。但移动次数比较次数减少了，最大为折半判定树的深度。但移动次数不变。不变。 故为故为O(n2)西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图 void BinSort (RecordType r , int length)/*对记录数组对记录数组r进行折半插入排序，进行折半插入排序， length为数组的长度为数组的长度*/ for (i=2; i=length; +i) x= ri; low=1; high=i-1; while(low=high) /* 确定插入位置确定插入位

21、置 */ mid=(low+high) / 2; if(x.key= low; -j ) rj+1= rj; /* 记录依次向后移动记录依次向后移动 */ rlow=x; /* 插入记录插入记录 */ 西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图 3 表插入排序表插入排序* 直接插入排序、折半插入排序均要大量移动记录，时间开销直接插入排序、折半插入排序均要大量移动记录，时间开销大。大。 表插入排序是采用链表存储结构进行插入排序的方法。表插入排序是采用链表存储结构进行插入排序的方法。 基本思想：基本思想： 先在待插入记录之前的有序子链表中查找应插入位置，然先在待插入记录之前的有序

22、子链表中查找应插入位置，然后将待插入记录插入链表。后将待插入记录插入链表。 由于链表的插入操作只修改指针域，不移动记录，所以表由于链表的插入操作只修改指针域，不移动记录，所以表插入排序可提高排序效率。插入排序可提高排序效率。 在算法的具体实现上，我们可以采用静态链表作为存储结构。在算法的具体实现上，我们可以采用静态链表作为存储结构。表插入排序示例如图表插入排序示例如图9.5所示。所示。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图首先给出类型说明如下：首先给出类型说明如下：typedef int KeyType;typedef struct KeyType key; OtherT

23、ype other-data; int next; RecordType1;设设r为用为用RecordType1类型数组表示的静态链表，为了插入方类型数组表示的静态链表，为了插入方便，用便，用r0做为表头结点，并构成循环链表，即做为表头结点，并构成循环链表，即 r0.next指向静指向静态循环链表的第一个结点，态循环链表的第一个结点，rn.next=0。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图 void SLinkListSort(RecordType1 r, int length) int n=length; r

24、0.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(

25、j=i-delta；j0&L- r0.key rj.key ；j-=delta) L-rj+delta= L-rj； L-rj+delta= L- r0； void ShellSort( SqList *L)/*对记录数组对记录数组r做希尔排序做希尔排序*/ for(i=0；ir做冒泡排序做冒泡排序 */ RecordType temp; n=L-length; change=TRUE； for(i=1; i=n-1&change ; +i ) change=FALSE； for(j=1 ; jrj.key L-rj+1.key ) temp=L-rj; L-rj=L-rj+1; L-rj+1

26、= temp; change=TRUE； /* BubbleSort */西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图， 效率度量：效率度量：最好情况（正序）：需进行一趟排序（即最好情况（正序）：需进行一趟排序（即n-1次比较）次比较）最坏情况（逆序）：最坏情况（逆序）： 需进行需进行n-1趟排序（每趟冒泡排序需进行趟排序（每趟冒泡排序需进行i次比较，次比较，3i次移动次移动)。 经过经过n-1趟冒泡排序后，总的比较次数为趟冒泡排序后，总的比较次数为(n-i)=n(n-1)/2 总的移动次数为总的移动次数为3n(n-1)/2次次 该算法的时间复杂度为该算法的时间复杂度为O(n2

27、)，空间复杂度为，空间复杂度为O(1)。冒泡排序法是一种稳定的排序方法。冒泡排序法是一种稳定的排序方法。 西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图9.3 先进排序方法先进排序方法9.3.1 快速排序快速排序 快速排序（快速排序（quick sort）是从起泡排序改进而得的一种）是从起泡排序改进而得的一种“交交换换”排序方法。排序方法。基本思想：基本思想： 通过一趟排序将记录分割成两部分，一部分记录的关键字通过一趟排序将记录分割成两部分，一部分记录的关键字均比另一部分记录的关键字小，再分别对两部分排序。（递归）均比另一部分记录的关键字小，再分别对两部分排序。（递归）西安科技大

28、学精品课程西安科技大学精品课程第第7 7章章 图图假设待排序的原始记录序列为（假设待排序的原始记录序列为（Rs，Rs+1，Rt-1，Rt） 一趟快速排序的基本操作：一趟快速排序的基本操作： 任选一个记录（通常选记录任选一个记录（通常选记录Rs），以它的关键字作为），以它的关键字作为“枢枢轴轴”，序列中关键字小于枢轴的记录均移动至该记录之前；序，序列中关键字小于枢轴的记录均移动至该记录之前；序列中关键字大于枢轴的记录均移动至该记录之后。列中关键字大于枢轴的记录均移动至该记录之后。初始关键码：初始关键码： 49 14 38 74 96 65 8 49 55 27 西安科技大学精品课程西安科技大学精

29、品课程第第7 7章章 图图西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图int Partition(RecordType R, int low, int high) R0=Rlow; /*将枢轴记录移至数组的闲置分量将枢轴记录移至数组的闲置分量*/ Pivotkey=Rlow.key; /*枢轴记录关键字枢轴记录关键字*/ while(lowhigh) /*从表的两端交替的向中间扫描从表的两端交替的向中间扫描*/ while(low=pivotkey) -high; Rlow+=Rhigh; while(lowhigh&

30、Rlow.key=pivotkey) +low; Rhigh-=Rlow; /*将比枢轴记录大的记录移到高端将比枢轴记录大的记录移到高端*/ /*while Rlow=R0; /*枢轴记录移到正确位置枢轴记录移到正确位置*/ return low; /*返回枢轴位置返回枢轴位置*/ /*Partition西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图void QSort (RecordType R, int s, int t) /*对记录序列对记录序列Rs.t进行快速排序进行快速排序*/ if (st-1) /*长度大于长度大于1 */ pivotloc=Partition(R,

31、s,t); QSort(R,s,pivotloc-1); QSort(R,pivotloc-1,t); /*对高端子序列递归排序对高端子序列递归排序*/ /if/Qsort西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图性能分析：性能分析： 分析快速排序的时间耗费分析快速排序的时间耗费, 共需进行多少趟排序，取决于递共需进行多少趟排序，取决于递归调用深度。归调用深度。 最大特点：平均性能很好最大特点：平均性能很好 最坏情况：单支形式最坏情况：单支形式时间复杂度为时间复杂度为O(n2)。 平均性能：平均性能： O(nlogn) 快速排序为一种不稳定的排序方法快速排序为一种不稳定的排序

32、方法西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图9.3.2 归并排序归并排序归并排序法：把两个有序序列归并为一个有序序列。归并排序法：把两个有序序列归并为一个有序序列。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图 void Merge(RecordType SR, RcdType TR, int i, int m, int n) /*将有序的将有序的SRi.m和和SRm+1.n归并为有序的归并为有序的TRi.n */ for(j=m+1,k=i;i=m&j=n; +k) /*将将SR中记录由小到大的并入中记录由小到大的并入TR*/ if(SRi.key=SRj.

33、key) TRk=SRi+; else TRk=SRj+; while(i=m) TRk+=SRi+; /*将剩余的将剩余的SRi.m复制到复制到TR*/ while(j=n) TRk+=SRj+; /*将剩余的将剩余的SRj.n复制到复制到TR*/Merge西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图归并排序算法也是一个递归调用的算法，如算法归并排序算法也是一个递归调用的算法，如算法9.13所示。所示。void Msort (RecordType SR, RecordType TR1, int s, int t) if(s=t) TR1s=SRs; else m=(s+t)/

34、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 时间复杂度为时间复杂度为O(nlogn)，空间复杂度为，空间复杂度为O(n)。与快速排序。与快速排序相比，归并排序的最大特点是它为一种稳定的排序方法。相比，归并排序的最大特点是它为一种稳定的排序方法。西安科技大学精品课程西安科技大学精品课程

35、第第7 7章章 图图9.3.3 堆排序堆排序 一一. 树形选择排序树形选择排序 树形选择排序也称作锦标赛排序。树形选择排序也称作锦标赛排序。基本思想：基本思想： 先把待排序的先把待排序的n个记录的关键字两两进行比较，取出较小个记录的关键字两两进行比较，取出较小的。然后再在个较小的记录中，采用同样的方法进行比较。选的。然后再在个较小的记录中，采用同样的方法进行比较。选出每两个中较小的，如此反复，直到选出最小关键字记录为止。出每两个中较小的，如此反复，直到选出最小关键字记录为止。在输出最小记录后，为再次选出次小记录，将根结点即最小记在输出最小记录后，为再次选出次小记录，将根结点即最小记录所对应的叶

36、子结点的关键字的值置为录所对应的叶子结点的关键字的值置为，再进行上述的过程，再进行上述的过程，直到所有的记录全部输出为止。如图直到所有的记录全部输出为止。如图9.10所示。所示。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图二二 堆排序堆排序1. 什么是堆什么是堆? n个元素个元素k1, k2, , kn满足：满足： 或：完全二叉树中所有非终端结点的值均不大于（或不小于）或：完全二叉树中所有非终端结点的值均不大于（或不小于）其左右孩子结点的值。其左右孩子结点的值。），（或2/21122122ikkkkkkiiiiii西安

37、科技大学精品课程西安科技大学精品课程第第7 7章章 图图西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图2堆排序堆排序 输出堆顶的最小值之后，将剩余输出堆顶的最小值之后，将剩余n-1个元素重新建成一个堆，个元素重新建成一个堆，则得则得n个元素的次小值，反复执行，便能的到一个有序序列。个元素的次小值，反复执行，便能的到一个有序序列。需要解决两个问题：需要解决两个问题： 如何建初始堆；如何建初始堆； 如何调整为堆如何调整为堆。 问题问题1: 当堆顶元素改变时，如何调整为堆当堆顶元素改变时，如何调整为堆? 西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图西安科技大学精品课程西

38、安科技大学精品课程第第7 7章章 图图问题二：对问题二：对n个元素初始建堆的过程。个元素初始建堆的过程。建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。过程。 n个结点的完全二叉树，则最后一个结点是第个结点的完全二叉树，则最后一个结点是第 个个结点的孩子结点。对第结点的孩子结点。对第 个结点为根的子树筛选，使该子个结点为根的子树筛选，使该子树成为堆，之后向前依次对各结点为根的子树进行筛选，使树成为堆，之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。图之成为堆，直到根结点。图9.13给出了给出了“建堆建堆”过程示例

39、。过程示例。2/n2/n西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图void sift（RecordType r, 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；/* 若存在右子树，若存在右子树， 且右子树根的关键字大，且右子树根的关键字大， 则沿右分支则沿右分支“筛选筛选” */ if(x= 1; -i) /* 自第个记录开始进

40、行筛选建堆自第个记录开始进行筛选建堆 */ sift(r，i，n) ； 堆排序的算法如下：堆排序的算法如下： void HeapSort（RecordType r, int length） crt-heap（r, length）；）； n=length; for ( i=n; i=2; -i) b=r1; /* 将堆顶记录和堆中的最后一个记录互换将堆顶记录和堆中的最后一个记录互换 */ r1=ri ri=b; sift(r，1，i-1)； /* 进行调整，进行调整， 使使r1.i-1变成堆变成堆 */ /* HeapSort */ 西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图

41、堆排序在最坏情况下，其时间复杂度也为堆排序在最坏情况下，其时间复杂度也为O(nlog2n)， 这是这是堆排序的最大优点。堆排序的最大优点。 堆排序与树形排序相比较，排序中只需要存放一个记录的堆排序与树形排序相比较，排序中只需要存放一个记录的辅助空间，因此也将堆排序称作原地排序。辅助空间，因此也将堆排序称作原地排序。 堆排序是一种不稳定的排序方法。堆排序是一种不稳定的排序方法。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图9.3.4 基数排序基数排序* 基数排序（基数排序（radix sorting）是和前几节讨论的排序方法完）是和前几节讨论的排序方法完全不同的一种排序方法。全不同

42、的一种排序方法。 从前几节的讨论可见，实现排序主要是通过关键字之间从前几节的讨论可见，实现排序主要是通过关键字之间的比较和移动记录这两种操作来完成的的比较和移动记录这两种操作来完成的; 实现基数排序不需要进行关键字间的比较，而基数排序实现基数排序不需要进行关键字间的比较，而基数排序是一种借助于多关键码排序的思想，是将单关键码按基数分是一种借助于多关键码排序的思想，是将单关键码按基数分成成“多关键码多关键码”进行排序的方法。进行排序的方法。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图1. 多关键码排序多关键码排序 例如，可以用分配和收集的方法来对扑克牌进行例如，可以用分配和收集的

43、方法来对扑克牌进行“排序排序”。扑克牌中扑克牌中52张牌，按花色和面值分成两个字段，大小关系为：张牌，按花色和面值分成两个字段，大小关系为： 花色：花色： 梅花梅花方块方块红心红心黑桃黑桃 面值：面值： 2345678910JQKA 方法方法1：先对花色排序，再对每个组分别按面值进行排序。：先对花色排序，再对每个组分别按面值进行排序。 方法方法2：先按面值给出：先按面值给出13个编号组个编号组(2号，号，3号，号，.，A号号)，再按，再按花色给出花色给出4个编号组个编号组(梅花、方块、红心、黑桃梅花、方块、红心、黑桃)。 这两种理牌的方法便是两种多关键字的排序方法。这两种理牌的方法便是两种多关

44、键字的排序方法。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图 一般情况下，设一般情况下，设n个元素的待排序列个元素的待排序列R1，R2，Rn，且每个记录包含且每个记录包含d个关键码个关键码k1，k2，kd，则称序列对关键，则称序列对关键码码k1，k2，kd有序是指：对于序列中任两个记录有序是指：对于序列中任两个记录Ri和和Rj(1ijn)都满足下列有序关系：都满足下列有序关系：),(),(2121djjjdiiikkkkkk其中其中k1称为最主位关键码，称为最主位关键码，kd称为最次位关键码称为最次位关键码西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图分两种方法分

45、两种方法 最高位优先最高位优先(Most Significant Digit first)法，简称法，简称MSD法：法：先按先按k1排序分组，同一组中记录，关键码排序分组，同一组中记录，关键码k1相等，再对各组相等，再对各组按按k2排序分成子组，之后，对后面的关键码继续这样的排序排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码分组，直到按最次位关键码kd对各子组排序后。再将各组连对各子组排序后。再将各组连接起来，便得到一个有序序列。扑克牌按花色、面值排序中接起来，便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法一即是介绍的方法一即是MSD法。法。 最低位优先最低位

46、优先(Least Significant Digit first)法，简称法，简称LSD法：法：先从先从kd开始排序，再对开始排序，再对kd-1进行排序，依次重复，直到对进行排序，依次重复，直到对k1排序后便得到一个有序序列。扑克牌按花色、面值排序中介排序后便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法二即是绍的方法二即是LSD法。法。西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图1 链式基数排序链式基数排序 基数排序属于上述基数排序属于上述“低位优先低位优先”排序法，通过反复进行分配排序法，通过反复进行分配与收集操作完成排序。与收集操作完成排序。假设记录假设记录ri的关

47、键字为的关键字为keyi，keyi是由是由d位十进制数字位十进制数字构成的，构成的， 即即keyi=Ki1 Ki2 Kid， 则每一位可以视为一个子关键则每一位可以视为一个子关键字，其中字，其中Ki1是最高位，是最高位，Kid是最低位，每一位的值都在是最低位，每一位的值都在0Kij9的范围内，此时基数的范围内，此时基数rd=10。如果。如果keyi是由是由d个英文字母构成的，个英文字母构成的， 即即keyi=Ki1 Ki2 Kid，其中，其中aKijz， 则基数则基数rd=26。 西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图图9.13 链式基数排序示例 278109063930

48、589184505269008083(a) 初始状态e0e1e2e3e4e5e6e7e8e9269589109f9008278f8f7f6f5505f4184f3063083f2f1f0930(b) 第一趟分配之后西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图图9.13 链式基数排序示例 930063083184505278008109589269(c) 第一趟收集之后e0e1e2e3e4e5e6e7e8e9f9f8f7f6f5f4f3930f2f1f0505(d) 第二趟分配之后589184083278063269008109西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图505008109930063269278083184589(e) 第二趟收集之后e0e1e2e3e4e5e6e7e8e9930f9f8f7f6f5505f4f3f2f1f0008(f) 第三趟分配之后589063083109184269278008063083109184269278505589930(g) 第三趟收集之后的有序记录图9.13 链式基数排序示例 西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图西安科技大学精品课程西安科技大学精品课程第第7 7章章 图图