一种新的分“档”快速排序算法

本文提出了一种由分“档”、整体置换和局部快速排序所组成的新排序算法-分“档”快速排序法,算法分析和实验结果都表明,在待排序数据均匀分布或正态分布的情况下,分“档”快速排序算法的时间复杂度可以达到O（n),而附加存储空间开销却仅仅为[（n 1)/2],同时排序速度明显优于Quick Sort[2]、快速分组排序[5]、分“档”统计插入排序[1]和Proportion Split Sort[4]等算法。     

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

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

分“档”快速排序算法研究

文章在文献［１］的基础上,提出了一种由分“档”、整体置换和局部快速排序所组成的新排序算法——分“档”快速排序法。算法分析和实验结果都表明：在待排序数据均匀分布或正态分布的情况下,分“档”快速排序算法的时间复杂度可以达到Ｏ（ｎ）,而附加存储空间开销却仅仅为［（ｎ＋１）／２］,同时排序速度明显优于Ｑｕｉｃｋ Ｓｏｒｔ［２］、快速分组排序［５］、分“档”统计插入排序［１］和 Ｐｒｏｐｏｒｔｉｏｎ 　Ｓｐｌｉｔ Ｓｏｒｔ［４］等算法。     

二次分“档”链接排序算法分析

“一种新的二次分‘档’链接排序算法”一文首先以随机无符号整数为基础，证明在一定条件下，这种新的排序算法具有O（n)时间复杂度，然后在没有给出证明的情况下，将算法的适用范围推方到任意数据。对这种新的排序算法进行了深入研究，指出了原文中的几点错误，并就随机无符号整数序列和随机无符号实数序列两种情况，分别给出了二次分“档”过程的理论分析，证明这种新的排序算法不适用于随机无符号实数序列。     

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

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

精度归“档”插入排序算法研究

提出了一种在最大值和最小值之间的数据范围内，由待排序数据的落点百分比精确到第一位小数点后经转换所形成的固定“档”住的基础上，利用归“档”统计和直接插入排序所形成的新排序算法一精度归“档”插入排序算法。概算法在待排序数据非极不均匀的情况下，时间复杂度降为O(n)，具有重要的实际意义。     

一种新的二次分"档"链接排序算法

提出了一种谓之二次分“档”链接的新排序方法（以下简称为二次分“档”链接排序）,并给出了该排序算法的描述、时间复杂度分析、空间复杂度分析及用Ｃ语言编写程序进行算法比较的实验结果,算法分析和实验结果都表明：在待排序数据满足Ｏ（△Ｍ）≤Ｏ（Ｎ）（这里,Ｎ为待排序数据个数,△Ｍ为关键字的变化范围）的情况下,二次分“档”链接排序方法与待排序数据分布无关且时间复杂度仅为Ｏ（Ｎ）,而附加在存储空间开销仅为Ｎ＋√     

针对任意分布数据的高效分档混合排序算法

针对任意分布数据的排序问题,在把对文献[7][8][9]等分档排序算法的改进与该算法在程序语言中的实现技术的改进相结合的基础上,提出了一种新的针对任意分布数据的高效分“档”排序算法,并通过把它与最近排序方面的工作进行比较说明了它的优越性。     

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

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

改进的按位拆分快速排序算法

在讨论目前已有的快速排序算法的基础上,提出一种新的按位拆分快速排序算法,利用Java实现了算法的并行运算。算法分析和实验结果表明,它的算法时间复杂度可达到O(Kn),排序速度明显优于Quick Sort。     

分段快速排序法的改进

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

任意分布数据的二次分"档"链接排序算法研究

本文提出一种谓之二次发“档”链接的新排序方法,给出了该排序算法的描述、时间复杂度分析、空间复杂度分析及用Ｃ语言编写程序进行算法比较的实验结果。     

Qsort算法的理论与实现

Qsort（Quick Sort，快速排序）是已知效率最高的通用内部排序算法，也是实践中被使用得最多的算法之一。但其概念与产品级实现之间，有天渊之别（其他算法也基本如此）。从掌握Qsort算法的概念，到了解具体实现的细节，可以视为区别新手和熟练程序员的标志。     

一种自定义顺序的字符串排序算法

现有的排序算法很难实现自定义顺序的字符串排序,提出一种自定义顺序的字符串快速排序方法.在应用连续编号定义字符排序顺序的基础上,使用哈希表结构将字符串转换成对应的整型数组,以字符的最大编号作为基数排序算法的新基数,实现字符串的基数排序.分析和实验表明,本文方法可有效实现自定义顺序的字符串排序,是一个时间和空间复杂度都是线性的排序算法,比快速排序(Quick Sort)具有更好的时间性能,且可以方便地推广到其它语言的字串排序中.     

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

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

完备置换阵列的两种代数枚举方法

完备置换阵列(CPA)是定义在集合Zn={1,2,…,n}上的所有n!个排列,n个正整数的每一种排列称为一个置换.随着n的增加,n!个置换的完全排列是很困难的工作.本文提出两种n!个置换的枚举方法,不同于传统的比较回溯法和字典排序法,而是借助于完好定义的操作函数来执行从一个置换到另一个置换的状态转移,所形成的完备置换阵列具有天然的组合结构特征.第一种方法是将完备置换阵列按照格雷码的结构特征进行排序,通过有限状态机执行操作函数来达到枚举基于格雷码排序的n!个置换的目的.第二种方法是基于组合数学的方法,借助于循环移位拉丁方来形成n!个置换的排列.     

与精度归“档”插入排序算法研究的商榷

作为计算机应用中一项复杂而重要的技术，排序一直是计算机领域内人们感兴趣的课题，寻找速度快、附加存储空间开销小的高效排序算法也一直是计算机工作者为之追求的目标。对精度归“档”插入排序算法研究中所存在的几个问题进行商榷与讨论。     

Multisets排序的最优并行算法

排序是一个既有十分重要的理论意义又有广泛的实际应用价值的问题 ,其中 ,Multisets排序问题是指对只有k个不同关键字值的n个数据 (记录 )进行排序 ,0 相似文献   

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

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

Radix Sort——复杂度为O（n）的排序方法

在每一本讲算法的教科书中差不多都有讲排序的方法，从最初的选择排序、冒泡排序，到哈希排序、快速排序、堆排序，二叉树排序等等。一般的认为，通用排序中．最低的算法复杂度为O(n·LoG(n))，n是待排序的元素个数。那么有没有比这更快，算法复杂度更低的排序算法呢?在本文中，大家将会看到一种算法复杂度为0(n）的