数据结构讲义第10章.优秀PPT.ppt

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

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

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

3、序序是是一一个个将将记记录录关关键键字字无无序序的的序序列列调调整整为为一一个个按按关关键字有序键字有序(递增（非递减递增（非递减)、递减、递减(非递增非递增)的记录序列。的记录序列。用用于于排排序序的的关关键键字字KiKi：可可以以是是记记录录的的主主关关键键字字，也也可可以以是次关键字，甚至还可以是若干数据项的集合。是次关键字，甚至还可以是若干数据项的集合。若是主关键字，则排序的结果是唯一的。若是主关键字，则排序的结果是唯一的。若是次关键字，排序结果不唯一。若是次关键字，排序结果不唯一。基本基本概念概念2 2、排序的稳定性：、排序的稳定性：假假设设Ki=Kj,ijKi=Kj,ij，且且在在

4、排排序序前前的的序序列列中中RiRi领领先先RjRj（即即i ij j），若若在在排排序序后后的的序序列列中中，RiRi仍仍领领先先RjRj，则则称称所所用用的的排排序方法是稳定的。序方法是稳定的。若若在在排排序序后后的的序序列列中中，RjRj领领先先Ri Ri，则则称称所所用用的的排排序序方方法是不稳定的。法是不稳定的。排排序序算算法法的的稳稳定定性性是是指指对对全全部部输输入入实实例例而而言言，只只要要能能找找出一个实例能证明其是不稳定的，就能说明它是不稳定的。出一个实例能证明其是不稳定的，就能说明它是不稳定的。3 3、内排序：排序期间，全部记录都存放在内存。、内排序：排序期间，全部记录都

5、存放在内存。外外排排序序：排排序序期期间间，只只有有部部分分记记录录在在内内存存，随随时时存存在在记录的内外存交换。记录的内外存交换。基本基本概念概念 4、排序过程进行的操作：比较操作：比较两个关键字的大小-必不行少的操作。变更记录的逻辑联系或将一个记录从一个位置移动到另一个位置。是否须要移动，与待排序记录的存储方式有关：以依次表作为存储结构：当两个记录关键字不满足给定关系时，必需移动记录。以链表作为存储结构，通过修改指针来变更记录的逻辑关系，不需移动记录。通常这种排序为链表排序。若存储在一组地址连续的存储单元中，另设一地址向量来指示各记录的存储位置。排序过程中通过移动地址向量中的记录的“地址

6、”来变更记录的次序关系。（排序完成后再调整记录的存储位置，这种存储方式的排序称为地址排序。）基本基本概念概念5 5、评价排序算法的标准：、评价排序算法的标准：执行时间；执行时间；所需协助空间。所需协助空间。若若所所需需协协助助空空间间不不依依靠靠于于问问题题的的规规模模n n，即即协协助助空空间间为为O(1)O(1)，则则称称为为就就地地排排序序。非非就就地地排排序序所所要要求求的的协协助助空空间间为为O(n)O(n)。排排序序算算法法的的时时间间开开销销主主要要是是关关键键字字的的比比较较次次数数和和记记录录的的移移动动次次数数。算算法法执执行行时时间间不不仅仅取取决决于于问问题题的的规规模

7、模，而而且且取取决决于于输输入入实实例例中中的的数数据据状状态态，分分析析中中一一般般给给出出最最好好、最最坏坏和平均的三种时间性能评价。和平均的三种时间性能评价。本本章章所所探探讨讨的的排排序序，除除基基数数排排序序外外，都都是是接接受受依依次次表表作作为存储结构。为存储结构。基本基本概念概念为了探讨便利，假设记录关键字均为整数。为了探讨便利，假设记录关键字均为整数。待排序的记录的数据类型为：待排序的记录的数据类型为：#define n 100#define n 100 typedef int KeyType;typedef int KeyType;typedef struct typede

8、f struct KeyType key;KeyType key;InfoType otherinfo;InfoType otherinfo;RecType;RecType;typedef RecType SeqListn+1;typedef RecType SeqListn+1;若若关关键键字字类类型型没没有有比比较较算算符符，可可事事先先定定义义宏宏或或函函数数来来表表示比较算符。如字符串比较。示比较算符。如字符串比较。10.2 10.2 插入排序插入排序一、插入排序算法的基本思想：先将第一个记录看作一个有序子表，然后依次从其次个记录起先逐个将记录插入到前面的有序子表中。二、干脆插入排序-

9、线性插入排序假设：待排序记录放在数组R1.n中。把数组中记录分成两个区R1.i-1和Ri.n，其中R1.i-1为有序区，Ri.n为无序区。然后把无序区中记录依次插入到有序区中形成新的有序区。这种方法通常称为增量法，因为每次在有序区中增加一个新记录。初始时，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处处设设置置监监视

