4路插入排序法

提出一种4路插入的排序方法。给出了算法思想、算法描述、算法分析和实验结果。其理论意义是改进了一类时间复杂度为O（N^2）排序法的时间复杂度，其实用价值是该排序法存一类时间复杂度为O（N^2）排序法中排序效率较高的，其平均排序速度比直接插入排序法、选择排序法、冒泡排序快66％以上。     

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

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

双向插入排序法

本文提出一种双向插入的排序方法。给出了算法思想、算法描述、算法分析和实验结果。其理论意义是改进了插入排序法的时间复杂度，其实用价值是该排序法比直接插入排序法具有较高的排序效率。     

深度优先稳定原地归并排序的高效算法

基于分治策略,使用深度优先的方法,提出了一种用于线性表的稳定原地归并排序算法,其时间复杂度为O(n lb n),辅助空间复杂度为O(1),递归栈空间复杂度为O(lb n),同时进行了算法分析和实验测试。实验结果表明,该算法效率较STL中的稳定原地归并排序算法有67.51%的提升,解决了稳定排序算法中要么时间复杂度高要么空间复杂度高的问题。     

基于数组的桶排序算法

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

分段快速排序法的改进

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

通过改变开关状态实现多源点多播

在并行和分布式环境中 ,多个结点之间的通讯一直是研究工作的焦点问题 ,这些通讯主要包括置换、多播(Multicast)及多源点多播 (Multiple Multicast) .L ai提出了适用于一类与带缓存的 Cube网相互拓扑等价的网络的置换算法 ,硬件代价为 O(N log N ) ,算法的时间复杂度为 O(N ) .Feng提出的 inside- out算法实现了 Omega- 1 × Omega网上的置换 ,总的路由时间复杂度为 O(N log N) ,硬件代价为 O(N log N) .支持严格无阻塞置换的三级 Clos网的总的交叉点数为O(N32 ) .支持严格无阻塞的多播的三级 Clos网为 O(N32 logrloglogr) .Yang提出了一种新的多播网络 ,硬件复杂度为 O(N log2 N ) .为了支持多源点多播 ,多级互联网硬件代价往往大幅上升 .本文借鉴了 L ai提出的规则改变开关状态的方法 ,并把这种算法推广到了多源点多播的情况 .提出了一种新的多源点多播路由算法 ,此算法也同样适用于这一类相互拓扑等价的多级互联网 ,包括 Baseline、Om ega、Cube等 .在此算法中 ,每个数据流被划分为固定大小的数据包 ,在网络中独立传送 ,网络中的每个开关的状态按照固定的状态每个时步规则变化 ,每个数据包两次经过网络后到达目标结点 .此类的网络的硬件代价为 O(Nlog N ) ,此多源点多播路由算法的时间复杂度为 O(N )     

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

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

基因组Translocation排序问题的改进多项式算法

该文给出基因组Transhocation排序问题的一个改进多项式算法，原算法所有存储空间O（n)，时间复杂度为O(n^3)，文中改进算法仍采用O(n)存储空间，时间复杂度为O(n^2logn),具体地，将计算Translocation距离的时间复杂度由O(n^3)改进为O(n^2),将计算Translocation序列的时间复杂度由O(n^3)改进为O(n^2logn).     

二次分档插入排序法

代码转换分档插入排序法,对于均匀分布的数据无疑是一种高效率的排序方法,其时间复杂性为O(N),但是,对于极不均匀分布的数据,该方法的效率将明显下降,其时间复杂性变为O(N~2),为了避免在上述情况下排序效率的明显下降,使分档插入排序法有更普遍的适用性,我们在本文中将要提出二次分档插入排序法。     

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

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

按位段计数排序法

本文提出一种按位段计数的排序方法。讨论了该排序法几个关键问题的解决方法，给出了算法思想、算法描述、算法分析和实验结果。其理论意义是该排序法的时间复杂度达到0(N)，其实用价值是该排序法具有较高的排序效率以及与数据类型、分布、范围无关。     

