数据结构讲义第10章..ppt

《数据结构讲义第10章..ppt》由会员分享，可在线阅读，更多相关《数据结构讲义第10章..ppt（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第十章第十章 内部排序内部排序 信息查找是信息系统的最主要的操作。如何信息查找是信息系统的最主要的操作。如何在大量信息中快速找到所需要的信息一直是信息在大量信息中快速找到所需要的信息一直是信息查找所追求的目标。如果数据是按照某种合理的查找所追求的目标。如果数据是按照某种合理的顺序进行存储，则查找将是最有效的。顺序进行存储，则查找将是最有效的。排序就是使数据有序的一种基本操作，是组排序就是使数据有序的一种基本操作，是组织数据的最基本运算，织数据的最基本运算，采用更有效的排序方法，采用更有效的排序方法，能很好地提高计算机的效率。能很好地提高计算机的效率。10.1 10.1 基本基本概念概念1 1、

2、排序、排序 排排序序:设设R1,R2,.,Rn是是n n个个记记录录的的序序列列,其其相相应应的的关关键键 字字 为为 K1,K2,Kn。需需 确确 定定 1,2,n的的 一一 种种 排排 列列p1,p2,pn，使其相应满足下面的非递减使其相应满足下面的非递减(或非递增或非递增)关系：关系：Kp1Kp2.Kpn使上面使上面n n个记录的序列成为一个按关键字有序的序列个记录的序列成为一个按关键字有序的序列 Rp1,Rp2,.,Rpn这样一种操作称为排序。这样一种操作称为排序。即即排排序序是是一一个个将将记记录录关关键键字字无无序序的的序序列列调调整整为为一一个个按按关关键字有序键字有序(递增（非

3、递减递增（非递减)、递减、递减(非递增非递增)的记录序列。的记录序列。用用于于排排序序的的关关键键字字Ki：可可以以是是记记录录的的主主关关键键字字，也也可可以以是次关键字，甚至还可以是若干数据项的集合。是次关键字，甚至还可以是若干数据项的集合。若是主关键字，则排序的结果是唯一的。若是主关键字，则排序的结果是唯一的。若是次关键字，排序结果不唯一。若是次关键字，排序结果不唯一。基本基本概念概念2 2、排序的稳定性：、排序的稳定性：假假设设Ki=Kj,ij，且且在在排排序序前前的的序序列列中中Ri领领先先Rj（即即ij），若若在在排排序序后后的的序序列列中中，Ri仍仍领领先先Rj，则则称称所所用用

4、的的排排序方法是稳定的。序方法是稳定的。若若在在排排序序后后的的序序列列中中，Rj领领先先Ri，则则称称所所用用的的排排序序方方法是不稳定的。法是不稳定的。排排序序算算法法的的稳稳定定性性是是指指对对所所有有输输入入实实例例而而言言，只只要要能能找找出一个实例能证明其是不稳定的，就能说明它是不稳定的。出一个实例能证明其是不稳定的，就能说明它是不稳定的。3、内排序：排序期间，全部记录都存放在内存。、内排序：排序期间，全部记录都存放在内存。外外排排序序：排排序序期期间间，只只有有部部分分记记录录在在内内存存，随随时时存存在在记录的内外存交换。记录的内外存交换。基本基本概念概念 4 4、排序过程进行

5、的操作：、排序过程进行的操作：比较操作：比较两个关键字的大小比较操作：比较两个关键字的大小-必不可少的操作。必不可少的操作。改改变变记记录录的的逻逻辑辑联联系系或或将将一一个个记记录录从从一一个个位位置置移移动动到到另另一个位置。一个位置。是否需要移动，与待排序记录的存储方式有关：是否需要移动，与待排序记录的存储方式有关：以以顺顺序序表表作作为为存存储储结结构构：当当两两个个记记录录关关键键字字不不满满足足给给定定关系时，必须移动记录。关系时，必须移动记录。以以链链表表作作为为存存储储结结构构，通通过过修修改改指指针针来来改改变变记记录录的的逻逻辑辑关系，不需移动记录。通常这种排序为链表排序。

6、关系，不需移动记录。通常这种排序为链表排序。若若存存储储在在一一组组地地址址连连续续的的存存储储单单元元中中，另另设设一一地地址址向向量量来来指指示示各各记记录录的的存存储储位位置置。排排序序过过程程中中通通过过移移动动地地址址向向量量中中的的记记录录的的“地地址址”来来改改变变记记录录的的次次序序关关系系。（排排序序完完成成后后再再调整记录的存储位置，这种存储方式的排序称为地址排序。）调整记录的存储位置，这种存储方式的排序称为地址排序。）基本基本概念概念5 5、评价排序算法的标准：、评价排序算法的标准：执行时间；执行时间；所需辅助空间。所需辅助空间。若若所所需需辅辅助助空空间间不不依依赖赖于

