论文部分内容阅读
为了降低经典归并排序算法O（n）的附加空间并保持稳定性，提出一个新的拟就地归并算法.介绍了根据移动次数导出的段长关系进行选择的原理，给出了相应的归并及归并排序的C语言算法，用大量随机序列进行了排序对比测试；测试组数自动选取，拟合结果为比较次数约为20.13n ln （n）＋1.24n ln（n）-1.22n ，移动次数约为20.655n ln （ n ）-0.89nln（n）＋2.6n、附加栈空间O（ln（n））.得益于算法的简便性，附加程序开销小，在测试范围内实际时空耗费在同类算法中有明显优势.