针对字符串等复杂数据的一种新的高效分档混合排序算法

针对字符串及记录等复杂数据及分布不均匀的数字数据的排序问题，在全面分析与提高各种排序算法的优点的基础上提出了一种新的高效分档排序算法，并通过把它与最近排序方面的工作进行比较充分说明了它的优越性与先进性．     

分档定位排序以及向分档定位查找的发展

分析了“王向阳二次分档排序”的不足．给出了等概分档映射算法，对已知分布函数的n个任意数据，仅需遍历计算一次，就可以分为m档，实现档之间有序化(档内仍无序)．令m≥n，可以使得每档数据量期望值不大于1，待排序序列已经接近有序化了，只需用很少的时耗即可完成档内排序，从而建立一个有序且等概分档的查找表．在此基础上，提出了分档定位查找算法，其优势是：①对于待查找的某个数，不需要进行“比较”，而只要进行“计算”，就可以直接在该查找表中确定一个数据“档”作为查找目标；②可以在该“档”范围内使用折半查找等高效查找；③适用于任意数据且数据量很大的查找表；④在避免了全程查找的同时也避免了“冲突”现象．     

分档混合排序算法

对传统典型的几种排序算法：直接比较排序、冒泡排序、快速排序、分档排序与基数排序的效率进行了全面的分析与比较，在此基础上提出了一种称之为分档混合排序算法的新的排序算法，并用算例说明了它的优越性。     

一种节省空间的排序算法

目前报道的一些排序算法，空间复杂度都比较大．提出了一种改进其空间复杂度的方法，其特点是算法简单、稳定，时间复杂度为O(n^2)，空间复杂度为2n，达到下界．与传统的排序算法用变量与变量比较的思路不同，本文提出的是一种用变量与其分布区间进行比较的新思路．本算法特别适合那些范围确定且分布基本均匀的待排数据，也适合一般数据对象的排序．     

一种新的插入排序和分档检索法

本文首先提出一种谓之代码转换、分档统计转移插入的新排序方法(以下简称分档插入排序法)。给出排序算法、流程图和用BASIC及PASCAL语言编写程序进行实验的结果,算法分析和实验结果都表明在被排数据均匀分布的情况下,该排序方法的时间复杂性为O(N),附加存贮开销为2N+2(N为数据量),并且该排序方法在速度上明显快于QUICK SORT法。接着又提出一种以分档插入排序法为基础的分档检索法。给出检索算法和流程图。对该算法进行分析的结果表明:在被检索数据均匀分布的情况下,分档检索法的平均检索长度不超过1.39(1+(1/N)),附加存贮开销为N+1。     

一种新的外排序方法

本文提出一种谓之代码转换，分档外排序的新排序方法。给出排序算法及用Ｃ语言编程进行实验的结果。算法分析和实验结果都表明在被排数据的均匀分布的情况下整个排序过程只需对外存储器上的数据进行两次读写，所以该排序方法是一种速度极快的外排序方法。     

一种基于HASH变换的循环散列分档排序算法

在数据排序问题中,各种分段快速排序算法[3～11]只有对特定的数据分布类型或者符合ΔM相似文献   

排序算法的选择

影响排序效率的首要因素是算法，但算法时间复杂性的“O”表示法仅反映了渐近特性，不能作为依据来选择排序算法。本文指出了影响排序效率的一些其它因素，在实际中还需要根据这些因素选择不同的算法；文章还给出了几种排序程序的实验数据，这些数据表明当待排序数据较多时，分配排序的程序在执行时间上具有明显的优势。     

基于区间数的不确定性数据聚类算法:UD-OPTICS