7、于问问题题的的规规模模n n，即即辅辅助助空空间间为为O(1)O(1)，则则称称为为就就地地排排序序。非非就就地地排排序序所所要要求求的的辅辅助助空空间间为为O(n)O(n)。排排序序算算法法的的时时间间开开销销主主要要是是关关键键字字的的比比较较次次数数和和记记录录的的移移动动次次数数。算算法法执执行行时时间间不不仅仅取取决决于于问问题题的的规规模模，而而且且取取决决于于输输入入实实例例中中的的数数据据状状态态，分分析析中中一一般般给给出出最最好好、最最坏坏和平均的三种时间性能评价。和平均的三种时间性能评价。本本章章所所讨讨论论的的排排序序，除除基基数数排排序序外外，都都是是采采用用顺顺序序

8、表表作作为存储结构。为存储结构。基本基本概念概念为了讨论方便，假设记录关键字均为整数。为了讨论方便，假设记录关键字均为整数。待排序的记录的数据类型为：待排序的记录的数据类型为：#define n 100 typedef int KeyType;typedef struct KeyType key;InfoType otherinfo;RecType;typedef RecType SeqListn+1;若若关关键键字字类类型型没没有有比比较较算算符符，可可事事先先定定义义宏宏或或函函数数来来表表示比较算符。如字符串比较。示比较算符。如字符串比较。10.2 10.2 插入排序插入排序一、插插入入

9、排排序序算算法法的的基基本本思思想想：先先将将第第一一个个记记录录看看作作一一个个有有序序子子表表，然然后后依依次次从从第第二二个个记记录录开开始始逐逐个个将将记记录录插插入入到前面的有序子表中。到前面的有序子表中。二、直接插入排序二、直接插入排序-线性插入排序线性插入排序假假设设：待待排排序序记记录录放放在在数数组组R1.n中中。把把数数组组中中记记录录分分成成两两个个区区R1.i-1和和Ri.n，其其中中R1.i-1为为有有序序区区，Ri.n为为无无序序区区。然然后后把把无无序序区区中中记记录录依依次次插插入入到到有有序序区区中中形形成成新新的的有有序序区区。这这种种方方法法通通常常称称为

10、为增增量量法法，因因为为每每次次在在有有序序区中增加一个新记录。区中增加一个新记录。初初始始时时，1个个记记录录自自然然有有序序，然然后后从从i=2开开始始，直直到到i=n为止，依次将为止，依次将Ri插入到有序区中。插入到有序区中。直接插入排序直接插入排序寻寻找找RiRi的的插插入入位位置置的的方方法法：从从j=i-1j=i-1的的记记录录位位置置开开始始依次向前比较依次向前比较:若若Ri.keyRj.key(j=i-1,i-2,.,1),Ri.key=1j=1，在在R0R0处处设设置置监监视视哨哨。即令：即令：R0=RiR0=Ri这这 样样，在在 向向 前前 搜搜 索索 过过 程程 中中，总

11、总 有有 一一 个个 记记 录录 有有Ri.keyRj.keyRi.keyRj.key。因因此此，引引入入哨哨兵兵元元素素简简化化了了边边界界条条件的判断，使得测试查找循环条件的时间减少一半。件的判断，使得测试查找循环条件的时间减少一半。直接插入排序直接插入排序设有一组待排序记录的关键自为：设有一组待排序记录的关键自为：49，38，65，97，76，13，27，49【初始关键字序列为】【初始关键字序列为】（49），），38，65，97，76，13，27，49 i=2 （38）（）（38，49），），65，97，76，13，27，49 i=3 （65）（）（38，49，65），），97，76，1

