一种基于数据块交换的快速稳定原地归并算法

• 作者: 汪林林 聂永萍 范时平
• 来源期刊: 重庆邮电学院学报(自然科学版)
• 学科: 工学
• 关键词: 排序 原地算法 稳定算法 二路归并 块交换
• 年，卷（期）: 2004,（4）
• 所属期刊栏目: 学术论文
• 页码范围: 93-96
• 页数: 4页
• 分类号: TP311.12|TP301.6
• 字数: 2876字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-825X.2004.04.024

摘要

与其它排序算法相比,二路归并最适合于对2个有序子表进行排序.归并长度分别为m和n的2个有序子表,经典算法有2种.第一种算法完成归并需要附加O(m+n)的空间,O(m+n)次比较和移动.第二种算法是原地的,但完成归并需要O(m+n)次比较和O(m×n)次移动.提出了一种基于块交换的快速稳定原地二路归并算法.实验证明,该算法与以前的原地算法相比,大大降低了元素的移动次数.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	汪林林		87	961	18.0	26.0
2	聂永萍		22	79	5.0	8.0
3	范时平		16	147	6.0	12.0