一个多元选择算法

本文基于数排序的思想，从高位关键字开始，对ｍ位关键字的ｎ个记录进行扫描，给出了一个多元选择算法，算法的最坏复杂度为Ｏ（ｍ（ｎ＋ｒ）），但平均复杂度为Ｏ（ｎ＋ｒ）。     

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

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

N-Star网络中最优的点到多点平行路由算法

Ｃｈｅｎｔ等研究了ｎ－Ｓｔａｒ网络中的点到多点并行路由问题,对前人的工作做了很大的改进,给出了一个几乎最优的时间复杂度为Ｏ（ｎ＾２）的算法,由Ｃｈｅｎ的算法所给出的ｎ－１条路Ｐ２,…,Ｐｎ满足│Ｐｉ│≤ｄｉｓｔ（ｖ１,ｖｉ）＋６,其中Ｐｉ是连续ｖｉ到ｖ１的路,│Ｐｉ│表示路Ｐｉ的长度,ｄｉｓｔ（ｖ１,ｖｉ）表示ｖｉ到ｖ１的最短路的长度。     

二次堆排序算法和提高排序效率的途径

本文讨论了一种堆排序的改进算法，该算法的平均时间复杂度达到ｎｌｏｇ２ｎ＋Ｏ（ｎ）。在此基础上，提出了二次堆排序的算法，使该排序过程中优化数据处理，排序速度提高１８０％。同时，本文给出了提高效率的措施、排序算法和实验结果。最后，给出了快速排序的优化数据处理的途径，从而较大地提高了排序效率。     

多项式族左扇区稳定的最大摄动区间

已知多项式ｐ（ｓ，ｒ）＝ｘ∑ｉ＝０ａｉ（ｒ）ｓ＾ｉ。其中诸系数ａｉ（ｒ）（ｉ＝０，１，…，ｎ）为参量ｒ的多项式函数且ｐ（ｓ，０）是左扇区稳定的多项式，本文给出ｒ的最大摄动区间以使对这区间中的所有ｒ．多项式ｐ（ｓ，ｒ）都是左扇区稳定的，     

一般化超立方网络的容错寻径算法

本文研究一般化超立方网络（ＧＨＣ）的容错寻径算法。给定一个一般化超立方网络Ｇ（ｍ，ｒ）：Ｎ＝ｍ＾ｒ（ｍ≥２，ｒ≥１），Ｆ为其故障结点集合，且Ｇ（ｍ，ｒ）－Ｆ是连通的，Ｓ和Ｄ是Ｇ（ｍ，ｒ）中任意两个非故障结点，其汉明距离Ｈ（Ｓ，Ｄ）＝ｈ，则当故障结点的个数│Ｆ│〈ｄ，一定存在一条长度≤ｈ＋２的非故障路径Ｐ（Ｓ，Ｄ），而当ｄ≤│Ｆ│〈ｍ（ｄ－ｍ＋１）时，一定存在一条长度≤ｈ＋４ｍ－２的非故障路径Ｐ（Ｓ     

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

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

一种新的映射链接排序算法

本文通过对长记录数据特性的分析,提出了一种谓之映射链接的新排序方法（以下简称为“晌射链接排序”）,给出了该排序算法的描述、时间复杂度分析及用Ｃ语言编写程序进行算法比较的实验结果。算法分析和实验结果都表明：映射连接排序方法与待排序数据分布情况无关,其时间复杂度仅为Ｏ（Ｎ）;对于大规模长记录数据的排序,其速度远远优于快速排序、快速分组排序、Ｐｒｏｐｏｒｔｉｏｎ Ｓｐｌｉｔ Ｓｏｒｔ等算法。     

并行归并排序算法

构造效率为Ｏ（１）的并行算法是一个引人注目的问题。［１］和［２］分别提出了并行度为Ｏ（ｌｏｇｎ）和Ｏ（ｎ＾１／２）的、效率为Ｏ（１）的并行排序算法。本文提出一种新的并行排序算法，其效率为Ｏ（１），而并行步数小于［１］和［２］的算法的并行步数。经过改进后，在保持效率为Ｏ（１）的情况下，可进一步将并行度扩大到Ｏ（ｎ＾１／２ｌｏｇ ｎ）。     

最长公共子充列问题的改进快速算法

现在几个最常用的解决最长公共子序列（ＬＣＳ）问题的算法的时间复杂度分别是Ｏ（ｐｎ）,Ｏ（ｎ（ｍｐ））。这里Ｍ、ｎ为两个待比较字符串的长度,Ｐ是最长公共子串的长度。给出一种时间复杂度为Ｏ（ｐ（ｍｐ））,空间复杂度为Ｏ（ｍ＋ｎ）的算法。与以前的算法相比,不管在Ｐ〈〈ｍ的情况下,还是在Ｐ接近Ｍ时,这种算法都有更快的速度。     

完全欧几里德距离变换的最优算法

