摘要
为了降低经典归并排序算法O(n)的附加空间并保持稳定性,提出一个新的拟就地归并算法.介绍了根据移动次数导出的段长关系进行选择的原理,给出了相应的归并及归并排序的C语言算法,用大量随机序列进行了排序对比测试;测试组数自动选取,拟合结果为比较次数约为20.13nln(n)+1.24nln(n)-1.22n,移动次数约为20.655nln(n)-0.89nln(n)+2.6n、附加栈空间O(ln(n)).得益于算法的简便性,附加程序开销小,在测试范围内实际时空耗费在同类算法中有明显优势.
In order to reduce the O （n） additional space of classical merge sort and keep stability, a new in-situ merging algorithm is presented. The length principle derived from the mobile number of assignments is introduced. Corresponding merge sort in C language was tested by groups of random sequences, the number of groups is also chosen automatically. Results show that the number of comparisons is about20.13nln（n）＋1.24nln（n）？1.22n, the number of assignments is about20.655nln（n）？0.89nln（n）＋2.6n, the additional stack space isO（ln（n））benefiting by simplicity and low additional program cost, the algorithm presented exhibits a clear advantage in both practical time and space consuming compared with an efficient merge sort algorithm.
出处
《湖南理工学院学报（自然科学版）》
CAS
2014年第2期45-49,共5页
Journal of Hunan Institute of Science and Technology(Natural Sciences)
关键词
归并
就地归并
归并排序
算法
merge
in-place merge
merge sort
algorithm
