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

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

一种快速线性原地二路归并算法

将内部缓冲技术、浮洞技术与分治技术相结合-提出了一种快速线性原地二路归并算法。归并长度 分别为m和n的2个有序子表（m≤n）该算法最多需要　2.5m＋1.5n＋次比较和7m+6n+ 5041次移动。如进一步降低系数-并与其他好的排序算法有机结合-理论上的原地二路归并算法必将成 为比快速排序更实用的算法。因此该线性原地二路归并算法具有较高的理论和实用价值。     

一种快速线性原地二路归并算法

将内部缓冲技术、浮洞技术与分治技术相结合．提出了一种快速线性原地二路归并算法。归并长度分别为m和n的2个有序子表(m≤n)，该算法最多需要2．5m 1．5n 4．5√m n次比较和7m 6n-√m n次移动。如进一步降低系数，并与其他好的排序算法有机结合，理论上的原地二路归并算法必将成为比快速排序更实用的算法。因此该线性原地二路归并算法具有较高的理论和实用价值。     

一种同步原地二路归并算法

介绍了一种同步原地二路归并算法。通过加入同步策略，该算法优化了内部缓冲区的使用，进一步降低了线性原地二路归并算法的线性系数。归并长度分别为m和n的2个有序子表（m≤n），该算法不超过2.5m＋n＋2.5〖KF(〗m〖KF)〗＋2〖KF(〗m〖KF)〗 lb m次元素比较和5m＋3n＋6〖KF(〗m〖KF)〗＋12〖KF(〗m〖KF)〗lb m次元素移动。实验证明，与经典原地二路归并排序相比较，该同步原地二路归并算法能够极大地降低元素移动次数和算法的运行时间。     

多路插入排序算法

对时间复杂性为O(n2)的传统直接插入排序,提出了一种多路直接插入排序算法,给出了相关算法描述及性能分析;讨论了新算法中的插入路数与时间复杂性的关系,得出了当路数为O√n时,时间复杂性有最小值O(n3/2)的结论;最后将多路直接插入排序算法与已有的一些直接插入排序算法进行了比较,结果明显优于已有算法.文中的算法思想同样适用于折半插入排序.     

一个拟就地稳定归并排序算法

为了降低经典归并排序算法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））.得益于算法的简便性,附加程序开销小,在测试范围内实际时空耗费在同类算法中有明显优势.     

利用手摇法对二路归并排序法的改进

在计算机处理信息的过程中,排序算法是一种重要运算．二路归并排序所需要使用的辅助空间与待排序数据规模相同,空间占有量过大,有改进的必要．利用手摇法,我们可以实现原地二路归并,且时间效率也比较理想．     

基于LARPBS模型的快速并行归并排序算法

提出了一种基于LARPBS模型上的并行归并排序算法,该算法使用M1 ε(0<ε<1)个处理器可以在O(lb lbM)时间内对Mε个有序序列进行归并.利用该归并算法对长度为N的序列进行排序,使用N1 ε个处理器可以在O((lb lb N)2)时间内完成.     

一种O(n+nlog2m)时间复杂度的排序算法

通过分析任意输入的n个数据的组成特性,设计一种O（n nlog2m）时间复杂度的排序算法,m为原始输入数据序列中有序／逆有序的子序列个数,1≤m≤n/2。此排序算法的时间复杂性结果与输入数据的概率分布假设无关。     

快速稳定表选择排序算法研究

为改进直接选择排序算法的不稳定性及对数据的不敏感性,笔者研究了表选择排序算法.该算法约定用静态链表存储待排数据,先创建有序链表,再根据链接信息将数据顺序存储.此算法不仅保证排序算法的稳定性,也使时间复杂性由原来的O(n~2/2)在最好和平均情况下分别降到O(n)和O(n~2/4)(最坏情况不变),另外还保证后续其他操作也同样具备顺序存储的优点.从排序稳定性、数据比较次数和移动次数三方面来看,本文中提出的排序算法在简单排序算法中是最优的.