欧几里德距离变换（ＥＤＴ）对由黑白素构成的二值图象中所有象素找出其到最近黑素的距离，应用于图象分析，计算机视觉，在本文之前，该问题的最好复杂度为Ｏ（ｎ＾２ｌｏｇｎ）。本文提出了一个复杂度为Ｏ（ｎ＾２）的算法，使复杂度达到最优，该算法可以并行化，在有ｒ个处理单元的ＥＲＥＷＰＲＡＭ计算模型上，若ｒｌｏｇｒ≤２２／６ｎ，则时间复杂度为Ｏ（ｎ／ｒ）否则为Ｏ（ｎｌｏｇｒ）。     

一类有效的一般并行分枝界限算法

本文针对使用ｐ个处理器选出ｐ个子问题进行并行扩展的一类并行分枝界限算法,提出了一个称作双层立体堆的数据结构,给出了ＰＲＡＭ－ＣＲＥＷ模型上的并行分枝界限算法。假定在状态空间树上扩展一个结点最多生成ｒ个子结点,本文提出的并行算法最多使用ｒ个处理器,其运行时间为Ｏ（（ｒ／ｌｏｇｒ）ｈｌｏｇｈ＋ｒｈ）。对于ｌｏｇｈ〈ｒ〈ｈ,在系数因子ｌｏｇｈ／ｌｏｇｒ的范围内,以及对于ｌｏｇｈ〉ｒ,在系数因子ｒ／ｌｏｇ     

超立方网络上的平行路径

超立方是分布存储系中最常用的结构。在以往的工作中,人们已经提出了不少容错寻径算法,然而,还没有考虑Ｈｎ中│Ｆ│≥２ｎ－２的情形,在一个含有故障结点集Ｆ的ｎ维超立方网络Ｈｎ中,│Ｆ│≤４ｎ－２４,（ｓ０,ｄ０）,（ｓ１,ｄ１）是其中任意两对非故障结点,结果,（１）对↓Ａｖ∈Ｖ（Ｈｎ）,有│Ａ（ｖ,Ｈｎ－Ｆ）│≥６．（２）沿着某一维ｋ（０≤ｋ≤ｎ－１）,可将Ｈｎ分割成两部分：（ｄ０∈）Ｈｎ－１,０和（     

4个多色Ramsey数的下界

研究了素数阶完全图Ｋｐ的边的ｎ－染色，给出了计算它的子图Ｇｐ（Ｓｉ）的团数的一种算法，得到１个三色，３个四色Ｒａｍｓｅｙ数的新的下界     

组合的二进制表示及其算法

本文讨论了一种用二进制字符串表示组合的方法，基于该方法，给出了按字典顺序生成所有组合的枚举递归算法。为了建立组合集与Ｉ集之间的一一映射关系，描述了相应的排序算法与逆排序算法。事实上，我们的这些算法与Ｋｎｏｔｔ算法相比具有明显的优越性。     

一种函数映射排序方法

本文给出一种函数映射排序法。该方法采用直接计算定位的方式提高排序速度。算法分析和实验结果表明：在被排数据均匀分布的情况下，该方法的时间复杂度为Ｏ（Ｎ），附加存储空间为Ｎ。且该方法在速度上明显快于Ｈｏａｒｅ快速排序法。     

最小生成树的高效异步并行算法

在ＭＩＭＤ－ＳＭ并行计算模型上，本文给出了时间复杂性为Ｏ（ｎ（ｎ／ｐ＋ｌｏｇｐ））的最小生成树的异步并行算法，其中ｎ，ｐ（１≤ｐ≤ｎ）分别表示图的顶点数和处理机的个数。     

映射式K路合并排序算法

本文介绍了映射式排序算法，这种算法附加一定的存储开销，时间复杂性为Ｏ（Ｎ）。在此基础上，本文还提出了一个新的Ｋ路合并算法，关键字与数相下标作映射和链接处理，不实施反复比较和交换关键字的操作，时间复杂性达到Ｏ（Ｎ），适宜一类特殊问题的大规模信息处理。     

最优堆排序算法

本文讨论了堆的若干性质,提出对堆排序算法的改进,改进后的堆排序算法是一个最优排序算法,在最坏情况下需要ｎｌｏｇｎ＋ｎａ３（ｎ）＋Ｏ（ｎ）次元素比较和ｎｌｏｎ＋Ｏ（ｎ）次元素移动。     

关于迷宫排序问题的研究

本文首先把迷宫排序问题推广为ｍ×ｎ迷宫（ｍ＞１，ｎ＞１）的排序问题，证明了ｍ×ｎ迷宫的任一初始状态能经过有限步移动转变成目标状态的充要条件，然后给出了一个ｍ×ｎ迷宫排序的算法，该算法的时间复杂度是Ｏ（ｍｎ（ｍ＋ｎ）），空间复杂度是Ｏ（ｍｎ）．最后还指出了它的时间复杂度的一个下界．这样，关于迷宫排序问题就基本上得到了圆满地解决．