基于数据分布特性的快速排序

文中提出了一种基于数据分析特性的快速排序算法，根据被排数据的分布行性，选择数据比较次数和数据移动次数较少的排序算法，当被排数据存在ｍ个有序序列时，其算法的时间复杂度为Ｏ（ｎｌｏｇ２ｍ）其中ｍ∈（１，ｃｆ√ｎ），ｃ为某一常数，其最佳性能为Ｏ（ｎ）。当ｍ≥ｃ（√ｎ）时，保持快速排序的最佳平均性能，使排序运行于较优状态下。     

位排序--一种快速排序法

众所周知,排序速度的快慢,取决于排序算法的时间复杂度和空间复杂度。因而,排序算法设计的主导思想,就是要千方百计降低算法的时间复杂度和空间复杂度。虽然计算机硬件的运算速度越来越快,但排序算法的研究仍是算法理论中的一个重要课题。已有的排序算法很多,在所有基于“记录关键字之间比较”的排序方法中,快速排序(quick sort)是平均时间性能最好的一种方法,平均时间为O（n*log n)。但是在最坏情况下,时间复杂度却很高,为O(n^2)。     

基于改进的排列法的目标威胁评估与排序模型

结合现代防空作战的特点和指挥自动化系统的工作过程,分析了影响目标威胁评估的几个重要因素,应用多属性决策中的一种改进排列法建立了数学模型,验证了其可行性.该方法不必将各属性值精确量化,只需知道各属性间的大小关系及权重就可以进行威胁评估与排序.     

基于插值细分的逼近细分法

通过在Hassan的四点三重插值细分法中引入一个偏移变量,推导出了一种逼近细分法,从而使三重逼近细分和插值细分统一到一个细分格式.该方法利用细分格式的生成多项式,在理论上分析了提出的细分格式的一致收敛性和Ck连续性;通过对细分格式中参数u取不同的值,可对生成的极限曲线形状进行控制.数值实验结果表明,文中方法是合理有效的.     

排序算法与全排列生成算法研究

引入排序计算树和排列枚举树的概念,研究某些排序算法和全排列生成算法之间的关系,由插入排序算法直接导出了一个全排列生成算法,也由一个全排列生成算法导出了一个排序算法.     

一种新的基于邻接矩阵的拓扑排序算法

为了降低基于邻接矩阵的拓扑排序算法的复杂性，将单顶点算法框架扩展成集合算法框架，给出一些便于进行拓扑排序的有向无环图的性质。在此基础上，定义了适合进行弧删除操作和无前驱顶点判断的邻接矩阵运算，给出了有向弧邻接矩阵的存储方案，最终提出了一种时间和空间复杂度都比较低的拓扑排序算法。     

多机并行处理排序算法的分析研究

目前,在串行计算机系统中,排序算法一直没有重大突破。随着新一代计算机的发展,本文提出了一种可在多机并行计算机系统中执行的并行处理排序算法,并给出了用并行设计语言写的实用算法。最后证明了其时间复杂性是O(n)阶的。     

分段快速排序法的改进

针对分段快速排序法^[1]因分段映射策略不理想而造成算法复杂度显著增加之问题,本文提出了一种由按位块分段、分段映射和局部快速排序所组成的新排序算法－按位块分段快速排序法（以下简称为“按位块分段快速排序”）。算法分析和实验结果都表明：在待排序数据均匀分布或正态分布的情况下,按位块分段快速排序法的时间复杂度可以达到O(N),是附加存储空间开销却仅仅为N＋M（M为分段数目,1≤M≤N）,同时排序速度明显优于QuickSort^[2]、分段快速排序^[1]、分“档”统计插入排序^[5]和Proportion Split Sort^[7]等算法。     

缫丝排序算法

文中提出一种改进的排序算法,弥补了快速排序在大规模下堆栈低效及合并排序在小规模下优势不明显的问题.算法扩展了合并排序思想,从一种特殊的蚕茧缫丝工艺得到启发,使用2～6个滚轴分离待排序列中的有序片段,在滚轴始末端扩展新数据,从而达到在合并操作前增加有序子序列长度的目的.理论推导表明,缫丝排序中的基本操作数量较合并排序减少4.75N,相当于将待排序列缩小至原有规模的1/4;效率测试实验表明,缫丝排序在各种规模下均能获得相比最快经典排序算法10％～15％的稳定优势,相比前人的改进排序算法具备相当的互补性,并能有效降低排序库函数自适应选择算法的实现复杂度.     

一种新的插值方法--运动轨迹法

介绍了一种新的插值方法:运动轨迹法,把插值问题转化成求匀加速运动轨迹的问题。新的插值方法简单、计算复杂度低,可以实现实时计算,插值函数二阶按段可导并且连续。这种方法可以用于对速度要求较高、对计算精度要求较低的实际领域中。     

面向对象数据库系统中有序集合的索引技术

本文首先讨论了面向对象数据库系统中的索引技术,分析了传统的基于值的索引技术不适合于用来索引有序集合的原因,然后提出了一种新的适合于有序集合的索引机制－Ｐ＋树,同时本文也设计了一个用于测试有序集合索引机制的评价基准,根据该测试基准对本文提出的索引机制进行了系统的分析与评价。     

Vague模式排序法进行目标价值排序

提出从Fuzzy数据向Vague数据的两个转化公式,提出Vague集之间的相似度量公式。数据转化公式和相似度量公式是Vague模式排序法的两个基础。该方法能进行目标价值排序,也能为如何选择更重要攻击目标提供理论依据。应用实例表明Vague模式排序法是实用的。     

JSP实现基于中值排序基数法的BBS树状结构

用JSP实现基于中值排序基数法的BBS树状结构,给出数据结构的设计以及具体的算法实现。     

分段快速排序法

本文给出分段快速排序方法,对于给定的N个数据记录,此方法的最大平均排序时间为O(N)。本文最后给出利用三种快速排序方法在IBM—PC机上分别关于均匀分布数据记录和正态分布数据记录进行排序的实验结果。