10、视哨哨。即令：即令：R0=Ri R0=Ri这这 样样，在在 向向 前前 搜搜 寻寻 过过 程程 中中，总总 有有 一一 个个 记记 录录 有有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

11、），），65，97，76，13，27，49 i=3 （65）（）（38，49，65），），97，76，13，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)void Inse

12、rtSort(SeqLiat&L)int i,j;int i,j;for for(i=2;i=L.length;+i)(i=2;i=L.length;+i)/对每一个对每一个RiRRiR if LT(L.ri.key,L.ri-1.key)if LT(L.ri.key,L.ri-1.key)L.r0=L.ri;L.r0=L.ri;for for (j=i-1;LT(j=i-1;LT(L.r0.key,(L.r0.key,L.rj.key);-j)L.rj.key);-j)/找寻插入位置找寻插入位置j j L.rj+1=L.rj;L.rj+1=L.rj;/将将j.i-1 j.i-1 的记录后移一

13、格的记录后移一格 L.rj+1=L.r0;L.rj+1=L.r0;/将将RiRi插插入到位值入到位值j j 干脆插入排序干脆插入排序算法分析：算法分析：空间分析：须要一个记录的协助空间。空间分析：须要一个记录的协助空间。时间分析：时间分析：、若若记记录录关关键键字字已已按按非非递递减减排排列列，每每趟趟排排序序插插入入，只只需需进进行行一一次次关关键键字字比比较较，则则总总的的比比较较次次数数为为n-1n-1。算算法法时时间间困难度为困难度为O(n)O(n)。、若若关关键键字字已已按按非非递递增增排排列列,则则对对第第i i个个记记录录进进行行查查找找插入时插入时,要比较要比较i i次次,移动

14、移动i+1i+1个记录。则总的比较次数为个记录。则总的比较次数为 i=i=（n+2n+2）(n-1)/2=(n2+n-2)/2 (i=2.n)(n-1)/2=(n2+n-2)/2 (i=2.n)移动记录数为移动记录数为(i+1)=(n+4)(n-1)/2=(n2+3n-4)/2(i+1)=(n+4)(n-1)/2=(n2+3n-4)/2平平 均均 比比 较较 次次 数数=(n2+n-2)/2+n-1)/2=n2/4+3n/4-=(n2+n-2)/2+n-1)/2=n2/4+3n/4-1n2/41n2/4平均移动次数平均移动次数=(n2+3n-4)/2+2(n-1)/2=(n2+3n-4)/2+

15、2(n-1)/2 =n2/4+7n/4-2n2/4 =n2/4+7n/4-2n2/4 则干脆插入排序的时间困难度为则干脆插入排序的时间困难度为O(n2)O(n2)干脆插入排序为稳定的排序方法。干脆插入排序为稳定的排序方法。折半插入排序折半插入排序方方法法：先先利利用用折折半半查查找找方方法法来来确确定定插插入入位位置置，然然后后向向后后移动元素进行插入。移动元素进行插入。优点：比较次数少，但移动元素个数相同。优点：比较次数少，但移动元素个数相同。void BinaryInsertSort(SeqLiat&L)for(i=2;i=L.length;i+)/共进行共进行n-1n-1次插入次插入 L

16、.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 mothodshells mothod）也称）也称“缩小增量排序缩小增量排序”。干干脆脆插插入入排排序序：若若待待排排记记录录为为“正正序序”时时，时时间间困困难难度度为为O(n),O(n),即即:待排记录基本有序时，效率高；待排记录基本有序时，效率高；当当n n很小时，效率也很高。很小时，效率也很高。希希尔

17、尔排排序序正正是是针针对对这这两两个个特特点点对对干干脆脆插插入入排排序序进进行行改改造造的一种插入排序方法。的一种插入排序方法。基基本本思思想想：先先将将整整个个待待排排记记录录分分割割成成若若干干个个子子序序列列分分别别进进行行干干脆脆插插入入排排序序。待待整整个个序序列列基基本本有有序序时时，再再对对全全部部记记录进行一次干脆插入排序。录进行一次干脆插入排序。分分割割方方法法：选选定定一一个个记记录录的的间间隔隔值值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 55 04 49 38 65 97 76对各组干脆排序后得到对各组干脆排序后得到:（其中移动记录（其中移动记录2次）次）13 04 4 9

19、 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 克努特的取法：克努特的取法：di+1=di DIV 3 其他：其他：dk=2t-k+1-1 t为排序躺数为排序躺数=(int)(log2n+1)n=10,t=3,di=7

