摘要
与其它排序算法相比,二路归并最适合于对2个有序子表进行排序。归并长度分别为m和n的2个有序子表,经典算法有2种。第一种算法完成归并需要附加O(m+n)的空间,O(m+n)次比较和移动。第二种算法是原地的,但完成归并需要O(m+n)次比较和O(m×n)次移动。提出了一种基于块交换的快速稳定原地二路归并算法。实验证明,该算法与以前的原地算法相比,大大降低了元素的移动次数。
Compared with other sorting algorithms ,the 2-way merge algorithm is the best one for sorting two sorted sublists. There are two classical algorithms to merge two sorted sublists of lengths m and n. The first algorithm needs O(m+n) additional space,O(m+n) comparison and O(m+n) movements. The second algorithm is in-place and needs O(m+n) comparison and O(m×n) movements. A fast stable in-place merging algorithm on the basis of swapping data blocks is introduced in the paper.The experiments certify that the new algorithm reduces the movements of the former in-place algoritm enormously.
出处
《重庆邮电学院学报（自然科学版）》
2004年第4期93-96,共4页
Journal of Chongqing University of Posts and Telecommunications(Natural Sciences Edition)
关键词
排序
原地算法
稳定算法
二路归并
块交换
sort in-place algorithm
stable algorithm
2-way merge
block swapping
