| 一种新的多路归并排序网络 |
| |
| 引用本文： | 赵立军,刘志勇.一种新的多路归并排序网络[J].计算机研究与发展,1999,36(4). |
| |
| 作者姓名： | 赵立军 刘志勇 |
| |
| 作者单位： | 中国科学院计算技术研究所,北京,100080 |
| |
| 摘 要： | 文中提出了一种新的多路归并排序网络，该网络基于倾斜与振荡多路归并排序算法．该网络有两个主要特点．一是其基本构件为ｋ－ｓｏｒｔｅｒｓ，即ｋ个数的排序器，ｋ为任意素数，而传统的排序网络的基本构件为两个数的排序，即２－ｓｏｒｔｅｒｓ．二是该网络的延迟可以小于传统的基于２－ｓｏｒｔｅｒｓ的Ｂａｔｃｈｅｒ排序网络．文中给出了该排序网络的具体实现；作为实例给出了Ｎ＝２７，ｋ＝３时的排序网络；分析了该网络的时间延迟；通过具体设计排序网络的基本构件２－ｓｏｒｔｅｒｓ和３－ｓｏｒｔｅｒｓ，表明这种新的多路归并排序网络和Ｂａｔｃｈｅｒ排序网络相比是一种高速的排序网络．
|
| 关 键 词： | 归并 排序 多路归并 排序网络 |
AN EFFICIENT MULTIWAY MERGING-SORTING NETWORK |
| |
| ZHAO Li-Jun,LIU Zhi-Yong.AN EFFICIENT MULTIWAY MERGING-SORTING NETWORK[J].Journal of Computer Research and Development,1999,36(4). |
| |
| Authors: | ZHAO Li-Jun LIU Zhi-Yong |
| |
| Abstract: | A new efficient multiway merging sorting network is proposed,which is based on sloping and shaking multiway merging sorting algorithm.Its basic component is k sorters,i.e.,the k elements sorter.The concrete implementation of the multiway merging sorting network is discussed,and its delay time is analyzed.It is shown that compared with the Batcher sorting network,it is an efficient multiway merging sorting network.It has less delay time than the Batcher sorting network if specific design of k sorters is adopted. |
| |
| Keywords: | merging sorting multiway merging sorting network |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
