计算排序算法设计与分析

针对大多数排序算法只考虑了记录本身的大小和记录相对位置,而忽略了记录内部特征,提出一种计算排序算法。通过分析记录本身的特征,快速计算出记录在目标数组中的索引值,从而达到排序的目的。该算法既减少了数据范围对数组排序的影响,又适应了有限小数的排序。实验结果表明,对于密度高、范围宽、特征位数多的大数组排序问题,该算法的性能优于基数排序、计数排序、静态排序等算法。

一种新的快速求核算法

为了解决核影响属性约简算法的速度和效率等问题,提出了一种基于正区域的求核算法.采用基数排序思想计算正区域,分别得到决策属性正区域的条件属性集和除决策属性正区域的一个条件属性之外的条件属性集,并且计算这2种属性集的基数之差,以判断该条件属性是否是核属性,依次判断所有条件属性,从而快速获得所需要的核.基于正区域求核算法的时间复杂度为O(|C||U|).实验结果表明,利用该算法求核,所耗时间将随对象数的增加呈线性增长,且当对象数最大时,求核所耗时间仅为对比算法的0.6%,同时证明了该算法对各种数据集均有很好的适应性.

分组排序算法

提出了分组排序算法,详细分析了算法的原理及其时间与空间复杂度,得出了在最坏情况下的时间复杂度是θ(mn);最好情况和平均情况下的时间复杂度均是θ(nlog(n/mk));在最坏情况下的空间复杂度是O(mn-m2+m);最好情况和平均情况下的空间复杂度均是O(mklog(n/mk));并用多组随机数据与效率较高的快速算法进行仿真对比实验,试验结果说明了文中结论的正确性。这一结果,将有助于进一步设计高效的海量数据分析方法。

一种自定义顺序的字符串排序算法

现有的排序算法很难实现自定义顺序的字符串排序,提出一种自定义顺序的字符串快速排序方法.在应用连续编号定义字符排序顺序的基础上,使用哈希表结构将字符串转换成对应的整型数组,以字符的最大编号作为基数排序算法的新基数,实现字符串的基数排序.分析和实验表明,本文方法可有效实现自定义顺序的字符串排序,是一个时间和空间复杂度都是线性的排序算法,比快速排序(Quick Sort)具有更好的时间性能,且可以方便地推广到其它语言的字串排序中.

非完备信息系统的相容类快速计算

经典粗糙集理论是建立在完备信息基础上的,然而现实中,由于各种原因,很多信息系统是非完备的。相容关系是非完备信息系统的核心概念之一,如何高效地计算相容类对提高各相关算法的性能至关重要。针对非完备信息系统中求解相容类计算耗时过大的缺陷,提出了一种求解相容类的快速计算方法。实验结果也进一步表明,该方法能够有效地降低计算耗时,在效率上较现有方法有显著提高。

一种基于统计的排序算法

本文提出了一种基于统计的快速排序算法 ,并对该算法的时间复杂度和空间复杂度进行了分析 .该算法要求排序关键字满足一定的约束条件 ,其时间复杂度为 O(n) .对该算法做一些简单的修改 ,还可以将其推广到对一般关键字的排序问题 .

一种基于向量夹角的快速计算等价类算法

等价类是Rough集理论的核心概念之一,如何高效地计算等价类是提高各相关算法性能的关键.引入高维空间向量夹角的概念,根据数据在机器中的存储特点,以字节内容的最大值加1作为基数对数据进行基数排序,在此基础上设计以计算向量夹角来求信息系统等价类的算法.该算法把原来计算等价类的逻辑比较转换为数值计算,非常显著地提高了等价类的计算效率,尤其对大规模高维数据.该算法的时间复杂度为O(|C‖U|log|U|),理论分析与实验结果表明了该算法的正确性和高效性.

一种改进的中文字符串排序方法

对中文字符串排序,最快算法的时间复杂度是O(nlgn)。基数排序算法是目前最快的排序方法之一,时间复杂度是O(dn),但其一般适用于相同长度的整型数据排序。提出了一种快速的变换方法,将字符串转换为与之等长的整型数组,使用基数排序算法对代表字串的整型数组排序,用以实现对字符串的快速排序。实验表明,提出的算法能快速地进行中文字符串排序,比快速排序算法具有更好的性能,且排序时间与数据规模之间是线性关系,算法的时间复杂度为O(dn)。

超快速排序算法

快速排序算法结构简单,平均性能较佳;基数排序性能较稳定。结合快速排序和基数排序,提出超快速排序算法,通过理论分析和实验表明,新算法的性能优于快速排序算法和基数排序算法。

采用基数排序算法的MMC优化均压策略

