采用折叠-展开技术的一种并行排序算法

• 作者: 丁嘉种 朱宜学 须德
• 来源期刊: 北方交通大学学报
• 学科: 工学
• 关键词: 网孔环接式 阵列处理机 并行排序算法 折叠 展开 平均时间复杂度
• 年，卷（期）: 1998,（2）
• 所属期刊栏目: 计算机应用专辑
• 页码范围: 0
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.3969/j.issn.1673-0291.1998.02.018

摘要

给出n×n网孔环接式阵列处理机上的一种并行排序算法,它将n×n阵列上的数据折叠成n×n/k子阵列,排序后再展开到整个n×n阵列上,实现n×n项数据的行主序排序,其平均时间复杂度为(2+1/k)n+o(n).若采用n×n/k阵列模型,且各处理器初始、结束状态允许有k项数据时,该算法的平均时间复杂度只有(1+2/k)n+o(n).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	须德	北方交通大学电子信息工程学院	21	500	9.0	21.0
2	朱宜学	北方交通大学电子信息工程学院	1	0	0.0	0.0
3	丁嘉种	北方交通大学电子信息工程学院	1	0	0.0	0.0