一种基于数据分块的快速原地归并算法

• 作者: 汪林林 范时平
• 来源期刊: 计算机科学
• 关键词: 原地算法 分治法 二路归并 分块 块交换 块排序
• 年，卷（期）: 2004,（8）
• 所属期刊栏目: 软件工程
• 页码范围: 204-208
• 页数: 5页
• 字数: 6464字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2004.08.060

摘要

与其它排序算法相比,二路归并最适合于对两个有序子表进行排序.归并长度分别为m和n的两个有序子表,经典算法有两种.第一种算法完成归并需要○(m+n)的附加空间,○(m+n)次比较和移动.第二种算法是原地的,但完成归并需要○(m+n)次比较和○(m×n)次移动.经过长期研究,提出了一种基于数据分块的快速原地归并算法.新算法通过将数据分块、对数据块排序等方法最多用○((m+n)log2√m+n次比较和○((m+n)3/2)次移动完成两个有序子表的原地归并.实验证明,该算法与经典的原地算法相比,极大地降低了元素的移动次数和算法的运行时间.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	汪林林	重庆邮电学院软件学院	87	961	18.0	26.0
2	范时平	重庆邮电学院软件学院	16	147	6.0	12.0