什么是Polyphase Merge Sort

本篇内容主要讲解“什么是Polyphase Merge Sort”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“什么是Polyphase Merge Sort”吧!Polyphase Merge Sort是一种External Sort算法,给定N个Tapes,只需要1个Tapes作为Output设备,而且读写均为顺序读写,对于Disk/Tapes等外存设备比较友好.
Merge Sort
归并排序,其算法思想是对于2个run(已排序的数据简称)进行归并得到最终结果.
在初始状态下,可以把一个待排序的元素视为一个run,然后以2的n次方为基数逐步归并为最终结果,显然,其算法复杂度(时间)是O(nlogn).Balanced N-way Merge Sort
平衡多路归并排序,其算法思想是使用N个输入和输出设备,读取N个输入归并产生N个输出.
注:下面是一个实现样例,其中以字符”|”分隔的部分称为runPass1Pass2之所以称为平衡,是因免费云主机域名为输入和输出的”设备”是一样多的.N-way指的是可以同时对N个设备进行处理(并行).
在空间利用上,这种算法需要N个空闲设备.Polyphase Merge Sort
Polyphase Merge Sort与N-way类似,但只需要1个空闲设备,大大节省了空间.
注:下面是一个实现样例,其中以字符”|”分隔的部分称为run初始状态
Tape1 : 2 3 5 6 30 | 1 11 200 | 25 40 56 70
Tape2 : 4 7 8 10 | 15 20 35 201 | 27 33 46 78 | 13 17 27 87 90
Tape3 : EmptyPass1
Tape1 : Empty
Tape2 : 13 17 27 87 90
Tape3 : 2 3 4 5 6 7 8 10 30 | 1 11 15 20 35 200 201 | 25 27 33 40 46 56 70 78Pass 2
Tape1 : 2 3 4 5 6 7 8 10 13 17 27 30 87 90
Tape2 : Empty
Tape3 :1 11 15 20 35 200 201 | 25 27 33 40 46 56 70 78Pass3
Tape1 : Empty
Tape2 : 1 2 3 4 5 6 7 8 10 11 13 15 17 20 27 30 35 87 90 200 201
Tape3 :25 27 33 40 46 56 70 78Pass4
Tape1 : 1 2 3 4 5 6 7 8 10 11 13 15 17 20 25 27 30 33 35 40 46 56 70 78 87 90 200 201
Tape2 : Empty
Tape3 : Empty到此，相信大家对“什么是Polyphase Merge Sort”有了更深的了解，不妨来实际操作一番吧！这里是百云网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！

相关推荐: Centos7系统安装Oracle无法调出图形安装界面怎么办

这篇文章主要讲解了“Centos7系统安装Oracle无法调出图形安装界面怎么办”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“Centos7系统安装Oracle无法调出图形安装界面怎么办”吧！启动安装程序的时候…