关系排序器的设计

本文提出了一种用于关系查询功能磁盘系统中的关系排序器的设计。基于无比较方式设计的这种排序器采用了分组排序与归并排序相结合的方式实现，其关键部件－最大值标记逻辑由０（［√ｎ］×ｍ）个基本逻辑门构成（ｎ为待排元组个数，ｍ为元组关键字的二进位数），结构简单、规整，适宜于用ＶＬＳＩ实现。     

两步迭代自返馈神经网络排序模型

本文提出了用神经网络有效地解决排序问题的途径和方法。建立了一个自反馈神经网络排序模型，对于ｎ个元素的排序问题，利用该模型可在两个迭代步内完成，排序时间与排序问题的规模无关。该模型的空间复杂度为Ｏ（ｎ＾２）。     

基于无比较器的非数值排序器的设计

本文提出了一种“无比较”非数值排序器的设计方法及其特点。利用一个４－１６译码器和相应的计数器，数据存储器等可在Ｏ（ｍ＊ｎ）（ｎ为待排元组数，ｍ为关键字字符数）内完成排序。文中还讨论了加快排序速度的一种并行排序方法。此种排序器可以作为功能磁磁盘系统中的功能部件或人他类似的用途。     

基于流水光总线阵列上Valiant并行归并排序的实现

基于流水总线的可重构线性阵列系统（LARPBS）是一种建立在光总线上的并行计算模型，许多研究工作者已经在该模型上设计出了一些高效的并行算法。文章提出了一种基于LARPBS模型上Vnliant并行归并的实现算法，利用该法对长度为N的序列进行排序，最坏情况下可以使用N个处理器在O（logNloglogN)时间完成。     

基于散列和归并技术的有效并行排序方法

本文提出一个在共享存储多处理机系统上实现的快速、有效的并行排序算法：将长度为ｎ的待排序数据划分成ｐ个长度为ｎ／ｐ的子序列，引入散列技术并行地对这ｐ个子序列的数据进行二次散列排序，这一阶段所需的平均时间为Ｏ（ｎ／ｐ）；最后并行地将ｐ个有序子序列归并成一个长度为ｎ的有序序列，归并阶段所需的时间为Ｏ（ｎ－ｎ／
／ｐ）。整个排序算法的并行执行代价为Ｏ（ｎｐ）。本排序方法可以拓以网络并行机群环境。     

试析BANKS关键词查询系统的数据库模式

随着网络技术的发展,并且结合关键字检索技术,越来越多地需要使用关键字查询数据库,检索数据库得到的查询结果可能涉及到多个数据表的多个元组.BANKS系统是比较典型的关键词查询系统,它将数据库看作是一个模型图,每个元组对应图中的节点,元组之间的关系对应于图中的边,并且引入对候选结果元组的排序评分.     

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

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

两两比较模型的Why-not问题解释及排序

由于数据缺失，数据库用户通常无法获得查询结果中的预期答案.它被称为"Why-not问题"，即"为什么预期的元组不会出现在结果中".现有的方法通过列举可能的元组值来解释Why-not问题.枚举所给出解释的数量往往太大，无法由用户探索.完整性约束，如函数依赖，被用来排除不合格的解释.然而，许多属性在简化后解释中仅仅表示为变量，用户可能仍然无法理解.由于数据稀疏性，许多不合理的解释也会被推荐给用户.提出通过研究元组间两两比较关系，从而对Why-not问题的解释进行排序的方法.首先，重新定义为什么Why-not问题解释的形式没有变量，以便于用户理解；其次，对元组中的相等/不相等关系进行表示，提出在{0，1}表示的元组对的基础上学习统计模型，从而解决直接在原始数据上学习所带来的稀疏性问题，许多模型可以被用来推断概率，包括统计分布、分类和回归；最后，根据推断的概率对解释进行评价和排序.实验结果证明：利用统计、分类和回归方法计算两两关系概率分布的方法，可以为用户寻找Why-not问题的解释并返回较为高质量的解释.     

关于排列集p（n,r）的几种有效算法

本文在按字典排序的前提下，给出了生成排列集ｐ（ｎ，ｒ）的枚举算法，为建立ｐ（ｎ，ｒ）与它的反相集合的映射及逆映射，提供了一对编解码算法；在此编解码算法的基础上，为建立ｐ（ｎ，ｒ）与ｚ＝｛１，２，…，│ｐ（ｎ，ｒ）│｝之间的一一映射关系，还给出了相应的排序和逆排序算法。实际上，我们给出的这些算法，与已知的算法相比，更具有普遍性和优越性。     

基于流水光总线阵列上的快速可扩展并行排序算法

在Y．Pan提出的基于流水光总线阵列模型(LARPBS)上使用N个处理器对N个元素进行排序在最好情况下以O(logN)时间，最坏情况下以O(N)时间完成的并行排序算法的基础上，提出了一种LARPBS模型上的可扩展的快速并行排序算法，对N个元素进行排序，使用p(1≤P≤N)个处理器在最好情况下以O(NlogN／p)时间，最坏情况下以O(N^2／p)时间完成排序。另外还提出了一种LARPBS模型上改进的快速高效并行排序算法，该算法对N个元素进行排序使用N个处理器在最好情况下以O(log√N)时间、最坏情况下以O(√N)时间完成排序。     

On the collective sort problem for distributed tuple spaces

