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

摘要：

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

关键词：排序、原地算法、稳定算法、二路归并、块交换

所属期刊栏目：16

分类号：TP311.12;TP301.6(计算技术、计算机技术)

在线出版日期：2004-09-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：93-96