二次链接桶排序法

本文进一步研究了桶排序法［１］，提出了适用于非均匀分布数据的高效率的二次链接桶排序法。本文是文献［１］中桶排序的推广。

桶排序

岭童小子很能干,常常帮助老师们做一些力所能及的事情。例如,每周五他都帮班主任统计每个同学获得的贴纸数量,并给大家排序。全班有45个同学,每个星期都要统计、排序,还不能出一丁点差错,这项任务可不轻松。而且,手工统计不仅麻烦、费时,还容易出错。有没有更好的办法呢?

基于数组的桶排序算法

经典桶排序算法以链表形式实现“桶”,处理均匀数据效率很高,是O(N)算法.但对极不均匀数据则退化成低效的O(N2)插入排序.讨论了记录携带附加数据的计数排序算法,将“桶”实现为顺序数组,避免链表的动态内存分配直接提高算法效率,并允许快排等O(NlogN)算法处理桶内数据.对均匀数据仍然保持O(N)时间复杂度,对极端不均匀数据则只退化为O(NlogN)的原算法.对一般非均匀数据,证明数组桶排序算法总体性能高于经典算法.均匀数据实验表明,桶排序算法明显优于Lin-ux下标准qsort系统调用,且数组桶排序算法效率更高.而在非均匀的正态数据实验中数组桶算法性能下降明显小于经典桶排序,总体效率仍然优于qsort的直接应用.

基于桶排序和电压离散度阈值的MMC子模块电压均衡算法

传统的MMC-HVDC子模块电压均衡冒泡排序算法存在时间复杂度高、子模块投切频繁的缺点。该文提出了一种结合桶排序算法与子模块电容电压离散度阈值的MMCHVDC子模块电容电压平衡算法。引入电压离散度阈值,将当前周期的电容电压序列与阈值进行对比,形成高压、中压、低压3组;根据桶排序的思路对3组电压序列进行区间分割;依据桥臂电流方向确定不同区间子模块的投切次序。最后通过MATLAB和PSCAD/EMTDC进行仿真,验证了所提算法在降低时间复杂度和功率模块开关频率上的有效性。

多核计算环境下的桶排序算法优化

经典并行桶排序算法的时间复杂度为O((n/p)*log(n/p)),其前提要求原始数据是在一个已知的间隔内均匀分布时,才有良好的效果。对非均匀分布的数据进行排序,最坏排序时间为O(n*logn),即退化成为串行的快速排序算法。为了解决该算法对原始数据的约束,本文提出一种改进的并行桶排序算法,对原始数据的划分不是根据数据在已知间隔中的位置,而是根据数据在序列上的位置划分数据。引入一种新的2-路归并算法,并且运用了流水线思想,设置任意分布数据排序的时间复杂度为O((n/p)*log(n/p))。

基于概率分布的桶排序算法

在桶排序算法中,如何将待排序记录均匀分配到每个"桶",是提高桶排序技术的关键.实际统计到的数据,大都在某一区间服从一定的概率分布.对于这类数据的排序,介绍一种新的方法,由其概率分布的密度函数构造一个散列函数,可将待排序的n条记录按其关键码值的大小均匀地分配到n个桶中,从而使桶排序的运行时间在任何情况下都能达到O(n).

基于桶排序的EDF调度算法优化

EDF调度算法在系统过载的情况下,就不能有效地实时调度系统中的所有任务,使任务的截止期错失率非常高.利用桶排序算法,将实时系统中任务按不同优先级等级分组排序,使得高优先级等级任务组中的任务优先被调度执行;对于其他低优先级等级任务组中的任务,根据资源利用率动态调整它们的优先级等级,从而降低实时系统的任务截止期错失率.仿真实验表明,优化后的EDF调度算法的截止期错失率,明显比优化前低,说明基于桶排序的EDF调度算法的实时任务截止期错失率比EDF调度算法低.

按字节桶分配链接排序法

本文准备提出一种谓之按字节桶分配链接的新排序方法。给出排序算法、流程图和用Ｃ语言编写程序进行实验的结果。算法分析和实验结果都表明，该排序方法的时间复杂性为Ｏ（Ｎ）且与数据的分布情况无关，附加存储开销为（Ｎ＋５１２）ε（其中ε是一个键接场所需空间的大小）［１］。该排序方法不仅在速度上明显快于快速排序法，而且在非均匀分布数据的情况下也明显快于桶排序法。

桶外排序算法的抽样分点分发策略

计算机外排序常用二阶段多路归并算法和桶算法.后者运算开销小,效率更高.但基于关键字高位比特的子文件分发策略应用受限:关键字必须是整数;得到的子文件可能大小不一;子文件数不能任意选择.基于统计学理论,提出抽样分点分发策略克服以上问题,扩展桶排序的应用范围.讨论了抽样分点估计的收敛性,给出了不发生内存溢出的保证概率.该策略使桶排序算法在SheenkSort排序系统上得到成功应用,并最终获得2003年度PennySort世界排序比赛Indy组冠军.