Generalized algorithm for parallel sorting on product networks

We generalize the well-known odd-even merge sorting algorithm, originally due to Batcher (1968), and show how this generalized algorithm can be applied to sorting on product networks. If G is an arbitrary factor graph with N nodes, its r-dimensional product contains N^r nodes. Our algorithm sorts N^r keys stored in the r-dimensional product of G in O(r^rF(N)) time, where F(N) depends on G. We show that, for any factor graph G, F(N) is, at most, O(N), establishing an upper bound of O(r² N) for the time complexity of sorting N^r keys on any product network. For product networks with bounded r(e.g. for grids), this leads to the asymptotic complexity of O(N) to sort N^r keys, which is optimal for several instances of product networks. There are factor graphs for which F(N)=O(log² N), which leads to the asymptotic running time of O(log² N) to sort N^r keys. For networks with bounded N (e.g. in the hypercube N=2, fixed), the asymptotic complexity becomes O(r²). We show how to apply the algorithm to several cases of well-known product networks, as well as others introduced recently. We compare the performance of our algorithm to well-known algorithms developed specifically for these networks, as well as others. The result of these comparisons led us to conjecture that the proposed algorithm is probably the best deterministic algorithm that can be found in terms of the low asymptotic complexity with a small constant     

How to sort N items using a sorting network of fixed I/O size

Sorting networks of fixed I/O size p have been used, thus far, for sorting a set of p elements. Somewhat surprisingly, the important problem of using such a sorting network for sorting arbitrarily large datasets has not been addressed in the literature. Our main contribution is to propose a simple sorting architecture whose main feature is the pipelined use of a sorting network of fixed I/O size p to sort an arbitrarily large data set of N elements. A noteworthy feature of our design is that no extra data memory space is required, other than what is used for storing the input. As it turns out, our architecture is feasible for VLSI implementation and its time performance is virtually independent of the cost and depth of the underlying sorting network. Specifically, we show that by using our design N elements can be sorted in Θ(N/p log N/p) time without memory access conflicts. Finally, we show how to use an AT²-optimal sorting network of fixed I/O size p to construct a similar architecture that sorts N elements in Θ(N/p log N/p log p) time     

快速插入排序法

设法用减少插入序列长度的办法，提出一种快速插入的排序方法。给出了算法思想、算法描述、算法分析和实验结果。其理论意义是改进了插入排序法的时间复杂度，其实用价值是该排序法的排序效率比直接插入排序法提高43％左右。     

均匀分布数据的分"档"统计插入排序算法研究

１．引言 排序（ｓｏｒｔｉｎｇ）是计算机程序设计中的一种重要运算,它的功能是将一个数据元素（或记录）的任意序列,重新排列成一个接关键字有序的序列．其精确定义如下： 设｛Ａｉ｝＝（Ａ１,Ａ２,…,ＡＮ）为一有限的数据集合,其中人是集合中的元素,又叫做记录．若 Ａｉ的某个标识特征为 Ｋｉ,称凡为 Ａｉ的关键字,又称为健或标识符．｛Ａｉ｝也称为记录集合．所谓排序,就是依照集合中元素的关键宇特征,把元素排列顺序重新加以组织,使新的有序集合｛Ａｊ｝对于任意的,有或． 由于排序是计算机科学中一项复杂而重要的技术,…     

一种新的分"档"统计插入排序算法

提出了一种谓之数据代码转换,分“档”统计,迁移插入的新排序方法,给出了该排序算法的描述,时间复杂度分析用Ｃ语言编写程序进行算法比较的实验结果,算法分析和实验结果都表明：在待排序数据均匀分布的情况下,分“档”统计插入排序方法的时间复杂度为Ｏ（Ｎ）,并且排序速度明显优于快速排序,分段快速排序,按位段分块排序等算法。