12、3，27，49 i=4 （97）（）（38，49，65，97），），76，13，27，49 i=5 （76）（）（38，49，65，76，97），），13，27，49 i=6 (13)（13，38，49，65，76，97），），27，49 i=7 (27)（13，27，38，49，65，76，97），），49 i=8 (49)（13，27，38，49，49，65，76，97）监视哨监视哨直接插入排序直接插入排序算法：算法：void InsertSort(SeqLiat&L)int i,j;for(i=2;i=L.length;+i)/对每一个对每一个RiR if LT(L.ri.key,L.r

13、i-1.key)L.r0=L.ri;for (j=i-1;LT(L.r0.key,L.rj.key);-j)/寻找插入位置寻找插入位置j L.rj+1=L.rj;/将将j.i-1 的记录后移一格的记录后移一格 L.rj+1=L.r0;/将将Ri插入到位值插入到位值j 直接插入排序直接插入排序算法分析：算法分析：空间分析：需要一个记录的辅助空间。空间分析：需要一个记录的辅助空间。时间分析：时间分析：、若若记记录录关关键键字字已已按按非非递递减减排排列列，每每趟趟排排序序插插入入，只只需需进进行行一一次次关关键键字字比比较较，则则总总的的比比较较次次数数为为n-1n-1。算算法法时时间间复杂度为复

14、杂度为O(n)O(n)。、若若关关键键字字已已按按非非递递增增排排列列,则则对对第第i i个个记记录录进进行行查查找找插入时插入时,要比较要比较i i次次,移动移动i+1i+1个记录。则总的比较次数为个记录。则总的比较次数为 i=i=（n+2n+2）(n-1)/2=(n(n-1)/2=(n2 2+n-2)/2 (i=2.n)+n-2)/2 (i=2.n)移动记录数为移动记录数为(i+1)=(n+4)(n-1)/2=(ni+1)=(n+4)(n-1)/2=(n2 2+3n-4)/2+3n-4)/2平均比较次数平均比较次数=(=(n n2 2+n-2)/2+n-1)/2=n+n-2)/2+n-1)