20、,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+1;i0<(L.r0.key,L.rj.key);j-=dk)L.rj+dk=L.rj;L.rj+dk=L.r0;希尔插入排序希尔插入

21、排序算法分析：算法分析：当增量序列为当增量序列为dk=2t-k+1-1时，时间困难都为时，时间困难都为O(n3/2)。依据阅历统计，依据阅历统计，shell排序所需比较和移动次数约为排序所需比较和移动次数约为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 38 49 49 657697交换排序交换排序 结结束束标标记记：若若某某遍遍处处理理多多数数据据交交换换，说说明明已已排排序序好好，可可提前结束

23、。提前结束。若若为为正正序序，则则只只需需进进行行一一趟趟排排序序，只只进进行行n-1n-1次次关关键键字字比较，无记录移动。比较，无记录移动。若若为为逆逆序序，则则需需进进行行n-1n-1趟趟排排序序，需需进进行行n(n-1)/2n(n-1)/2次次比比较，并做等数量级的记录移动，算法时间困难度为较，并做等数量级的记录移动，算法时间困难度为O(n2).O(n2).算算法法中中可可设设置置一一开开关关变变量量switchswitch，每每遍遍处处理理起起先先时时，令令其为其为FALSEFALSE，该遍若有数据交换，则置成，该遍若有数据交换，则置成TRUETRUE。交换排序交换排序 算法描述：算

24、法描述：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、具具体体做做法法：设设待待排排序序记记录录的的范范围围rlowhigh,rlowhigh,附附设设两两个个指指针针i i和和j j，其其

26、初初值值分分别别为为lowlow和和highhigh，设设枢枢轴轴记记录录pivot=rlow,pivotkey=pivot.keypivot=rlow,pivotkey=pivot.key。先先从从j j所所指指记记录录向向前前搜搜寻寻，找找到到第第一一个个关关键键字字小小于于pivotkeypivotkey的的记记录录与与pivotpivot相相互互交交换换。然然后后从从i i所所指指位位置置起起向向后后搜搜寻寻，找找到到第第一一个个记记录录关关键键字字比比pivotkeypivotkey大大的的记记录录与与pivotpivot互互换换。重重复复上上面面两两步步，直直到到i=ji=j为止（

27、该位置即为为止（该位置即为pivotpivot的位置）。的位置）。这这样样，以以枢枢轴轴记记录录作作为为分分界界线线，将将待待排排记记录录分分成成两两个个子子序序列列，且且rlowi-1ri+1high,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 3

28、8 13 49 76 97 65 49 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

29、(low=pivotkey)-high;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(Sqlis

30、t&L,int low,int high)if (lowhigh)loc=Partition(L,low,high);Quicksort(L,low,loc-1);Quicksort(L,loc+1,high);快速排序快速排序算法分析：算法分析：、协助存储空间：由递归调用时栈的最大深度确定。、协助存储空间：由递归调用时栈的最大深度确定。最坏状况（待排记录为有序）为最坏状况（待排记录为有序）为O(n)O(n)。最好状况为。最好状况为O(O(2n)2n)。、时间困难度：平均时间为、时间困难度：平均时间为knkn2n2n，k k为某个常数因子。为某个常数因子。阅历证明，在全部同数量级的此类排序中，

31、快速排序的常数阅历证明，在全部同数量级的此类排序中，快速排序的常数因子因子k k最小。即最小。即 快速排序是速度最快的排序。快速排序是速度最快的排序。时间困难度：时间困难度：O(nO(n2n)2n)3 3、有序或基本有序：最坏状况：、有序或基本有序：最坏状况：O(n2)O(n2)。若枢轴记录用。若枢轴记录用rlowrlow、r(low+high)/2r(low+high)/2和和rhighrhigh中关键字的中值的记录，中关键字的中值的记录，并与并与rlowrlow互换，可以大大改善最坏状况的快速排序。互换，可以大大改善最坏状况的快速排序。、快速排序是非稳定排序。如、快速排序是非稳定排序。如

32、23 23，2222，2121，2020，2323，1212，656510.4 10.4 选择排序选择排序基基本本思思想想：每每一一趟趟从从n-i+1(i=1,2,.,n)n-i+1(i=1,2,.,n)个个记记录录中中选选取取关键字最小的记录作为有序序列中第关键字最小的记录作为有序序列中第i i个记录。个记录。一、简洁选择排序一、简洁选择排序-干脆选择排序干脆选择排序基基本本思思想想：第第i i趟趟排排序序起起先先时时，有有序序区区和和无无序序区区分分别别为为R1.i-1R1.i-1和和Ri.nRi.n（i=1,2,.n-1i=1,2,.n-1）,该该趟趟排排序序则则是是从从n-n-i+1i