在不确定性数据聚类算法的研究中,普遍需要假设不确定性数据服从某种分布,继而获得表示不确定性数据的概率密度函数或概率分布函数,然而这种假设很难保证与实际应用系统中的不确定性数据分布一致。现有的基于密度的算法对初始参数敏感,在对密度不均匀的不确定性数据聚类时,无法发现任意密度的类簇。鉴于这些不足,提出基于区间数的不确定性数据对象排序识别聚类结构算法(UD-OPTICS)。该算法利用区间数理论,结合不确定性数据的相关统计信息来更加合理地表示不确定性数据,提出了低计算复杂度的区间核心距离与区间可达距离的概念与计算方法,将其用于度量不确定性数据间的相似度,拓展类簇与对象排序识别聚类结构。该算法可很好地发现任意密度的类簇。实验结果表明,UD-OPTICS算法具有较高的聚类精度和较低的复杂度。     

基于概率可信度的区间数排序方法

针对多属性决策理论的研究需要,提出一种基于概率可信度的区间数排序方法,给出了区间数排序问题的形式化描述.为明确排序规则,定义了区间数的二元序关系.采用概率密度函数表征区间数的特征信息,并构建出区间数序关系的概率可信度模型.通过建立互补判断矩阵,将区间数排序问题转换为矩阵运算过程,实现了不同类型区间数的比较.实验结果表明,所提出方法能够有效克服传统排序方法在适用范围方面的局限性,具有排序速度快、求解质量高等优点.     

一种新的分"档"置换插入排序算法

近年来，人们提出了众多时间复杂度为O（n）的排序算法．但分析研究结果表明，上述排序方法都不同程度上存在着以下两点不足：（1）附加存储空间开销大，（2）排序效率过分依桢于关键字的均匀分布．基于此，表文提出了一种由分“档”、整体置换和局部直接插入排序所组成的新排序算法——分“档”置换插入排序法．算法分析和实验结果都表明：该排序方法与待排序数据分布无关，其时间复杂度为O（n），而附加存储空间开销少于0．5n，同时排序速度明显优于QuickSort、HeapSort、按字节桶分配链接排序、ProportionSplitSort等算法．     

Efficient EREW PRAM algorithms for parentheses-matching

We present four polylog-time parallel algorithms for matching parentheses on an exclusive-read and exclusive-write (EREW) parallel random-access machine (PRAM) model. These algorithms provide new insights into the parentheses-matching problem. The first algorithm has a time complexity of O(log² n) employing O(n/(log n)) processors for an input string containing n parentheses. Although this algorithm is not cost-optimal, it is extremely simple to implement. The remaining three algorithms, which are based on a different approach, achieve O(log n) time complexity in each case, and represent successive improvements. The second algorithm requires O(n) processors and working space, and it is comparable to the first algorithm in its ease of implementation. The third algorithm uses O(n/(log n)) processors and O(n log n) space. Thus, it is cost-optimal, but uses extra space compared to the standard stack-based sequential algorithm. The last algorithm reduces the space complexity to O(n) while maintaining the same processor and time complexities. Compared to other existing time-optimal algorithms for the parentheses-matching problem that either employ extensive pipelining or use linked lists and comparable data structures, and employ sorting or a linked list ranking algorithm as subroutines, the last two algorithms have two distinct advantages. First, these algorithms employ arrays as their basic data structures, and second, they do not use any pipelining, sorting, or linked list ranking algorithms     

变换存储结构的一种高效排序算法

给出变换存储结构的一种高效排序算法 ,该算法的时间复杂度为 O(n) ,且与待排序数据的分布无关 .给出了该排序算法的描述 ,并在时间复杂度和空间复杂度两方面与其他排序算法作了比较     

单向链表快速排序算法

单向链表广泛应用于动态存储结构,当前单向链表的排序算法普遍效率偏低,而平均效率最高的快速排序算法并不适用于单向链表。基于分治策略,使用递归方法,通过重新链接单向链表节点,提出了用于单向链表的快速排序算法,其平均时间复杂度为O(nlog2n),辅助空间复杂度为O(0),平均递归栈空间复杂度为O(log2n);同时,进行了算法分析和实验测试,其效率较其它单向链表排序算法有较大提高,且较传统基于线性表的快速排序算法也有一定提高。研究结果解决了当前单向链表排序效率较低的问题。     

基于有限节点集的网络毁伤最大化问题研究