15、/2=n2 2/4+3n/4-1n/4+3n/4-1n2 2/4/4平均移动次数平均移动次数=(=(n n2 2+3n-4)/2+2(n-1)/2+3n-4)/2+2(n-1)/2 =n =n2 2/4+7n/4-2n/4+7n/4-2n2 2/4/4 则直接插入排序的时间复杂度为则直接插入排序的时间复杂度为O(nO(n2 2)直接插入排序为稳定的排序方法。直接插入排序为稳定的排序方法。折半插入排序折半插入排序方方法法：先先利利用用折折半半查查找找方方法法来来确确定定插插入入位位置置，然然后后向向后后移动元素进行插入。移动元素进行插入。优点：比较次数少，但移动元素个数相同。优点：比较次数少，但

16、移动元素个数相同。void BinaryInsertSort(SeqLiat&L)for(i=2;i=L.length;i+)/共进行共进行n-1n-1次插入次插入 L.r0=L.ri;left=1；right=i-1;while(left=right)mid=(left+right)/2;if(L.r0.key=left;j-)L.rj+1=L.rj;/元素后移元素后移L.rleft=L.r0;希尔插入排序希尔插入排序希尔排序（希尔排序（shells mothod）也称也称“缩小增量排序缩小增量排序”。直直接接插插入入排排序序：若若待待排排记记录录为为“正正序序”时时，时时间间复复杂杂度度为

17、为O(n),O(n),即即:待排记录基本有序时，效率高；待排记录基本有序时，效率高；当当n n很小时，效率也很高。很小时，效率也很高。希希尔尔排排序序正正是是针针对对这这两两个个特特点点对对直直接接插插入入排排序序进进行行改改造造的一种插入排序方法。的一种插入排序方法。基基本本思思想想：先先将将整整个个待待排排记记录录分分割割成成若若干干个个子子序序列列分分别别进进行行直直接接插插入入排排序序。待待整整个个序序列列基基本本有有序序时时，再再对对全全部部记记录进行一次直接插入排序。录进行一次直接插入排序。分分割割方方法法：选选定定一一个个记记录录的的间间隔隔值值d d，将将所所有有间间隔隔d d

18、的的记记录录作作为为一一组组。在在组组内内进进行行直直接接插插入入排排序序。然然后后缩缩小小间间隔隔，重新分组，再进行组内重新排序，直到间隔为重新分组，再进行组内重新排序，直到间隔为1 1为止。为止。希尔插入排序希尔插入排序例如例如:设待排序列为设待排序列为 49 38 65 97 76 13 27 4 9 55 04按如下方式分组按如下方式分组:49 38 65 97 76 13 27 4 9 55 04dh=5对各组直接排序后得到对各组直接排序后得到:13 27 4 9 55 04 49 38 65 97 76共移动记录共移动记录5 5次次希尔插入排序希尔插入排序dh=313 27 4 9

19、 55 04 49 38 65 97 76对各组直接排序后得到对各组直接排序后得到:（其中移动记录（其中移动记录2次）次）13 04 4 9 38 27 49 55 65 97 76最后最后,全序列进行一次直接插入排序得到全序列进行一次直接插入排序得到:04 13 27 38 4 9 49 55 65 76 97最后移动记录最后移动记录5 5次。共移动记录次。共移动记录1010次。直接插入排序共移动次。直接插入排序共移动2727次。次。希尔插入排序希尔插入排序di的取值的取值:希尔提出的取法：希尔提出的取法：d1=n DIV 2 di+1=(di+1)DIV 2 克努特的取法：克努特的取法：d

20、i+1=di DIV 3 其他：其他：dk=2t-k+1-1 t为排序躺数为排序躺数=(int)(log2n+1)n=10,t=3,di=7,3,1 算法中，用数组存放每趟分组的间隔。算法中，用数组存放每趟分组的间隔。即：即：d1,d2,.dt 称为增量序列。称为增量序列。希尔插入排序希尔插入排序viod Shellsort(Sqlist&L,int d ,int t)/d0.t-1=.7,3,1 for(k=0;kt;+k)fz_insert_sort(L,dk);/分成分成 dk组直接排序组直接排序 void fz_insert_sort(Sqlist&L,int dk);for(i=dk

21、+1;i0<(L.r0.key,L.rj.key);j-=dk)L.rj+dk=L.rj;L.rj+dk=L.r0;希尔插入排序希尔插入排序算法分析：算法分析：当增量序列为当增量序列为dk=2t-k+1-1时，时间复杂都为时，时间复杂都为O(n3/2)。根据经验统计，根据经验统计，shellshell排序所需比较和移动次数约为排序所需比较和移动次数约为n1.3。当当n时，时，可减少到可减少到n(log2n)2。shell排序是不稳定的排序排序是不稳定的排序。10.3 10.3 交换排序交换排序一、冒泡排序一、冒泡排序基基本本思思想想：每每次次比比较较相相邻邻元元素素关关键键字字，如如不不符

22、符合合次次序序就就立即进行交换。立即进行交换。若若把把元元素素按按纵纵向向排排列列，在在比比较较和和交交换换的的过过程程中中，关关键键字字值值小小的的记记录录就就象象气气泡泡一一样样逐逐步步往往上上冒冒，而而关关键键字字大大的的记记录录象象石石头头一一样样往往下下沉沉。每每一一次次有有一一块块大大的的石石头头沉沉到到下下面面。所所以称为冒泡排序。以称为冒泡排序。493865977613274938 496576132749 9738 4965132749 769738 491327 49 65769738 13 27 49 49 65769713 27 38 49 49 65769713 27

23、 38 49 49 657697交换排序交换排序 结结束束标标志志：若若某某遍遍处处理理无无数数据据交交换换，说说明明已已排排序序好好，可可提前结束。提前结束。若若为为正正序序，则则只只需需进进行行一一趟趟排排序序，只只进进行行n-1n-1次次关关键键字字比较，无记录移动。比较，无记录移动。若若为为逆逆序序，则则需需进进行行n-1n-1趟趟排排序序，需需进进行行n(n-1)/2n(n-1)/2次次比比较，并做等数量级的记录移动，算法时间复杂度为较，并做等数量级的记录移动，算法时间复杂度为O(nO(n2 2).).算算法法中中可可设设置置一一开开关关变变量量switchswitch，每每遍遍处处

24、理理开开始始时时，令令其为其为FALSE，该遍若有数据交换，则置成该遍若有数据交换，则置成TRUE。交换排序交换排序 算法描述：算法描述：viod Bubble_sort(Sqlist&L)for(i=L.length-1;i0;-i)switch=FALSE;for (j=0;ji;+j)if GT(L.rj.key,L.rj+1.key)L.rjL.rj+1;switch=TRUE;if(!switch)break;快速排序快速排序对冒泡排序的一种改进对冒泡排序的一种改进1 1、基基本本思思想想：通通过过一一趟趟排排序序，把把待待排排序序记记录录分分成成独独立立的的两两部部分分。其其中中一

25、一部部分分记记录录的的关关键键字字比比另另一一部部分分记记录录关关键键字字小小。然然后后再再按按上上面面方方式式对对每每一一部部分分进进行行同同样样的的分分割割排排序序，以达到整个序列有序（直到每一部分的记录数为以达到整个序列有序（直到每一部分的记录数为1 1为止）。为止）。2 2、实实现现方方法法：在在待待排排序序记记录录中中先先选选一一记记录录（通通常常选选第第一一个个记记录录）作作为为枢枢轴轴，然然后后将将所所有有关关键键字字小小于于它它的的关关键键字字的的记记录录放放在在它它的的前前面面，将将所所有有关关键键字字较较它它大大的的记记录录放放在在它它的位置之后。的位置之后。3 3、具具体

26、体做做法法：设设待待排排序序记记录录的的范范围围rlowrlowhigh,附附设设两两个个指指针针i i和和j j，其其初初值值分分别别为为lowlow和和high，设设枢枢轴轴记记录录pivot=rlow,pivotkey=pivot.key。先先从从j j所所指指记记录录向向前前搜搜索索，找找到到第第一一个个关关键键字字小小于于pivotkey的的记记录录与与pivot互互相相交交换换。然然后后从从i i所所指指位位置置起起向向后后搜搜索索，找找到到第第一一个个记记录录关关键键字字比比pivotkey大大的的记记录录与与pivot互互换换。重重复复上上面面两两步步，直直到到i=ji=j为为

27、止（该位置即为止（该位置即为pivot的位置）。的位置）。这这样样，以以枢枢轴轴记记录录作作为为分分界界线线，将将待待排排记记录录分分成成两两个个子子序列，且序列，且rlowi-1ri+1high,这一过程称为一趟排序。这一过程称为一趟排序。快速排序快速排序例：例：49 38 65 97 76 13 27 49 pivot 4949 38 65 97 76 13 27 49 i j 27 38 65 97 76 13 49 49 i j 27 38 49 97 76 13 65 49 i j 27 38 13 97 76 49 65 49 i j 27 38 13 49 76 97 65 49

28、 i j 27 38 13 49 76 97 65 49 ij 快速排序快速排序任意子系列任意子系列L.rlow.high的一趟划分算法的一趟划分算法:int partition(Sqlist&L,int low,int high)/以以L.rlow为为枢轴记录枢轴记录,对子系列对子系列L.rlow.high的一趟划分的一趟划分 L.r0=L.rlow;/把枢轴记录把枢轴记录L.rlow放在放在L.0中中,使使L.rlow空闲空闲 pivotkey=L.rlow.key;while(lowhigh)/用枢轴记录进行一趟划分用枢轴记录进行一趟划分 while(low=pivotkey)-high

29、;L.rlow=L.rhigh;/在在high端端,寻找一个比寻找一个比pivotkey小小的记录放入的记录放入low,使使L.rhigh空闲空闲 while(lowhigh&L.rlow.key=pivotkey)+low;L.rhigh=L.rlow;/在在low端端,寻找一个比寻找一个比pivotkey大大的记录放入的记录放入high,使使L.rlow空闲空闲 L.rlow=L.r0;return low;/找到枢轴记录的位置找到枢轴记录的位置low 快速排序快速排序快速排序的递归算法实现快速排序的递归算法实现void Quicksort(Sqlist&L,int low,int hig

30、h)if (lowhigh)loc=Partition(L,low,high);Quicksort(L,low,loc-1);Quicksort(L,loc+1,high);快速排序快速排序算法分析：算法分析：、辅助存储空间：由递归调用时栈的最大深度确定。辅助存储空间：由递归调用时栈的最大深度确定。最坏情况（待排记录为有序）为最坏情况（待排记录为有序）为O(n)O(n)。最好情况为最好情况为O(O(2 2n n)。、时间复杂度：平均时间为时间复杂度：平均时间为knkn2 2n n，k k为某个常数因子。为某个常数因子。经验证明，在所有同数量级的此类排序中，快速排序的常数经验证明，在所有同数量级

31、的此类排序中，快速排序的常数因子因子k k最小。即最小。即 快速排序是速度最快的排序。快速排序是速度最快的排序。时间复杂度：时间复杂度：O(nO(n2 2n n)3 3、有有序序或或基基本本有有序序：最最坏坏情情况况：O(nO(n2 2)。若若枢枢轴轴记记录录取取rlowrlow、r(low+high)/2r(low+high)/2和和rhighrhigh中中关关键键字字的的中中值值的的记记录录，并与并与rlowrlow互换，可以大大改善最坏情况的快速排序。互换，可以大大改善最坏情况的快速排序。、快快速速排排序序是是非非稳稳定定排排序序。如如 2323，2222，2121，2020，2323，

32、1212，656510.4 10.4 选择排序选择排序基基本本思思想想：每每一一趟趟从从n-i+1(i=1,2,.,n)n-i+1(i=1,2,.,n)个个记记录录中中选选取取关键字最小的记录作为有序序列中第关键字最小的记录作为有序序列中第i i个记录。个记录。一、简单选择排序一、简单选择排序-直接选择排序直接选择排序基基本本思思想想：第第i趟趟排排序序开开始始时时，有有序序区区和和无无序序区区分分别别为为R1.i-1和和Ri.n（i=1,2,.n-1）,该该趟趟排排序序则则是是从从n-i+1个个记记录录选选取取关关键键字字最最小小的的记记录录Rk，并并与与第第i（i=1,2,.,n）个个记记

33、录交换录交换,形成新的有序区和无序区。形成新的有序区和无序区。即即从从开开始始，每每次次从从剩剩余余元元素素中中选选出出最最小小（最最大大）元素。这就是直接选择排序。元素。这就是直接选择排序。Void SelectSort(SeqList&L);int i,j,k;for(i=1;i=L.lenght;i+)k=i;for(j=i+1;j=L.lenght;j+)if(Rj.keyRk.key)k=j;if(k!=i)R0=Ri;Ri=Rk;Rk=R0;直接选择排序算法分析直接选择排序算法分析算法分析：算法分析：第第i趟排序需比较趟排序需比较n-i次次,共共n-1趟趟 移动记录最少为移动记录最

34、少为0，最多为，最多为3(n-1)关键字比较为关键字比较为n(n-1)/2因此因此:算法时间复杂度为算法时间复杂度为O(n2)算法空间复杂度：算法空间复杂度：只需交换数据的一个辅助空间。为就地排序。只需交换数据的一个辅助空间。为就地排序。排序是非稳定的（交换后可能改变了相对位置）。排序是非稳定的（交换后可能改变了相对位置）。堆排序堆排序堆：设有堆：设有n个元素的序列：个元素的序列：k1,k2,.,kn 对所有的对所有的i=1,2,.,(int)(n/2)，当满足下面关系：当满足下面关系：kik2i，kik2i+1 或或 kik2i，kik2i+1 这样的序列称为堆。这样的序列称为堆。堆的两种类

35、型：堆的两种类型：根结点最小的堆根结点最小的堆-小根堆。小根堆。根结点最大的堆根结点最大的堆-大根堆。大根堆。根结点称为堆顶根结点称为堆顶 即即：在在一一棵棵完完全全二二叉叉树树中中，所所有有非非叶叶结结点点的的值值均均小小于于（或均大于）左、右孩子的值。（或均大于）左、右孩子的值。堆排序堆排序例：例：96 96，8383，2727，3838，1111，0909 12 12，3636，2424，8585，4747，3030，5353，9191对应的二叉树结构为：对应的二叉树结构为：968327381109大根堆大根堆1236248547305391小根小根堆堆堆排序堆排序堆堆排排序序：是是一一

36、种种树树型型选选择择排排序序，特特点点是是，在在排排序序过过程程中中，把把R1.nR1.n看看成成是是一一个个完完全全二二叉叉树树的的存存储储结结构构，利利用用完完全全二二叉叉树树双双亲亲结结点点和和孩孩子子结结点点的的内内在在关关系系，在在当当前前无无序序区区中中选选择关键字最大（最小）的记录。择关键字最大（最小）的记录。堆排序步骤：堆排序步骤：1、从从k-1层层的的最最右右非非叶叶结结点点开开始始，使使关关键键字字值值大大（或或小小）的的记记录录逐逐步步向向二二叉叉树树的的上上层层移移动动，最最大大（或或小小）关关键键字字记记录成为树的根结点，使其成为堆。录成为树的根结点，使其成为堆。2、

37、逐逐步步输输出出根根结结点点，令令r1=ri(i=n,n-1,.,2)，在在将将剩剩余结点调整成堆。直到输出所有结点。余结点调整成堆。直到输出所有结点。堆排序堆排序例：设由关键字集合：例：设由关键字集合：49,38,65,97,76,13,27,49)4938659776132749761327493865974949386597761327494997654976132738堆排序堆排序977665494913273838766549491327977649653849132797第第1 1个与第个与第8 8个个交换交换前前7 7个调整成堆个调整成堆2749653849137697第第1 1

38、个与第个与第7 7个交换个交换堆排序堆排序13492738496576971365274949273897第第1 1个与第个与第6 6个交换个交换前前6 6个调整成堆个调整成堆6549273849137697第第1 1个与第个与第5 5个交换个交换前前5 5个调整成堆个调整成堆4965271349273897堆排序堆排序13382749496576974965273813274997第第1 1个与第个与第4 4个交换个交换前前4 4个调整成堆个调整成堆第第1 1个与第个与第3 3个交换个交换前前3 3个调整成堆个调整成堆49652749382713974965272713384997堆排序堆排

39、序1327384949657697第第1 1个与第个与第2 2个交换个交换前前2 2个调整成堆个调整成堆4965272713384997排序完成：排序完成：13,27,38,49,49,65,76,97堆排序堆排序这里要解决两个问题：这里要解决两个问题：、如何由一个无序序列建成一个堆；、如何由一个无序序列建成一个堆；、输出一个根结点后，如何将剩余元素调整成一个堆。、输出一个根结点后，如何将剩余元素调整成一个堆。大大根根堆堆：把把一一棵棵完完全全二二叉叉树树调调整整成成堆堆的的过过程程实实际际上上是是一一个个筛筛选选过过程程，小小的的关关键键字字筛筛到到筛筛底底，大大的的关关键键字字浮浮到到筛筛

40、上上面。调整时，取左右孩子的大者进行调整。面。调整时，取左右孩子的大者进行调整。、将一个无序序列建成一个堆的方法：、将一个无序序列建成一个堆的方法：筛选过程的算法为：筛选过程的算法为：从从最最后后一一个个非非叶叶结结点点开开始始，逐逐步步向向根根结结点点，反反复复进进行行“筛筛选选”过过程程，使使其其结结点点元元素素的的关关键键字字大大于于左左右右孩孩子子结结点点的的关键字。关键字。堆排序堆排序将指定结点为根的子树调整成堆的算法：将指定结点为根的子树调整成堆的算法：void Heapadjust(Sqlist&H,int s,int m)/除结点除结点H.rs外外,H.rs+1.m为堆为堆,将

41、将s 结点调整到适当位置结点调整到适当位置 temp=H.rs;for(j=2*s;j=m;j*=2)if(j0;-i)Heapadjust(H,i,H.length);/将堆顶记录与未排序子序列末记录交换，并调整成堆将堆顶记录与未排序子序列末记录交换，并调整成堆 for(i=H.length;i1;-i)H.r0=H.r1;H.r1=H.ri;H.ri=H.r0;Heapadjust(H,1,i-1)/剩余剩余 1.i-1 个元素调整为堆个元素调整为堆 堆排序堆排序算法分析：算法分析：对对深深度度为为k k的的堆堆，筛筛选选算算法法中中进进行行关关键键字字的的比比较较次次数数至至多多为为2

42、2（k-1k-1）。建建堆堆时时，n n个个元元素素所所需需的的比比较较次次数数不不超超过过4 4n n。堆排序时，堆排序时，22n n2 2n n.堆排序在最坏的情况下，时间复杂度为堆排序在最坏的情况下，时间复杂度为O(nO(n2 2n n)仅需一个记录大小的辅助存储空间。仅需一个记录大小的辅助存储空间。堆堆排排序序方方法法当当记记录录较较少少时时，不不值值得得提提倡倡。当当n n很很大大时时，效率高。效率高。堆排序是非稳定的。堆排序是非稳定的。10.5 10.5 归并排序归并排序“归归并并”的的含含义义：将将两两个个或或两两个个以以上上有有序序表表组组合合成成一一个个新的有序表。新的有序表

43、。归归并并排排序序的的基基本本思思想想：将将待待排排序序的的n个个记记录录，看看作作n个个有有序序的的子子序序列列，每每个个子子序序列列的的长长度度为为1。然然后后两两两两归归并并，得得到到n/2个个长长度度为为2或或为为1的的子子序序列列；再再两两两两归归并并，.，如如此此重重复复，直直到到得得到到长长度度为为n的的子子序序列列为为止止。这这种种排排序序的的方方法法称称为为2_路路归并排序。归并排序。2_路路归归并并排排序序的的核核心心操操作作：将将一一维维数数组组中中前前后后两两个个有有序序序列归并为一个有序序列。序列归并为一个有序序列。例例：49，38，65，97，76，13，27，49

44、 38，49，65，97，13，76，27，49 38，49，65，97，13，27，49，76 13，27，38，49，49，65，76，97在在归归并并过过程程中中，需需要要一一个个与与原原来来长长度度相相同同的的表表存存放放归归并并结果。结果。归并排序归并排序将两个有序序列归并为一个有序序列的算法：将两个有序序列归并为一个有序序列的算法：void merge(Sqlist SR,Sqlist&TR,int i,int m,int n)/将有序表将有序表 SR.ri.m以及以及SR.rm+1.n有序归并到有序归并到 TR.ri.m中中 la=i;lb=m+1;lc=i;/序列序列 la,l

45、b,lc 的始点的始点 while(la=m&lb=n)if LT(SR.rla.key,SR.rlb.key)TR.rlc+=SR.rla+/有序合并有序合并 else TR.rlc+=SR.rlb+if(la=m)TR.rlc.n=SR.rla.m;/剩余复制剩余复制 if(lb梅花梅花3-.-梅花尖梅花尖-方块方块2-方块方块3-.-方块尖方块尖-黑桃黑桃2-黑桃黑桃3-.-黑桃尖黑桃尖-红桃红桃2-红桃红桃3-.-红桃尖红桃尖每一张有两个关键字：花色（梅花每一张有两个关键字：花色（梅花方块方块黑桃黑桃红桃）红桃）面值（面值（23.A）规定：规定：“花色花色”的地位高于面值。的地位高于面

46、值。要将扑克牌整理成上面次序，通常有两种方法：要将扑克牌整理成上面次序，通常有两种方法：、先先按按花花色色分分成成有有次次序序的的4堆堆。每每一一堆堆具具有有相相同同花花色色，再对每一堆按面值进行整理。再对每一堆按面值进行整理。、先先按按面面值值分分成成13堆堆，然然后后按按面面值值从从小小到到大大重重叠叠起起来来，再再把把整整个个牌牌颠颠倒倒过过来来再再按按不不同同花花色色分分成成4堆堆，然然后后按按花花色色从从小到大合起来，就得到所需要的次序。即小到大合起来，就得到所需要的次序。即分配和收集分配和收集。这种整理扑克牌的方法便是多关键字排序的方法。这种整理扑克牌的方法便是多关键字排序的方法。

47、基数排序基数排序设有设有n个记录的序列个记录的序列 R1,R2,.,Rn且且每每个个记记录录Ri含含有有d个个关关键键字字（Ki1,Ki2,.,Kid）,则则称称序序列列R1,R2,Rn对对关关键键字字（K1,K2,Kd）有有序序指指：对对任任意意两个记录两个记录Ri和和Rj（1=ij=n）都满足下列有序关系：都满足下列有序关系：（Ki1,Ki2,.,Kid）（Kj1,Kj2,.,Kjd）其中其中K1为最高位关键字，为最高位关键字，Kd为最低位关键字。为最低位关键字。基数排序基数排序二、基数排序二、基数排序它它是是一一种种借借助助多多关关键键字字（多多个个排排序序码码）排排序序的的思思想想来来

48、实实现单关键字排序的排序方法。现单关键字排序的排序方法。对对记记录录关关键键字字进进行行定定义义时时，总总是是要要规规定定其其长长度度和和组组成成的的字字符符。这这样样，可可以以把把d位位关关键键字字看看作作d个个关关键键字字组组成成的的一一个个多关键字。多关键字。例例如如，若若关关键键字字是是3位位数数字字组组成成，可可以以看看作作（k1,k2,k3）三三 个个 关关 键键 字字 组组 成成。有有 5个个 字字 母母 组组 成成 的的 关关 键键 字字 可可 看看 成成（k1,k2,k3,k4,k5）五五个个关关键键字字组组成成。由由数数字字组组成成的的关关键键字字有有10个个不不同同的的取

49、取值值，其其“基基”为为10；字字母母组组成成的的关关键键字字有有26个不同取值，其个不同取值，其“基基”为为26。“基基”指关键字取值的范围。指关键字取值的范围。基基数数排排序序：设设关关键键字字的的基基为为rd，从从关关键键字字低低位位起起，按按关关键键字字的的不不同同值值将将序序列列中中记记录录“分分配配”到到rd个个队队列列中中，再再从从小到大顺序小到大顺序“收集收集”起来，如此重复起来，如此重复d次。次。基数排序基数排序三、链式基数排序三、链式基数排序用用静静态态链链表表存存储储n n个个待待排排记记录录，令令表表头头记记录录指指向向第第一一个个记记录录。用链表表示队列。队列头、尾指

50、针放入数组中。用链表表示队列。队列头、尾指针放入数组中。278278，109109，063063，930930，589589，184184，505505，269269，008008，083083 109083278063930589184505269008尾指针尾指针 e0 e1 e2 e3 e4 e5 e6 e7 e8 e9头指针头指针 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9第第一一趟趟分分配配930063083184505278008109589269第第1 1趟收集之后趟收集之后 （前一个堆尾链接到下一个非空队头）（前一个堆尾链接到下一个非空队头）0632699300