33、+1个个 记记 录录 选选 取取 关关 键键 字字 最最 小小 的的 记记 录录 RkRk，并并 与与 第第i i（i=1,2,.,ni=1,2,.,n）个记录交换）个记录交换,形成新的有序区和无序区。形成新的有序区和无序区。即即从从起起先先，每每次次从从剩剩余余元元素素中中选选出出最最小小（最最大大）元素。这就是干脆选择排序。元素。这就是干脆选择排序。Void SelectSort(SeqList&L);Void SelectSort(SeqList&L);int i,j,k;int i,j,k;for(i=1;i=L.lenght;i+)for(i=1;i=L.lenght;i+)k=i;

34、k=i;for(j=i+1;j=L.lenght;j+)for(j=i+1;j=L.lenght;j+)if(Rj.keyRk.key)k=j;if(Rj.keyRk.key)k=j;if(k!=i)if(k!=i)R0=Ri;Ri=Rk;Rk=R0;R0=Ri;Ri=Rk;Rk=R0;干脆选择排序算法分析干脆选择排序算法分析算法分析：算法分析：第第i趟排序需比较趟排序需比较n-i次次,共共n-1趟趟 移动记录最少为移动记录最少为0，最多为，最多为3(n-1)关键字比较为关键字比较为n(n-1)/2因此因此:算法时间困难度为算法时间困难度为O(n2)算法空间困难度：算法空间困难度：只需交换数据

35、的一个协助空间。为就地排序。只需交换数据的一个协助空间。为就地排序。排序是非稳定的（交换后可能变更了相对位置）。排序是非稳定的（交换后可能变更了相对位置）。堆排序堆排序堆：设有堆：设有n个元素的序列：个元素的序列：k1,k2,.,kn 对全部的对全部的i=1,2,.,(int)(n/2)，当满足下面关系：，当满足下面关系：kik2i，kik2i+1 或或 kik2i，kik2i+1 这样的序列称为堆。这样的序列称为堆。堆的两种类型：堆的两种类型：根结点最小的堆根结点最小的堆-小根堆。小根堆。根结点最大的堆根结点最大的堆-大根堆。大根堆。根结点称为堆顶根结点称为堆顶 即即：在在一一棵棵完完全全二

36、二叉叉树树中中，全全部部非非叶叶结结点点的的值值均均小小于于（或均大于）左、右孩子的值。（或均大于）左、右孩子的值。堆排序堆排序例：例：96 96，8383，2727，3838，1111，0909 12 12，3636，2424，8585，4747，3030，5353，9191对应的二叉树结构为：对应的二叉树结构为：968327381109大根堆大根堆1236248547305391小根堆小根堆堆排序堆排序堆堆排排序序：是是一一种种树树型型选选择择排排序序，特特点点是是，在在排排序序过过程程中中，把把R1.nR1.n看看成成是是一一个个完完全全二二叉叉树树的的存存储储结结构构，利利用用完完全全

37、二二叉叉树树双双亲亲结结点点和和孩孩子子结结点点的的内内在在关关系系，在在当当前前无无序序区区中中选选择关键字最大（最小）的记录。择关键字最大（最小）的记录。堆排序步骤：堆排序步骤：1 1、从从k-1k-1层层的的最最右右非非叶叶结结点点起起先先，使使关关键键字字值值大大（或或小小）的的记记录录逐逐步步向向二二叉叉树树的的上上层层移移动动，最最大大（或或小小）关关键键字字记记录成为树的根结点，使其成为堆。录成为树的根结点，使其成为堆。2 2、逐逐步步输输出出根根结结点点，令令r1=ri(i=n,n-1,.,2)r1=ri(i=n,n-1,.,2)，在将剩余结点调整成堆。直到输出全部结点。在将剩

38、余结点调整成堆。直到输出全部结点。堆排序堆排序例：设由关键字集合：例：设由关键字集合：49,38,65,97,76,13,27,49)4938659776132749761327493865974949386597761327494997654976132738堆排序堆排序977665494913273838766549491327977649653849132797第第1 1个与第个与第8 8个交换个交换前前7 7个调整成堆个调整成堆2749653849137697第第1 1个与第个与第7 7个交换个交换堆排序堆排序13492738496576971365274949273897第第1 1个

39、与第个与第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堆排序堆排序1327384949657697第第1 1个与第个与第2 2个交换个交换前前2 2个调整成堆个调整成堆4965272