为了减少模块化多电平变流器MMC在子模块过多时均压控制的排序运算量,同时降低子模块的开关频率,提出了一种采用基数排序算法的MMC优化均压策略。首先分析基数排序算法的原理,指出了在桥臂子模块很多时,将基数排序运用于MMC的均压控制,可以减少排序运算量;其次,根据子模块电容电压的波动允许空间和基数排序算法原理提出了一种优化均压策略,该策略通过减少基数排序中"收集"和"分配"的次数,能进一步减少排序运算量,同时也有效避免了因子模块电容电压发生微小的变化而引起的不必要的开关动作,减少开关频率。仿真分析和实验结果验证了所提出优化均压策略的可行性和高效性。

基于分布计数的基数排序方法的研究

排序是计算机科学中一个非常重要的问题。提出了一种基于分布计数的基数排序方法,给出该算法定义、算法描述、算法正确性证明和算法分析;讨论了基于该排序算法几个关键问题的解决方法。算法理论分析和实验结果研究均表明该算法时间复杂度为O(N),速度优于快速排序,是一种高效的排序方法。

谈专业竞赛对教学实践改革的促进作用

本文结合"数据结构"实践教学,探讨了高等教育大众化教育背景下计算机专业人才培养模式。通过介绍近年来我校参加的计算机专业竞赛,说明改革实践教学模式的必要性。

地址基数排序算法的设计与实现

本文提出了一种集地址排序与基数排序优点于一体的具有比传统快速排序算法性能更高的排序方法,全文给出了该算法的描述、部分源程序、时间/空间复杂度分析。本算法由于具有不需要关键字比较的特点而特别适用于大数据量的排序,又由于有不需要移动元素的特点而特别适用于大记录的排序工作,应用结果表明,该算法具有很高的实用价值。

对按位分段排序算法的研究

利用基数排序算法“分配”、“收集”的思想 ,以及二进制数据按位存贮的特征 ,改进出一种非比较排序算法———按位分段排序算法 ,并通过对该算法时间复杂度和空间复杂度的分析 。

基于Hadoop的多关键字排序方法研究

在单机环境下按多关键字对大数据排序需要较长的执行时间,为了提高按多关键字对大数据排序的效率,根据Hadoop的Map Reduce模型,给出了两种基于Hadoop的多关键字排序方法。方法一在Reduce函数中使用链式基数排序算法按多关键字对大数据并行排序,利用多个节点的计算能力提高排序的效率。方法二通过定义组合键和比较器实现了对记录的多个关键字按字节比较,节省了将字节流反序列化为对象的时间。通过实验测试了两种方法的性能,实验结果表明,两种方法均能取得较高的排序效率和较好的可扩展性。

各种内部排序算法的比较

排序是程序设计中非常重要的内容,其算法种类繁多,现介绍常用的几种排序算法,并比较了它们的异同。针对不同的序列选择最佳排序方法,以提高效率。

基于基数排序的集成服务优先队列算法

传统的服务质量(QoS)算法分为差别服务和集成服务两种,前者提供相对的服务质量保证,而后者则可以提供绝对的服务质量保证,二者最终都可以归结为优先队列算法。在核心路由器中QoS对优先队列的要求比较高,差别服务需要提供OC-768(40Gbps)线速、很大的有效排队长度和较小的最小时延。集成服务除了上述要求还需要很大的优先级数目。受到基数排序算法的启发,论文设计了一种基于基数排序的适用于集成服务的优先队列算法,具有以下特点:(1)带宽可以达到OC-768线速,优先级数目和有效排队长度不受限制,最小时延可以接受。(2)结构比较简单,不需要非常复杂的电路设计。

基于结构特征的身份证号码基数排序算法研究

通过深入研究身份证号的编码规则和基数排序算法,提出一种基于身份证号码结构特点的基数排序算法.实验表明,当问题规模较大时,执行效率优于经典基数排序算法.

基数排序及其基于位操作的优化

采用“大O表示法”客观地分析了基数排序算法的时间复杂度,给出了基数排序算法的实现和正确性的证明,并与比较排序算法作了横向的运行时间的对比。对基数排序效率不佳的现状,提出了用位操作方法来优化基数排序,并通过实验证实:优化后的基数排序算法明显提高了排序的运行速度,具有一定的实用价值,使基数排序在一定程度上可与目前最快的快速排序相比拟。

线性时间复杂度排序算法研究及应用

算法在程序设计中起着至关重要的作用,一个好的算法可以让程序变得高效。排序作为数据处理最基本的工作之一,在程序中需要大量使用。常见的几种排序算法的平均时间复杂度最优为O(nlog2n),为从根本上提高程序的运行效率,对能够在线性时间解决数据排序的算法进行了研究,并在实际问题中对桶排序算法加以了应用。