| 一种基于数据分块的快速原地归并算法 |
| |
| 引用本文： | 范时平,汪林林.一种基于数据分块的快速原地归并算法[J].计算机科学,2004,31(8):204-208. |
| |
| 作者姓名： | 范时平 汪林林 |
| |
| 作者单位： | 重庆邮电学院软件学院,重庆,400065 |
| |
| 摘 要： | 与其它排序算法相比,二路归并最适合于对两个有序子表进行排序.归并长度分别为m和n的两个有序子表,经典算法有两种.第一种算法完成归并需要○(m+n)的附加空间,○(m+n)次比较和移动.第二种算法是原地的,但完成归并需要○(m+n)次比较和○(m×n)次移动.经过长期研究,提出了一种基于数据分块的快速原地归并算法.新算法通过将数据分块、对数据块排序等方法最多用○((m+n)log2√m+n次比较和○((m+n)3/2)次移动完成两个有序子表的原地归并.实验证明,该算法与经典的原地算法相比,极大地降低了元素的移动次数和算法的运行时间.
|
| 关 键 词： | 原地算法 分治法 二路归并 分块 块交换 块排序 |
A Fast In-place Merging Algorithm on the Basis of Dividing Data into Blocks |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 万方数据 等数据库收录！ |
|
点击此处可从《计算机科学》下载全文 |
|
