采用折叠-展开技术的一种并行排序算法
须德
朱宜学
丁嘉种
1.北方交通大学电子信息工程学院,北京,1000442.北方交通大学电子信息工程学院,北京,1000443.北方交通大学电子信息工程学院,北京,100044
摘要：给出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).
关键词：网孔环接式阵列处理机并行排序算法折叠展开平均时间复杂度
分类号：TP301.6(计算技术、计算机技术)
论文发表日期：1998-01-01
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
英文信息