首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到14条相似文献,搜索用时 46 毫秒
1.
一种基于数据块交换的快速稳定原地归并算法   总被引:2,自引:0,他引:2  
与其它排序算法相比,二路归并最适合于对2个有序子表进行排序。归并长度分别为m和n的2个有序子表,经典算法有2种。第一种算法完成归并需要附加O(m+n)的空间,O(m+n)次比较和移动。第二种算法是原地的,但完成归并需要O(m+n)次比较和O(m×n)次移动。提出了一种基于块交换的快速稳定原地二路归并算法。实验证明,该算法与以前的原地算法相比,大大降低了元素的移动次数。  相似文献   

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

3.
一种快速线性原地二路归并算法   总被引:1,自引:0,他引:1       下载免费PDF全文
将内部缓冲技术、浮洞技术与分治技术相结合-提出了一种快速线性原地二路归并算法。归并长度分别为m和n的2个有序子表(m≤n)该算法最多需要 2.5m+1.5n+次比较和7m+6n+5041次移动。如进一步降低系数-并与其他好的排序算法有机结合-理论上的原地二路归并算法必将成为比快速排序更实用的算法。因此该线性原地二路归并算法具有较高的理论和实用价值。  相似文献   

4.
介绍了一种同步原地二路归并算法。通过加入同步策略,该算法优化了内部缓冲区的使用,进一步降低了线性原地二路归并算法的线性系数。归并长度分别为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次元素移动。实验证明,与经典原地二路归并排序相比较,该同步原地二路归并算法能够极大地降低元素移动次数和算法的运行时间。  相似文献   

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

6.
介绍了一种基于满二叉树的原地快速排序算法。与经典快速排序算法相比,新算法每趟划分采用动态枢轴而不是静态枢轴,同时新算法利用满二叉树的特点计算下一趟划分的枢轴位置和元素范围,避免使用递归或开辟内存堆栈。实验表明,新算法的时间性能优于目前最好的原地排序一堆排序。原地快速排序二叉树的概念对排序算法的研究和改进具有很好的理论和实用参考价值。  相似文献   

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

8.
针对银行业务管理、高考成绩统计、气象资料整理等一类特殊“汇总”排序问题。文中提出了一种以映射、链接和归并为基础的新排序算法-映射归并排序算法(以下简称为“映射归并排序”),给出了该排序算法的描述、时间复杂度分析及用C语言编写程序进行算法比较的实验结果。算法分析和实验结果都表明:映射归并排序方法和待排序数据分布无关,其时间复杂度仅为O(N);而且在处理上述大规模“汇总”排序问题时,映射归并排序速度明显优于Flash Sort,Proportion Split Sort,2-路重复的K路归并排序和直接K路归并排序等算法。  相似文献   

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

10.
提出一种动态交换的策略,对一个元素计数后,根据计数值的大小将元素移动到序列的合适位置,使得算法在每运算一个元素后,元素间的排列都是有序的,计数值大的元素位于序列的前端,从而有效地减少了查询时间.分析了算法的时间及空间复杂度,并通过实验验证了算法的实时性与高效性.  相似文献   

11.
本文提出一种新的基于有序双端链表的比较排序算法,即ODListsort(ordered double-end linked list sort)算法。该算法首先要定义一个可共存的链表最大数量,然后通过生成链表、根据规则插入数据以及合并操作来对数据集进行排序。在ODListsort算法中,数据元素是以链表形式进行动态内存分配的,因此它比一些经典的排序算法性能更优。实验结果表明,对于随机数据集,ODListsort排序与快速排序的速度接近,比归并排序、选择排序、插入排序以及冒泡排序的速度更快;对于有序数据集,ODListsort排序的效率远超快速排序,略高于归并排序。  相似文献   

12.
详细分析2-路插入排序算法,给出了一种改进的2-路插入排序算法及其实现.这种插入排序算法不论时间复杂度还是空间复杂度,相对原2-路插入排序算法都有较好的改善。  相似文献   

13.
讨论了运用分治策略的思想实现快速排序、归并排序和堆排序三种排序算法,从分、解、合三方面剖析排序,从而得出分割方式是影响排序效率的关键,并将分治法扩展应用到更多排序方法中.  相似文献   

14.
该文通过对双向板的主梁、次梁的合理简化,并结合单块板的弹性力学理论分析结果,尤其是利用方板在三边固支、一边简支时的解析解,提出了一种新的半解析计算方法———逐边迭代平衡放松法,解决了在任意荷载以及复合荷载作用下楼板的弯曲计算问题,并基于MATLAB语言编制出通用性较强的计算程序,给出了算例.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号