In systems coordinated with a distributed set of tuple spaces, it is crucial to assist agents in retrieving the tuples they are interested in. This can be achieved by sorting techniques that group similar tuples together in the same tuple space, so that the position of a tuple can be inferred by similarity. Accordingly, we formulate the collective sort problem for distributed tuple spaces, where a set of agents is in charge of moving tuples up to a complete sort has been reached, namely, each of the N tuple spaces aggregate tuples belonging to one of the N kinds available. After pointing out the requirements for effectively tackling this problem, we propose a self-organizing solution resembling brood sorting performed by ants. This is based on simple agents that perform partial observations and accordingly take decisions on tuple movement. Convergence is addressed by a fully adaptive method for simulated annealing, based on noise tuples inserted and removed by agents on a need basis so as to avoid sub-optimal sorting. Emergence of sorting properties and scalability are evaluated through stochastic simulations.     

String sorting technique for microcomputers

This paper reports the development of a sorting algorithm, called a ‘pocket sort.’ It is primarily directed to sorting of character data. The algorithm is strictly of order O(n); sorting time is directly proportional to the number of data elements to be sorted. Further, through the use of pointer - linked list data structures, no internal movement of the records containing the sort field is required. The algorithm has been implemented in Turbo Pascal. Data are presented comparing this pocket sort to other sorting techniques.     

A constant-time parallel sorting algorithm and its opticalimplementation

High-speed electronic sorting networks are difficult to implement with VLSI technology because of the dense and global connectivity required. Optics eliminates this bottleneck by offering global interconnections, massive parallelism, and noninterfering communications. We present a parallel sorting algorithm and its efficient optical implementation using currently available optical hardware. The algorithm sorts n data elements in a few steps, independent of the number of elements to be sorted. Thus, it is a constant-time sorting algorithm, that is, O(1) time     

Prufer编解码的最优算法

讨论标号树的Prufer编码的编解码算法.文献中常见的Prufer编解码算法需要O(n log n)时间.文献[1,2,4,9]提出了Prufer编解码的线性时间算法.这些算法都用到了整数排序算法,利用待排序整数的取值特殊性,得到线性时间整数排序算法.由此将Prufer编解码问题的计算归结为整数排序问题.本文从更直接的角度考察Prufer编解码问题,从简单算法出发,挖掘问题的本质特征,逐步简化,得到Prufer编码的一个非常简单实用的线性时间最优编解码算法.本文采用的解决问题的方法也具有一定的技巧,可供解决类似问题时借鉴.     

一种比QUICKSORT更快的排序算法

本文根据大多数统计数据服从正态分布的特性,在排序时不需要用传统的比较排序算法,而是根据分布函数构造出一个序号函数,运用该函数可以很快地计算出每个数据所排的位置。其排序速度大大快于QUICKSORT等比较排序,排序时间的平均特性仅为0（n）。     

Adaptive binary sorting schemes and associated interconnectionnetworks

Many routing problems in parallel processing, such as concentration and permutation problems, can be cast as sorting problems. In this paper, we consider the problem of sorting on a new model, called an adaptive sorting network. We show that any sequence of n bits can be sorted on this model in O(lg² n) bit-level delay using O(n) constant fanin gates. This improves the cost complexity of K.E. Batcher's binary sorters (1968) by a factor of O(lg² n) while matching their sorting time. The only other network that can sort binary sequences in O(n) cost is the network version of columnsort algorithm, but this requires excessive pipelining. In addition, using binary sorters, we construct permutation networks with O(n lg n) bit-level cost and O(lg³ n) bit-level delay. These results provide the asymptotically least-cost practical concentrators and permutation networks to date. We note, of course, that the well-known AKS sorting network has O(lg n) sorting time and O(n lg n) cost, but the constants hidden in these complexities are so large that our complexities outperform those of the AKS sorting network until n becomes extremely large     

基于关系数据库的脆弱性水印算法研究

为了检测对关系数据库的恶意篡改,提出了一种脆弱性数字水印算法。该算法将数据库的元组划分到不同的分组中,在对每个分组内的元组进行秘密排序的基础上,生成由属性水印和元组水印构成的分组水印矩阵,因此可以将对数据库的篡改定位在分组范围内。利用单向哈希函数及关系数据动态生成水印,不但保证了水印信息的安全性,而且也实现了水印的盲检测。理论分析和实验结果表明,该方法能够有效探测攻击者对关系数据库进行元组添加、属性值修改、元组删除和属性变化四类操作,从而为关系数据的真实性认证提供依据。     

基本有序数据的分段堆排序算法研究

本文通过堆排序算法的特生分析,结合基本有序数据的特点,提出了一种谓之分段堆的新排序方法,给出了该排序算法的描述,时间复杂度分析及用Ｃ语言编写程序进行算法比较的实验结果,算法 实验结果都表明在被排序数据基本有序的情况下,分段堆排序算法在速度上明显优地快速排序,堆排序等用排序算法。     

一种基于关系数据库的脆弱性水印算法

为了检测对关系数据库的恶意篡改,提出了一种脆弱性数字水印算法,该算法将数据库的元组划分到不同的分组中,在对分组内的所有元组进行秘密排序的基础上,生成由属性水印和元组水印构成的分组水印矩阵,从而可以将对数据库的篡改定位在分组范围内.理论分析和实验结果表明了该方法的有效性和可行性.