共查询到18条相似文献,搜索用时 46 毫秒
1.
一种新的分"档"置换插入排序算法 总被引:1,自引:0,他引:1
近年来,人们提出了众多时间复杂度为O(n)的排序算法.但分析研究结果表明,上述排序方法都不同程度上存在着以下两点不足:(1)附加存储空间开销大,(2)排序效率过分依桢于关键字的均匀分布.基于此,表文提出了一种由分“档”、整体置换和局部直接插入排序所组成的新排序算法——分“档”置换插入排序法.算法分析和实验结果都表明:该排序方法与待排序数据分布无关,其时间复杂度为O(n),而附加存储空间开销少于0.5n,同时排序速度明显优于QuickSort、HeapSort、按字节桶分配链接排序、ProportionSplitSort等算法. 相似文献
2.
本文提出了一种由分“档”、整体置换和局部快速排序所组成的新排序算法-分“档”快速排序法,算法分析和实验结果都表明,在待排序数据均匀分布或正态分布的情况下,分“档”快速排序算法的时间复杂度可以达到O(n),而附加存储空间开销却仅仅为[(n 1)/2],同时排序速度明显优于Quick Sort[2]、快速分组排序[5]、分“档”统计插入排序[1]和Proportion Split Sort[4]等算法。 相似文献
3.
一种新的二次分"档"链接排序算法 总被引:13,自引:2,他引:13
王向阳 《计算机研究与发展》2000,37(8):1012-1017
提出了一种谓之二次分“档”链接的新排序方法(以下简称为二次分“档”链接排序),并给出了该排序算法的描述、时间复杂度分析、空间复杂度分析及用C语言编写程序进行算法比较的实验结果,算法分析和实验结果都表明:在待排序数据满足O(△M)≤O(N)(这里,N为待排序数据个数,△M为关键字的变化范围)的情况下,二次分“档”链接排序方法与待排序数据分布无关且时间复杂度仅为O(N),而附加在存储空间开销仅为N+√ 相似文献
4.
提出了一种在最大值和最小值之间的数据范围内,由待排序数据的落点百分比精确到第一位小数点后经转换所形成的固定“档”住的基础上,利用归“档”统计和直接插入排序所形成的新排序算法一精度归“档”插入排序算法。概算法在待排序数据非极不均匀的情况下,时间复杂度降为O(n),具有重要的实际意义。 相似文献
5.
一种新的映射链接排序算法 总被引:9,自引:0,他引:9
本文通过对长记录数据特性的分析,提出了一种谓之映射链接的新排序方法(以下简称为“晌射链接排序”),给出了该排序算法的描述、时间复杂度分析及用C语言编写程序进行算法比较的实验结果。算法分析和实验结果都表明:映射连接排序方法与待排序数据分布情况无关,其时间复杂度仅为O(N);对于大规模长记录数据的排序,其速度远远优于快速排序、快速分组排序、Proportion Split Sort等算法。 相似文献
6.
循环插入排序法 总被引:2,自引:0,他引:2
唐开山 《计算机工程与应用》2005,41(12):88-91
文章提出了一种循环插入的排序方法。给出了算法思想、算法描述、算法分析和实验结果。其理论意义是改进了一类时间复杂度为O(N2)排序法的时间复杂度,其实用价值是该排序法在一类时间复杂度为O(N2)排序法中排序效率较高的,其平均排序速度比直接插入排序法、选择排序法、冒泡排序快50%~63%。 相似文献
7.
王向阳 《计算机工程与设计》2000,21(4):61-64
结合小间隔数据的特点,提出了一种谓之迁移的百序方法,给出了该排离算法的描述,时间复杂度分析及用汇编语言与程序进行算法比较的实验结果,算法分析和实验结果都表明在特排序数据间隔不太大的情况下,迁移排序算法在速度上明显优于快速排序算法。 相似文献
8.
陈黎静 《计算机技术与发展》2010,20(8):33-36
表插入排序算法的优点在于其避免了记录的移动,算法执行的花销主要在于查找插入位置,平均时间复杂度为O(n2/4)。针对表插入排序算法中每次查找插入位置均需从表头开始的限制,提出了新的表插入排序算法,给出了相关算法描述及性能分析。大量实验表明,新的表插入排序算法的平均时间复杂度为O(n2/6),而查找插入位置所需进行的元素比较的次数平均减少了33%。结果显示虽然平均时间复杂度与其他的表插入排序算法相当,但元素比较的次数却有了很大的降低,为下一步与折半查找相结合提供了方向。 相似文献
9.
均匀分布数据的分"档"统计插入排序算法研究 总被引:20,自引:0,他引:20
王向阳 《数值计算与计算机应用》2000,21(3):187-193
1.引言 排序(sorting)是计算机程序设计中的一种重要运算,它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个接关键字有序的序列.其精确定义如下: 设{Ai}=(A1,A2,…,AN)为一有限的数据集合,其中人是集合中的元素,又叫做记录.若 Ai的某个标识特征为 Ki,称凡为 Ai的关键字,又称为健或标识符.{Ai}也称为记录集合.所谓排序,就是依照集合中元素的关键宇特征,把元素排列顺序重新加以组织,使新的有序集合{Aj}对于任意的,有或. 由于排序是计算机科学中一项复杂而重要的技术,… 相似文献
10.
11.
任意分布数据的二次分"档"链接排序算法研究 总被引:4,自引:0,他引:4
本文提出一种谓之二次发“档”链接的新排序方法,给出了该排序算法的描述、时间复杂度分析、空间复杂度分析及用C语言编写程序进行算法比较的实验结果。 相似文献
12.
13.
长记录数据的映射链接排序算法研究 总被引:4,自引:1,他引:4
王向阳 《小型微型计算机系统》2000,21(6):631-633
本文针对现有排序方法处理大规模长记录数据的应用局限性,提出了一种谓之映射链接的新排序方法,给出了该排序算法的描述、时间复杂度分析及用C语言编写程序进行算法比较的实验结果。 相似文献
14.
二次分“档”链接排序算法分析 总被引:4,自引:1,他引:3
“一种新的二次分‘档’链接排序算法”一文首先以随机无符号整数为基础,证明在一定条件下,这种新的排序算法具有O(n)时间复杂度,然后在没有给出证明的情况下,将算法的适用范围推方到任意数据。对这种新的排序算法进行了深入研究,指出了原文中的几点错误,并就随机无符号整数序列和随机无符号实数序列两种情况,分别给出了二次分“档”过程的理论分析,证明这种新的排序算法不适用于随机无符号实数序列。 相似文献
16.
按字节桶分配链接排序法 总被引:13,自引:1,他引:13
本文准备提出一种谓之按字节桶分配链接的新序方法,给出排序算法,流科和用C语言编写程序进行实验的结果。算法分析和实验结果都表明,该排序方法的时间复杂性O且与数据的分布情况,附加存储开销为(N+512)ε。该排序方法不仅速度上明显快于快速排序法,而且在非均匀分布数据的民政部下了明显快于桶排序法。 相似文献
17.
工程数据大量存在于现代生产制造企业。传统工程数据上沿用的关键字查询方法具有难以处理各种异构文档、无法识别关键字在工程领域的语义等缺陷。针对此,提出一种新的工程数据关键字检索方法。该方法先通过建立代表工程数据的本体,对各种异构的工程文档用适合的工具提取文本信息,建立XML快照。XML快照为索引关键字标注了相对应的本体概念。检索框架首先将用户的查询关键字匹配到本体的概念上,在匹配的过程中,提出一种算法消减关键字的语义混淆。在此基础上,提出一种排序模型,该模型对符合查询的XML快照进行打分排序,打分着重考虑了快照在语义上满足关键字查询的程度。检索框架最后排序并返回快照对应的原始文档给用户,使异构的工程数据文档能被统一处理和查询。该方法在工程数据上的检索结果查全率、查准率高,检索结果排序合理,能适用于实际企业中的大量工程数据文档,解决了传统工程数据检索的不足。实验使用了实际数据集,验证说明了该方法的实际有效性和性能上的高效性。 相似文献
18.
本文对世界上仍在研究的N个工件在M台机器上加工的最优排序的理论及其算法问题,从相对优势递推的观点进行了研究,给出了相应的理论和算法。利用该方法,不仅可以解任意多个工件在任意多台机器上加工的最优排序确定,并计算出最省时的加工工时,其计算机排序工作量要比文中提及的“枚举法排序”少得多。 相似文献