40、713384997排序完成：排序完成：13,27,38,49,49,65,76,97堆排序堆排序这里要解决两个问题：这里要解决两个问题：、如何由一个无序序列建成一个堆；、如何由一个无序序列建成一个堆；、输出一个根结点后，如何将剩余元素调整成一个堆。、输出一个根结点后，如何将剩余元素调整成一个堆。大大根根堆堆：把把一一棵棵完完全全二二叉叉树树调调整整成成堆堆的的过过程程事事实实上上是是一一个个筛筛选选过过程程，小小的的关关键键字字筛筛到到筛筛底底，大大的的关关键键字字浮浮到到筛筛上上面。调整时，取左右孩子的大者进行调整。面。调整时，取左右孩子的大者进行调整。、将一个无序序列建成一个堆的方法：、将

41、一个无序序列建成一个堆的方法：筛选过程的算法为：筛选过程的算法为：从从最最终终一一个个非非叶叶结结点点起起先先，逐逐步步向向根根结结点点，反反复复进进行行“筛筛选选”过过程程，使使其其结结点点元元素素的的关关键键字字大大于于左左右右孩孩子子结结点点的的关键字。关键字。堆排序堆排序将指定结点为根的子树调整成堆的算法：将指定结点为根的子树调整成堆的算法：void Heapadjust(Sqlist&H,int s,int m)/除结点除结点H.rs外外,H.rs+1.m为堆为堆,将将s 结点调整到适结点调整到适当位置当位置 temp=H.rs;for(j=2*s;j=m;j*=2)if(j0;-i

42、)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 2（k-1k-1）。建建堆堆时时，n n个个元元素素所所需需的的比比较较次次数数不不超超过过4n4n。堆排序时，堆排序

43、时，2n2n2n.2n.堆排序在最坏的状况下，时间困难度为堆排序在最坏的状况下，时间困难度为O(nO(n2n)2n)仅需一个记录大小的协助存储空间。仅需一个记录大小的协助存储空间。堆堆排排序序方方法法当当记记录录较较少少时时，不不值值得得提提倡倡。当当n n很很大大时时，效率高。效率高。堆排序是非稳定的。堆排序是非稳定的。10.5 10.5 归并排序归并排序“归归并并”的的含含义义：将将两两个个或或两两个个以以上上有有序序表表组组合合成成一一个个新的有序表。新的有序表。归归并并排排序序的的基基本本思思想想：将将待待排排序序的的n个个记记录录，看看作作n个个有有序序的的子子序序列列，每每个个子子

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

45、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,lb,lc 的始点的始点 while(la=m&lb=n)if LT(SR.rla.key,SR.rlb.key)TR.rlc+=

46、SR.rla+/有序合并有序合并 else TR.rlc+=SR.rlb+if(la=m)TR.rlc.n=SR.rla.m;/剩余复制剩余复制 if(lb2-梅花梅花3-.-3-.-梅花尖梅花尖-方块方块2-2-方块方块3-.-3-.-方块尖方块尖-黑桃黑桃2-2-黑桃黑桃3-.-3-.-黑桃尖黑桃尖-红桃红桃2-2-红桃红桃3-.-3-.-红桃尖红桃尖每一张有两个关键字：花色（梅花每一张有两个关键字：花色（梅花 方块方块 黑桃黑桃 红桃）红桃）面面值值（23.A23.A）规定：规定：“花色花色”的地位高于面值。的地位高于面值。要将扑克牌整理成上面次序，通常有两种方法：要将扑克牌整理成上面次

47、序，通常有两种方法：、先先按按花花色色分分成成有有次次序序的的4 4堆堆。每每一一堆堆具具有有相相同同花花色色，再对每一堆按面值进行整理。再对每一堆按面值进行整理。、先先按按面面值值分分成成1313堆堆，然然后后按按面面值值从从小小到到大大重重叠叠起起来来，再再把把整整个个牌牌颠颠倒倒过过来来再再按按不不同同花花色色分分成成4 4堆堆，然然后后按按花花色色从从小到大合起来，就得到所须要的次序。即安排和收集。小到大合起来，就得到所须要的次序。即安排和收集。这种整理扑克牌的方法便是多关键字排序的方法。这种整理扑克牌的方法便是多关键字排序的方法。基数排序基数排序设有设有n个记录的序列个记录的序列 R

48、1,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为最低位关键字。为最低位关键字。基数排序基数排序二、基数排序二、基数排序它它是是一一种种借借助助多多关关键键字字（多多个个排排序序码码）排排序序的的思思想想来来实实现单关键字排序的排序方法。现单关键字排序的排序方法

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

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