《第9章排序.ppt》由会员分享,可在线阅读,更多相关《第9章排序.ppt(108页珍藏版)》请在三一文库上搜索。
1、第9章 排序,9.1排序概念,排序(sort)或分类,所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来。其确切定义如下: 输入:n个记录R1,R2,Rn,其相应的关键字分别为K1,K2,Kn。 输出:Ril,Ri2,Rin,使得Ki1Ki2Kin。(或Ki1Ki2Kin)。,2排序运算的依据-关键字,用来作排序运算依据的关键字,可以是数字类型,也可以是字符类型。 关键字的选取应根据问题的要求而定。 【例】在高考成绩统计中将每个考生作为一个记录。每条记录包含准考证号、姓名、各科的分数和总分数等项内容。若要惟一地标识一个考生的记录,则必须用“准考证号“作为关键字。若要按照考
2、生的总分数排名次,则需用“总分数“作为关键字。,排序的稳定性,当待排序记录的关键字均不相同时,排序结果是惟一的,否则排序结果不唯一。 在待排序的文件中,若存在多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,该排序方法是稳定的;若具有相同关键字的记录之间的相对次序发生变化,则称这种排序方法是不稳定的。,注意:,排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中,只要有一个实例使得算法不满足稳定性要求,则该排序算法就是不稳定的。,排序方法的分类,1按是否涉及数据的内、外存交换分 在排序过程中,若整个文件都是放在内存中处理,排序时不涉及数据的内、外存交
3、换,则称之为内部排序(简称内排序);反之,若排序过程中要进行数据的内、外存交换,则称之为外部排序。 注意: 内排序适用于记录个数不很多的小文件 外排序则适用于记录个数太多,不能一次将其全部记录放人内存的大文件。,2按策略划分内部排序方法,可以分为五类:插入排序、选择排序、交换排序、归并排序和分配排序。,按性能分类,简单排序算法:性能o(n2) 复杂排序算法:性能o(nlog2n),排序算法分析,1排序算法的基本操作 大多数排序算法都有两个基本的操作: (1) 比较两个关键字的大小; (2) 改变指向记录的指针或移动记录本身。 注意: temp=ai; ai=ai+1; ai+1=tem 第(2
4、)种基本操作的实现依赖于待排序记录的存储方式。,2待排文件的常用存储方式,(1) 以顺序表(或直接用向量)作为存储结构 排序过程:对记录本身进行物理重排(即通过关键字之间的比较判定,将记录移到合适的位置) (2) 以链表作为存储结构 排序过程:无须移动记录,仅需修改指针。通常将这类排序称为链表(或链式)排序; (3) 用顺序的方式存储待排序的记录,但同时建立一个辅助表(如包括关键字和指向记录位置的指针组成的索引表) 排序过程:只需对辅助表的表目进行物理重排(即只移动辅助表的表目,而不移动记录本身)。适用于难于在链表上实现,仍需避免排序过程中移动记录的排序方法。,用索引表实现排序,b0 b1,a
5、10,b10,3排序算法性能评价,(1) 评价排序算法好坏的标准 评价排序算法好坏的标准主要有两条: 执行时间和所需的辅助空间 算法本身的复杂程度 (2) 排序算法的空间复杂度 若排序算法所需的辅助空间并不依赖于问题的规模n,即辅助空间是O(1),则称之为就地排序(In-PlaceSou)。 非就地排序一般要求的辅助空间为O(n)。 (3) 排序算法的时间开销 大多数排序算法的时间开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的规模,还取决于输入实例中数据的状态。,文件的顺序存储结构表示,#define n l00 /假设的文件长度,即待排序的记录数目 typed
6、ef Studinfo InfoType; typedef int KeyType; /假设的关键字类型 typedef struct /记录类型 KeyType key; /关键字项 InfoType otherinfo;/其它数据项,类型InfoType依赖于具体应用而定义 RecType; typedef RecType SeqListn+1;/SeqList为顺序表类型,表中第0个单元一般用作哨兵,9.2插入法排序,插入排序(Insertion Sort)的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的数组中的适当位置,直到全部记录插入完成为止。 本节介绍两种
7、插入排序方法:直接插入排序和希尔排序。,直接插入排序基本思想,1、基本思想 假设待排序的记录存放在数组R1n中。初始时,R1自成1个有序区,无序区为R2n。从i=2起直至i=n为止,依次将Ri插入当前的有序区R1i-1中,生成含n个记录的有序区。,for(i=2;i=n;i+) 在1到i-1之间找到一个合适位置 把ai插入到这个合适的位置 ,2、第i-1趟直接插入排序:,通常将一个记录Ri(i=2,3,n-1)插入到当前的有序区,使得插入后仍保证该区间里的记录是按关键字有序的操作称第i-1趟直接插入排序。 排序过程的某一中间时刻,R被划分成两个子区间R1i-1(已排好序的有序区)和Rin(当前
8、未排序的部分,可称无序区)。 直接插入排序的基本操作是将当前无序区的第1个记录Ri插人到有序区R1i-1中适当的位置上,使R1i变为新的有序区。因为这种方法每次使有序区增加1个记录,通常称增量法。,2改进的方法,一种查找比较操作和记录移动操作交替地进行的方法。 具体做法: 将待插入记录Ri的关键字从右向左依次与有序区中记录Rj(j=i-1,i-2,1)的关键字进行比较: 若Rj的关键字大于Ri的关键字,则将Rj后移一个位置; 若Rj的关键字小于或等于Ri的关键字,则查找过程结束,j+1即为Ri的插入位置。 关键字比Ri的关键字大的记录均已后移,所以j+1的位置已经腾空,只要将Ri直接插入此位置
9、即可完成一趟直接插入排序。,直接插入排序算法,1算法描述 void lnsertSort(SeqList R) /对顺序表R中的记录R1n按递增序进行插入排序 int i,j; for(i=2;i=n;i+) /依次插入R2,Rn if(Ri.keyRi-1.key)/若Ri.key大于等于有序区中所有的keys,则Ri /应在原有位置上 R0=Ri;j=i-1; /R0是哨兵,且是Ri的副本 do /从右向左在有序区R1i-1中查找Ri的插入位置 Rj+1=Rj; /将关键字大于Ri.key的记录后移 j- ; while(R0.keyRj.key); /当Ri.keyRj.key时终止 R
10、j+1=R0;13 /Ri插入到正确的位置上 /endif /InsertSort,直接插入排序算法,1算法描述 void lnsertSort(SeqList R) /对顺序表R中的记录R1n按递增序进行插入排序 int i,j; for(i=2;i=n;i+) /依次插入R2,Rn if(Ri.keyRi-1.key)/若Ri.key大于等于有序区中所有的keys,则Ri /应在原有位置上 R0=Ri;j=i-1; /R0是哨兵,且是Ri的副本 do /从右向左在有序区R1i-1中查找Ri的插入位置 Rj+1=Rj; /将关键字大于Ri.key的记录后移 j- ; while(R0.key
11、Rj.key); /当Ri.keyRj.key时终止 Rj+1=R0;13 /Ri插入到正确的位置上 /endif /InsertSort,直接插入排序算法,1算法描述main() void lnsertSort(SeqList R) int i,j; for(i=1+d;i0 & R0.keyRj.key); Rj+d=R0; ,void f1(int a2) a0=23; a1=100; main() int b2=18,10; f1(b); pritnf( ,2哨兵的作用,算法中引进的附加记录R0称监视哨或哨兵(Sentinel)。 哨兵有两个作用: 进人查找(插入位置)循环之前,它保存
12、了Ri的副本,使不致于因记录后移而丢失Ri的内容; 它的主要作用是:在查找循环中“监视“下标变量j是否越界。一旦越界(即j=0),因为R0.key和自己比较,循环判定条件不成立使得查找循环结束,从而避免了在该循环内的每一次均要检测j是否越界(即省略了循环判定条件“j=1“)。 注意: 实际上,一切为简化边界条件而引入的附加结点(元素)均可称为哨兵。 【例】单链表中的头结点实际上是一个哨兵 引入哨兵后使得测试查找循环条件的时间大约减少了一半,所以对于记录数较大的文件节约的时间就相当可观。对于类似于排序这样使用频率非常高的算法,要尽可能地减少其运行时间。所以不能把上述算法中的哨兵视为雕虫小技,而应
13、该深刻理解并掌握这种技巧,排序过程示例,算法性能分析,最坏情形,最好情形(原来已经排序好),Cmin=n-1=O(n) Mmin=0=O(1) 平均情况C=O(n2) M=O( 直接插入法排序的最大特点,当原来已经排序好(基本上已经排序好),则速度最快,当原来的序列大致已排序好时,也比较快。,注意: 初始文件按关键字递增有序,简称“正序“。 初始文件按关键字递减有序,简称“反序“。,9.2.2希尔排序(Shell Sort),希尔排序(Shell Sort)是插入排序的一种。因DLShell于1959年提出而得名。 希尔排序基本思想 基本思想: 先取一个小于n的整数d1作为第一个增量,把文件的
14、全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序;然后,取第二个增量d2d1重复上述的分组和排序,直至所取的增量dt=1(dtdt-ld2d1),即所有记录放在同一组中进行直接插入排序为止。 该方法实质上是一种分组插入方法。 给定实例的shell排序的排序过程 假设待排序文件有10个记录,其关键字分别是: 49,38,65,97,76,13,27,49,55,04。 增量序列的取值依次为: 5,3,1,Shell排序的算法实现,1 不设监视哨的算法描述 void ShellPass(SeqList R,int d) /希尔排序中的一趟排序,d为当前增量
15、 for(i=d+1;i0&R0.key0 do increment=increment/3+1; /求下一增量 ShellPass(R,increment); /一趟增量为increment的Shell插入排序 while(increment1) /ShellSort,分析,shell排序算法性能分析,时间复杂度为=O(nlog2n)O(n2) 算法不稳定,2算法的空间复杂度分析 算法所需的辅助空间是一个监视哨,辅助空间复杂度S(n)=O(1)。是一个就地排序。 3直接插入排序的稳定性 直接插入排序是稳定的排序方法。,8.3交换排序,交换排序的基本思想是:两两比较待排序记录的关键字,发现两个
16、记录的次序相反时即进行交换,直到没有反序的记录为止。 应用交换排序基本思想的主要排序方法有:冒泡排序和快速排序。,8.3.1冒泡排序,1、排序方法 将被排序的记录数组R1n垂直排列,每个记录Ri看作是重量为Ri.key的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上“飘浮“。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。,(2)第一趟扫描,从无序区底部向上依次比较相邻的两个气泡的重量,若发现轻者在下、重者在上,则交换二者的位置。即依次比较(Rn,Rn-1),(Rn-1,Rn-2),(R2,R1);对于每对气泡(Rj+1,Rj)
17、,若Rj+1.keyRj.key,则交换Rj+1和Rj的内容。 第一趟扫描完毕时,“最轻“的气泡就飘浮到该区间的顶部,即关键字最小的记录被放在最高位置R1上。,(3)第二趟扫描,扫描R2n。扫描完毕时,“次轻“的气泡飘浮到R2的位置上 最后,经过n-1 趟扫描可得到有序区R1n,规律,n个数 n-1趟 第1趟 比较 n-1次 第2趟 比较n-2次 第i趟 比较n-i 第n-1趟 比较1次 for(i=1;iaj+1) aj与aj+1交换;,排序示例,排序示例,(2)具体算法,void BubbleSort(SeqList R) /R(ln)是待排序的文件,采用自下向上扫描,对R做冒泡排序 in
18、t i,j; Boolean exchange; /交换标志 for(i=1;ii;j-) /对当前无序区Rin自下向上扫描 if(Rj+1.keyRj.key) /交换记录 temp=Rj+1; /R0不是哨兵,仅做暂存单元 Rj+1=Rj; Rj=temp; exchange=TRUE; /发生了交换,故将交换标志置为真 if(exchange=FALSE) /本趟排序未发生交换,提前终止算法 return; /endfor(外循环) /BubbleSort,4、算法分析,(1)算法的最好时间复杂度 若文件的初始状态是正序的,一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达
19、到最小值: Cmin=n-1 Mmin=0。 冒泡排序最好的时间复杂度为O(n)。,(2)算法的最坏时间复杂度,若初始文件是反序的,需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1in-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值: Cmax=n(n-1)/2=O(n2) Mmax=3n(n-1)/2=O(n2) 冒泡排序的最坏时间复杂度为O(n2)。,(2)算法的最坏时间复杂度,若初始文件是反序的,需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1in-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,
20、比较和移动次数均达到最大值: Cmax=n(n-1)/2=O(n2) Mmax=3n(n-1)/2=O(n2) 冒泡排序的最坏时间复杂度为O(n2)。,(3)算法的平均时间复杂度为O(n2),虽然冒泡排序不一定要进行n-1趟,但由于它的记录移动次数较多,故平均时间性能比直接插入排序要差得多。,(4)算法稳定性,冒泡排序是就地排序,且它是稳定的。,(1)记住最后一次交换发生位置lastExchange的冒泡排序 在每趟扫描中,记住最后一次交换发生的位置lastExchange,(该位置之前的相邻记录均已有序)。下一趟排序开始时,R1lastExchange-1是有序区,RlastExchange
21、n是无序区。这样,一趟排序可能使当前有序区扩充多个记录,从而减少排序的趟数。具体算法【参见习题】。 (2) 改变扫描方向的冒泡排序 冒泡排序的不对称性 能一趟扫描完成排序的情况: 只有最轻的气泡位于Rn的位置,其余的气泡均已排好序,那么也只需一趟扫描就可以完成排序。 【例】对初始关键字序列12,18,42,44,45,67,94,10就仅需一趟扫描。 需要n-1趟扫描完成排序情况: 当只有最重的气泡位于R1的位置,其余的气泡均已排好序时,则仍需做n-1趟扫描才能完成排序。,9.3.2 快速排序(QuickSort),1、算法思想 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排
22、序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。 (1) 分治法的基本思想 分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。,(2)快速排序的基本思想,设当前待排序的无序区为Rlowhigh,利用分治法可将快速排序的基本思想描述为: 分解: 在Rlowhigh中任选一个记录作为基准(Pivot),以此基准将当前无序区划分为左、右两个较小的子区间Rlowpivotpos-1)和Rpivotpos+1high,并使左边子区间中所有记录的关键字均小于等于基准记录(不
23、妨记为pivot)的关键字pivot.key,右边的子区间中所有记录的关键字均大于等于pivot.key,而基准记录pivot则位于正确的位置(pivotpos)上,它无须参加后续的排序。,求解:,通过递归调用快速排序对左、右子区间Rlowpivotpos-1和Rpivotpos+1high快速排序。 组合: 因为当“求解“步骤中的两个递归调用结束时,其左、右两个子区间已有序。对快速排序而言,“组合“步骤无须做什么,可看作是空操作。,2、快速排序算法QuickSort,void QuickSort(SeqList R,int low,int high) /对Rlowhigh快速排序 int p
24、ivotpos; /划分后的基准记录的位置 if(lowhigh)/仅当区间长度大于1时才须排序 pivotpos=Partition(R,low,high); /对Rlowhigh做划分 QuickSort(R,low,pivotpos-1); /对左区间递归排序 QuickSort(R,pivotpos+1,high); /对右区间递归排序 /QuickSort,3、划分算法Partition,(1) 简单的划分方法 具体做法 第一步:(初始化)设置两个指针i和j,它们的初值分别为区间的下界和上界,即i=low,i=high;选取无序区的第一个记录Ri(即Rlow)作为基准记录,并将它保存
25、在变量pivot中; 第二步:令j自high起向左扫描,直到找到第1个关键字小于pivot.key的记录Rj,将Rj)移至i所指的位置上,这相当于Rj和基准Ri(即pivot)进行了交换,使关键字小于基准关键字pivot.key的记录移到了基准的左边,交换后Rj中相当于是pivot;然后,令i指针自i+1位置开始向右扫描,直至找到第1个关键字大于pivot.key的记录Ri,将Ri移到i所指的位置上,这相当于交换了Ri和基准Rj,使关键字大于基准关键字的记录移到了基准的右边,交换后Ri中又相当于存放了pivot;接着令指针j自位置j-1开始向左扫描,如此交替改变扫描方向,从两端各自往中间靠拢,
26、直至i=j时,i便是基准pivot最终的位置,将pivot放在此位置上就完成了一次划,划分算法:,int Partition(SeqList R,int i,int j) ReceType pivot=Ri; while(i=pivot.key) j-; if(ij) Ri+=Rj; while(ij /endwhile Ri=pivot; return i; /partition,划分算法:,int Partition(SeqList R,int i,int j) /调用Partition(R,low,high)时,对Rlowhigh做划分, /并返回基准记录的位置 ReceType piv
27、ot=Ri; /用区间的第1个记录作为基准 while(i=pivot.key) /pivot相当于在位置i上 j-; /从右向左扫描,查找第1个关键字小于pivot.key的记录Rj if(ipivot.key Rj-=Ri; /相当于交换Ri和Rj,交换后j指针减1 /endwhile Ri=pivot; /基准记录已被最后定位 return i; /partition,4、快速排序执行过程,快速递归过程,6、算法分析,快速排序的时间主要耗费在划分操作上,对长度为k的区间进行划分,共需k-1次关键字的比较。,(1)最坏时间复杂度,最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最
28、大)的记录,划分的结果是基准左边的子区间为空(或右边的子区间为空),而划分所得的另一个非空的子区间中记录数目,仅仅比划分前的无序区中记录个数减少一个。 因此,快速排序必须做n-1次划分,第i次划分开始时区间长度为n-i+1,所需的比较次数为n-i(1in-1),故总的比较次数达到最大值: Cmax = n(n-1)/2=O(n2) 如果按上面给出的划分算法,每次取当前无序区的第1个记录为基准,那么当文件的记录已按递增序(或递减序)排列时,每次划分所取的基准就是当前无序区中关键字最小(或最大)的记录,则快速排序所需的比较次数反而最多。,(2) 最好时间复杂度,在最好情况下,每次划分所取的基准都是
29、当前无序区的“中值“记录,划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数: 0(nlgn),9.4 选择法排序,选择排序(Selection Sort)的基本思想是:每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子文件的最后,直到全部记录排序完毕。 常用的选择排序方法有直接选择排序和堆排序。,直接选择排序(Straight Selection Sort),1、直接选择排序的基本思想 n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果: 初始状态:无序区为R1n,有序区为空。 第1趟排序 在无序区R1n中选出关键字最小的记录Rk,将它与无
30、序区的第1个记录R1交换,使R11和R2n分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 ,第i趟排序,第i趟排序开始时,当前有序区和无序区分别为R1i-1和Rin(1in-1)。该趟排序从当前无序区中选出关键字最小的记录Rk,将它与无序区的第1个记录Ri交换,使R1i和Ri+1n分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 这样,n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。,直接选择法排序,3、算法描述,void SelectSort(SeqList R) int i,j,k; for(i=1;in;i+)/做第i趟排序(1in-
31、1) k=i; for(j=i+1;j=n;j+) /在当前无序区Rin中选key最小的记录Rk if(Rj.keyRk.key) k=j; /k记下目前找到的最小关键字所在的位置 if(k!=i) /交换Ri和Rk R0=Ri;Ri=Rk;Rk=R0; /R0作暂存单元 /endif /endfor /SeleetSort,4、算法分析,(1)关键字比较次数 无论文件初始状态如何,在第i趟排序中选出最小关键字的记录,需做n-i次比较,因此,总的比较次数为: n(n-1)/2=0(n2) (2)记录的移动次数 当初始文件为正序时,移动次数为0 文件初态为反序时,每趟排序均要执行交换操作,总的移
32、动次数取最大值3(n-1)。 直接选择排序的平均时间复杂度为O(n2)。 (3)直接选择排序是一个就地排序,(4)稳定性分析,直接选择排序是不稳定的,9.4.2 堆排序,1、 堆排序定义,n个关键字序列Kl,K2,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质): (1) kiK2i且kiK2i+1 或(2)KiK2i且kiK2i+1(1i ) 若将此序列所存储的向量R1n看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。,例,【例】关键字序列(10,15,56,25,30,70)和(70,
33、56,30,25,15,10)分别满足堆性质(1)和(2),故它们均是堆,其对应的完全二叉树分别如小根堆示例和大根堆示例所示。,示例,2、大根堆和小根堆,根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大根堆。 注意: 堆中任一子树亦是堆。 以上讨论的堆实际上是二叉堆(Binary Heap),类似地可定义k叉堆,34,25,72,62,17,53,32,75,32,62,32,75,22,49,49,17,low=4,25,large=8,3、堆排序特点,堆排序(HeapSort)是一树形选择排序。 堆排
34、序的特点是:在排序过程中,将Rln看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系【参见二叉树的顺序存储结构】,在当前无序区中选择关键字最大(或最小)的记录。,5、堆排序 堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。,(1)用大根堆排序的基本思想, 先将初始文件R1n建成一个大根堆,此堆为初始的无序区 再将关键字最大的记录R1(即堆顶)和无序区的最后一个记录Rn交换,由此得到新的无序区R1n-1和有序区Rn,且满足R1n-1.keysRn.key 由于交换后新的根R1可能违反
35、堆性质,故应将当前无序区R1n-1调整为堆。然后再次将R1n-1中关键字最大的记录R1和该区间的最后一个记录Rn-1交换,由此得到新的无序区R1n-2和有序区Rn-1n,且仍满足关系R1n-2.keysRn-1n.keys,同样要将R1n-2调整为堆。 直到无序区只有一个元素为止。,(2)大根堆排序算法的基本操作:, 初始化操作:将R1n构造为初始堆; 每一趟排序的基本操作:将当前无序区的堆顶记录R1和该区间的最后一个记录交换,然后将新的无序区调整为堆(亦称重建堆)。,(3)堆排序的算法:,void HeapSort(SeqList R) /对R1n进行堆排序,不妨用R0做暂存单元 int i
36、; BuildHeap(R); /将R1-n建成初始堆 for(i=n;i1;i-) /对当前无序区R1i进行堆排序,共做n-1趟。 R0=R1;R1=Ri;Ri=R0; /将堆顶和堆中最后一个记录交换 Heapify(R,1,i-1); /将R1i-1重新调整为堆,仅有R1可能违反堆性质 /endfor /HeapSort,筛选法调整堆,void Heapify(SeqList R,int low,int high) int large; RecType temp=Rlow; /temp=25 for(large=2*low;large=Rlarge.key)/25=75 break; Rl
37、ow=Rlarge; low=large;low=8 Rlow=temp; ,建堆算法,void buildHeap(SeqList R) int i; for (i=n/2;i0;i-) Heapify(R,i,n);/对R进行调整,从i这个元素开始,到n ,建堆过程示例(初始),13,17,23,24,42,91,16,05,建堆过程示例(2) 88与23交换后,42,13,88,24,91,23,16,05,建堆过程示例(3) i=3符合要求,不调整,42,13,88,24,91,23,16,05,建堆过程示例(4) i=2 13与88调整,42,88,13,24,91,23,16,05
38、,建堆过程示例(5) i=1 13与88调整,05,88,23,24,42,13,16,05,调整过程,O(nlog2n) O(n2),初始状态,91,88,49,24,49,13,42,05,调整(1),13,88,23,24,42,91,16,05,调整(1A),88,13,23,24,42,91,16,05,调整(1B),88,24,23,13,42,91,16,05,效率或时间复杂度,O(nlog2n) 8个队,按循环赛,要进行多少场比赛。 8,9.5归并排序,两路归并算法 1、算法基本思路 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:Rlowm,Rm+1high,先
39、将它们合并到一个局部的暂存向量R1(相当于输出堆)中,待合并完成后将R1复制回Rlowhigh中。,(1)合并过程,合并过程中,设置i,j和p三个指针,其初值分别指向这三个记录区的起始位置。合并时依次比较Ri和Rj的关键字,取关键字较小的记录复制到R1p中,然后将被复制记录的指针i或j加1,以及指向复制位置的指针p加1。 重复这一过程直至两个输入的子文件有一个已全部复制完毕(不妨称其为空),此时将另一非空的子文件中剩余记录依次复制到R1中即可。,归并示例,i,j,k,p,o(nlog2n) ,存储空间O(n), O(1),n个数归并示例,2、归并算法,void Merge(SeqList R,
40、int low,int m,int high) /将两个有序的子文件Rlowm)和Rm+1high归并成一个有序的 /子文件Rlowhigh int i=low,j=m+1,p=0; /置初始值 RecType *R1; /R1是局部向量,若p定义为此类型指针速度更快 R1=(ReeType *)malloc(high-low+1)*sizeof(RecType); if(! R1) /申请空间失败 Error(“Insufficient memory available!“); while(i=m&j=high) /两子文件非空时取其小者输出到R1p上 R1p+=(Ri.key=Rj.key
41、)?Ri+:Rj+; while(i=m) /若第1个子文件非空,则复制剩余记录到R1中 R1p+=Ri+; while(j=high) /若第2个子文件非空,则复制剩余记录到R1中 R1p+=Rj+; for(p=0,i=low;i=high;p+,i+) Ri=R1p;/归并完成后将结果复制回Rlowhigh /Merge,2、归并算法,void Merge(SeqList R,int low,int m,int high) /该算法把R中的有序二段合并成有序一段 /第一段是low到m,第二段m+1到high int i=low,j=m+1,p=0; RecType *R1; R1=(Re
42、eType *)malloc(high-low+1)*sizeof(RecType); if(! R1) Error(“Insufficient memory available!“); while(i=m&j=high) R1p+=(Ri.key=Rj.key)?Ri+:Rj+; while(i=m) R1p+=Ri+; while(j=high) R1p+=Rj+; for(p=0,i=low;i=high;p+,i+) Ri=R1p; /Merge,具体算法如下:,void MergePass(SeqList R,int length) int i; for(i=1;i+2*length
43、-1=n;i=i+2*length) Merge(R,i,i+length-1,i+2*length-1); if(i+length-1n) Merge(R,i,i+length-1,n); /MergePass O(nlog2n),length,具体算法如下:,void MergePass(SeqList R,int length) /对R1n做一趟归并排序 int i; for(i=1;i+2*length-1=n;i=i+2*length) Merge(R,i,i+length-1,i+2*length-1); /归并长度为length的两个相邻子文件 if(i+length-1n) /尚有两个子文件,其中后一个长度小于length Merge(R,i,i+length-1,n); /归并最后两个子文件 /注意:若in且i+length-1n时,则剩余一个子文件轮空,无须归并 /MergePass,(4)二路归并排序算法,void MergeSort(SeqList R) /采用自底向上的方法,对R1n进行二路归并排序 n=13 int length; for(1ength=1;lengthn;length*=2) /做 趟归并 MergePass(R,length); /有序段长度n时终止 ,
链接地址:https://www.31doc.com/p-2553386.html