基于桶内动态融合的透明现象的高效绘制

基于桶排序的顺序独立透明现象绘制算法,采用桶排序原理将投影收集到同一个像素上的多个片元并排序,当发生桶内片元冲突时会产生错误的绘制结果.为此,提出一种基于桶内动态融合的透明现象的高效绘制算法.此算法采用桶内动态融合和并发读/写的方法逐一融合落入同一个桶内的所有片元,并在后处理中按从前向后的顺序融合各个桶内的颜色值.由于同时发生桶内片元冲突和读/写冲突的概率非常小,因而可以大大提高绘制结果的准确性.实验结果表明,与基于桶排序的绘制算法相比,采用文中算法可以更准确地绘制场景,生成与真实结果非常相近的绘制效果,同时算法的效率基本保持不变.

一个期望时间为O(N)的递归分组排序

1982年,Akl等人提出桶排序算法；若排序文件中的数据服从概率分布,其密度函数有界,则桶排序的平均工作量为O(N),特殊的,若排序文件中的数据服从均匀分布,则桶排序的平均工作量也为O(N)。但当数据服从正态分布时,由于数据范围无界,桶排序的平均工作量大于O(N)。

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

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

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

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

一种实用高效的安全多方排序协议

安全多方排序问题是保护用户隐私的多方协作计算中最为重要的核心问题之一。为避免基于比较的排序方法,借鉴计数排序和桶排序的思想,把多方排序问题简化为多方求和问题。采用数据压缩及巧妙的编码方法,结合安全多方求和技术,发挥蒙特卡罗算法的优势,构造了一个安全实用的多方排序协议。该协议保证了解决安全多方排序问题的安全性、有效性、公平性。

数据交换之冒泡法

在生活中,我们遇到问题怎么办?当然是想办法解决问题啦!用于解决问题的各种方法及其步骤就是算法。算法不是唯一的,针对一个问题,一千个人有一千种算法。将问题迁移到程序中,我们也要设计算法,并用计算机语言来描述算法。那么,你们知道多少种算法呢?贪心算法、穷举法、递推法、桶排序……从本期起,本刊开设“晓敏讲算法”专栏,曹晓敏老师将携星空和岭童小子这两个小伙伴,带大家走进奇妙的Scratch编程世界,讲解经典算法,攻克一个个“难题”。一起来学习吧!

一种最短路径射线追踪的快速算法

为提高最短路径射线追踪的精度,需要增加模型的剖分网格和离散节点,并增加子波传播方向,或者采用其他方法改善计算结果,这些处理会带来大量的额外计算.本文的快速算法改进了波前点的管理和子波传播的计算这两项耗时的工作,较大幅度地提高了传统算法的效率.在波前点的管理上,采用按时间步划分区间的方法,实现了波前点的桶排序管理,其效率高于传统方法中常用的堆排序算法.在子波传播的计算上,利用斯奈尔定律,同时参考来自邻近节点的波的走时,来限定当前子波传播的有效区域,排除大量不需要计算的子波传播方向.模型实算表明,本文快速算法的计算速度是传统方法的几倍至十多倍.

直线优化A^＊算法在最短路径问题中的改进与实现

最短路径算法的效率是汽车实时导航、动态路径规划等应用领域普遍关注和迫切需要解决的问题。在深入分析经典Dijkstra最短路径算法的基础上,从数据结构和搜索策略两方面对算法进行了改进,采用存储桶排序方式,提出了带启发因子的直线优化A*算法。实验结果表明改进的算法具有较高的稳定性和效率。

一种快速属性核求解算法

在RoughSet理论中,计算属性核是最重要的计算之一。以桶排序的思想设计了一个新的求解U/C的算法,其时间复杂度被降为O(|C||U|)。基于此,提出了一个新的求核算法,其时间复杂度被降为O(|C|2|U|)。通过实验证明了求核算法的高效性。

城市交通最优路径规划仿真研究

研究城市交通最优路径规划问题,由于城市交通网复杂,增加了规划的难度,传统的最优路径规划算法没有考虑城市道路网络中的交通限制问题,更忽略了车辆在道路交叉口转向延误的时间,不符合城市交通的实际情况。为了解决上述问题,首先建立了一个城市路网交通模型。然后运用线性规划方法建立最优路径规划问题的线性规划模型。最后采用桶排序算法对狄杰斯特拉算法进行优化,得到一个新的最优路径规划算法,对线性规划模型进行求解。仿真结果证明,利用算法搜索得到的最优路径更加符合实际的路网情况,为设计提供了理论依据。

显式有限元中的一种并行接触算法

开发一种显式非线性有限元分析中的并行接触算法.基于区域分割技术将桶排序全局搜索方法并行化,各处理器通过桶编号向量检测相互交叠及潜在的点-面接触对.根据数据通信的特点将接触对分为三类,对各类接触对分别设计通信策略.数值算例表明,并行算法具有较高的加速比、并行效率及良好的可扩展性.