对网络实施攻击时,人们希望在有限的资源下获得最大的毁伤效果,而节点排序策略并不能实现毁伤最大.针对这种情况,定义攻击有限节点集的网络毁伤最大化问题,并给出问题的近似求解算法.由于近似求解算法计算复杂度较高,进一步提出基于重要节点的贪婪算法(greedy algorithm based on important nodes,GABIN).对无标度网络的实验表明:GABIN算法能够有效地减少计算时间,且效果接近于近似求解算法;当无标度网络的度指数$\gamma\geqslant2.5$时,GABIN算法的效果明显优于排序算法,所得节点集中超过30%的节点不同于排序算法.对Power网络的毁伤实验表明,GABIN算法适用于较大规模的实际网络,且效果显著优于度、介数、接近度、删除节点等排序算法.实验发现,利用GABIN算法获得的关键节点集包含大量的非中心性节点,这为网络攻击或网络防护提供了一个新的思路.     

线对象邻接关系快速重构算法

给定向量化坐标,计算n个线对象两两邻接关系,普通算法时间复杂度为O(n*n);理论最好时间复杂度为O(C),其中C是邻接关系的基数。基于散列桶,给出了建立线对象邻接关系的快速算法,其平均时间复杂度为O(n(1+1/r)),r为算法分配的桶数量与n的比,空间复杂度为O(n)。证明了若不允许使用额外空间,则不可能使用排序算法解决该问题;给出了允许使用额外空间条件下的两遍排序算法,时间复杂度为O(n(lbn+1+2/r))。应用表明快速算法比普通算法速度提高1~3个数量级。     

Reducing the run-time complexity of multiobjective EAs: The NSGA-II and other algorithms

The last decade has seen a surge of research activity on multiobjective optimization using evolutionary computation and a number of well performing algorithms have been published. The majority of these algorithms use fitness assignment based on Pareto-domination: Nondominated sorting, dominance counting, or identification of the nondominated solutions. The success of these algorithms indicates that this type of fitness is suitable for multiobjective problems, but so far the use of Pareto-based fitness has lead to program run times in O(GMN/sup 2/), where G is the number of generations, M is the number of objectives, and N is the population size. The N/sup 2/ factor should be reduced if possible, since it leads to long processing times for large population sizes. This paper presents a new and efficient algorithm for nondominated sorting, which can speed up the processing time of some multiobjective evolutionary algorithms (MOEAs) substantially. The new algorithm is incorporated into the nondominated sorting genetic algorithm II (NSGA-II) and reduces the overall run-time complexity of this algorithm to O(GN log/sup M-1/N), much faster than the O(GMN/sup 2/) complexity published by Deb et al. (2002). Experiments demonstrate that the improved version of the algorithm is indeed much faster than the previous one. The paper also points out that multiobjective EAs using fitness based on dominance counting and identification of nondominated solutions can be improved significantly in terms of running time by using efficient algorithms known from computer science instead of inefficient O(MN/sup 2/) algorithms.     

A new parallel and distributed shortest path algorithm forhierarchically clustered data networks

This paper presents new efficient shortest path algorithms to solve single origin shortest path problems (SOSP problems) and multiple origins shortest path problems (MOSP problems) for hierarchically clustered data networks. To solve an SOSP problem for a network with n nodes, the distributed version of our algorithm reaches the time complexity of O(log(n)), which is less than the time complexity of O(log ² (n)) achieved by the best existing algorithm. To solve an MOSP problem, our algorithm minimizes the needed computation resources, including computation processors and communication links for the computation of each shortest path so that we can achieve massive parallelization. The time complexity of our algorithm for an MOSP problem is O(m log(n)), which is much less than the time complexity of O(M log² (0)) of the best previous algorithm. Here, M is the number of the shortest paths to be computed and m is a positive number related to the network topology and the distribution of the nodes incurring communications, m is usually much smaller than M. Our experiment shows that m is almost a constant when the network size increases. Accordingly, our algorithm is significantly faster than the best previous algorithms to solve MOSP problems for large data networks