共查询到16条相似文献,搜索用时 140 毫秒
1.
温丽萍 《数字社区&智能家居》2009,5(7):5153-5154
作为计算机应用中一项复杂而重要的技术,排序一直是计算机领域内人们感兴趣的课题,寻找速度快、附加存储空间开销小的高效排序算法也一直是计算机工作者为之追求的目标。对精度归“档”插入排序算法研究中所存在的几个问题进行商榷与讨论。 相似文献
2.
提出了一种在最大值和最小值之间的数据范围内,由待排序数据的落点百分比精确到第一位小数点后经转换所形成的固定“档”住的基础上,利用归“档”统计和直接插入排序所形成的新排序算法一精度归“档”插入排序算法。概算法在待排序数据非极不均匀的情况下,时间复杂度降为O(n),具有重要的实际意义。 相似文献
3.
4.
一种新的分"档"置换插入排序算法 总被引:1,自引:0,他引:1
近年来,人们提出了众多时间复杂度为O(n)的排序算法.但分析研究结果表明,上述排序方法都不同程度上存在着以下两点不足:(1)附加存储空间开销大,(2)排序效率过分依桢于关键字的均匀分布.基于此,表文提出了一种由分“档”、整体置换和局部直接插入排序所组成的新排序算法——分“档”置换插入排序法.算法分析和实验结果都表明:该排序方法与待排序数据分布无关,其时间复杂度为O(n),而附加存储空间开销少于0.5n,同时排序速度明显优于QuickSort、HeapSort、按字节桶分配链接排序、ProportionSplitSort等算法. 相似文献
5.
一种节省空间的排序算法 总被引:2,自引:0,他引:2
目前报道的一些排序算法,空间复杂度都比较大.提出了一种改进其空间复杂度的方法,其特点是算法简单、稳定,时间复杂度为O(n^2),空间复杂度为2n,达到下界.与传统的排序算法用变量与变量比较的思路不同,本文提出的是一种用变量与其分布区间进行比较的新思路.本算法特别适合那些范围确定且分布基本均匀的待排数据,也适合一般数据对象的排序. 相似文献
6.
本文提出了一种由分“档”、整体置换和局部直接插入排序所组成的新排序算法——分“档”置换插入排序法。算法分析和实验结果都表明:该排序方法与待排序数据分布无关,其时间复杂度为O(n),而附加存储空间开销少于0.5n,同时排序速度明显优于Quick Sort、Heap Sort、按字节桶分配链接排序、Proportion Split Sort等算法。 相似文献
7.
陈黎静 《计算机技术与发展》2010,20(8):33-36
表插入排序算法的优点在于其避免了记录的移动,算法执行的花销主要在于查找插入位置,平均时间复杂度为O(n2/4)。针对表插入排序算法中每次查找插入位置均需从表头开始的限制,提出了新的表插入排序算法,给出了相关算法描述及性能分析。大量实验表明,新的表插入排序算法的平均时间复杂度为O(n2/6),而查找插入位置所需进行的元素比较的次数平均减少了33%。结果显示虽然平均时间复杂度与其他的表插入排序算法相当,但元素比较的次数却有了很大的降低,为下一步与折半查找相结合提供了方向。 相似文献
8.
张雪坤 《电脑编程技巧与维护》2018,(5):7-9
介绍了计算机算法特别是排序算法的概念,以及评估算法性能的指标。然后介绍了常见排序算法,重点研究了选择排序的原理,并进行具体的实现,并分析了该算法的时间和空间复杂度。 相似文献
9.
10.
分“档”快速排序算法研究 总被引:3,自引:0,他引:3
文章在文献[1]的基础上,提出了一种由分“档”、整体置换和局部快速排序所组成的新排序算法——分“档”快速排序法。算法分析和实验结果都表明:在待排序数据均匀分布或正态分布的情况下,分“档”快速排序算法的时间复杂度可以达到O(n),而附加存储空间开销却仅仅为[(n+1)/2],同时排序速度明显优于Quick Sort[2]、快速分组排序[5]、分“档”统计插入排序[1]和 Proportion Split Sort[4]等算法。 相似文献
11.
基于数组的桶排序算法 总被引:1,自引:0,他引:1
经典桶排序算法以链表形式实现"桶",处理均匀数据效率很高,是O(N)算法 .但对极不均匀数据则退化成低效的O(N2)插入排序 .讨论了记录携带附加数据的计数排序算法,将"桶"实现为顺序数组,避免链表的动态内存分配直接提高算法效率,并允许快排等O(N log N)算法处理桶内数据 .对均匀数据仍然保持O(N)时间复杂度,对极端不均匀数据则只退化为O(N log N)的原算法 .对一般非均匀数据,证明数组桶排序算法总体性能高于经典算法 .均匀数据实验表明,桶排序算法明显优于Linux下标准qsort系统调用,且数组桶排序算法效率更高 .而在非均匀的正态数据实验中数组桶算法性能下降明显小于经典桶排序,总体效率仍然优于qsort的直接应用 . 相似文献
12.
13.
该文给出基因组Transhocation排序问题的一个改进多项式算法,原算法所有存储空间O(n),时间复杂度为O(n^3),文中改进算法仍采用O(n)存储空间,时间复杂度为O(n^2logn),具体地,将计算Translocation距离的时间复杂度由O(n^3)改进为O(n^2),将计算Translocation序列的时间复杂度由O(n^3)改进为O(n^2logn). 相似文献
14.
15.
插入排序算法的双链表模拟 总被引:4,自引:2,他引:2
主要讨论了插入排序算法,并用双链表模拟实现了该算法。在WIN-TC下面调试通过程序并得到正确的执行结果,从而直观地反映出插入排序算法的排序过程。 相似文献
16.