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

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

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

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

任意类型的分类数据的快速排序

快速排序在数据部分相等或有序时,时间复杂度最坏为O（n2）。针对于任意类型的分类数据的排序,文章在快速排序的基础上,提出一种新的排序算法,具有快速排序算法的简洁性,但是不使用递归算法,时间复杂度为O（n）,空间复杂度为O（1）。通过理论分析和实验表明,该算法的性能明显优于其它排序算法,特别适合于数据量大的场合。     

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

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

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

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

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

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

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

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

一种三路划分快速排序的改进算法

快速排序是一种经典的排序算法,它的平均性能非常突出。针对快速排序在某些特殊情况下(如数据已有序或重复数据较多时)效率较低的问题进行了研究,对三路快速排序进行改进,使快速排序在特殊情况下也能保持较好的效率。通过大量的数据测试发现,该算法在最好情况下其性能在几个数量级上优于普通快速排序,在最坏情况下,其性能较普通快速排序无明显差距。改进后的三路快速排序是一种通用高效的排序算法,因此在某些情况下选用、该算法会获得更好的效率。     

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

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

基于浮点数机内编码的快速排序方法

本文提出一种可对任意分布的浮点数进行排序的快速排序方法,它基于浮点数的机内编码,具有速度快、实现简单、实用的特点。其时间复杂度为O(n),在对不同分布的随机浮点数进行的排序实验中,其速度是快速排序的数倍。同时,本算法思想还可用于双精度数、整数、字符串等类型数据的排序。     

一种新的基于哈希函数的排序算法

提出一种哈希函数分档的排序算法。根据数组下标递增的特点,针对任意分布整数,建立有效的哈希函数,通过反复映射完成排序。分析算法的时间和空间复杂度,实验验证算法的运行效率。算法分析和实验结果表明：算法的时间和空间复杂度均为O（n）,在问题规模较大时,效率优势明显。     

An Improved HEAPSORT Algorithm with n log n - 0.788928n Comparisons in the Worst Case

A new variant of HEAPSORT is presented in this paper. The algorithm is not an internal sorting algorithm in the strong sense, since extra storage for n integers is necessary. The basic idea of the new algorithm is similar to the classical sorting algorithm HEAPSORT, but the algorithm rebuilds the heap in another way. The basic idea of the new algorithm is it uses only one comparison at each node. The new algorithm shift walks down a path in the heap until a leaf is reached. The request of placing the element in the root immediately to its destination is relaxed. The new algorithm requires about n log n - 0.788928n comparisons in the worst case and n log n - n comparisons on the average which is only about 0.4n more than necessary. It beats on average even the clever variants of QUICKSORT, if n is not very small. The difference between the worst case and the best case indicates that there is still room for improvement of the new algorithm by constructing heap more carefully.     

基于Quick Sorting的快速分页排序算法

提出了分页排序的概念和基于Quick Sorting的快速分页排序算法(Quick Page Sorting)以及基于Hinl缓存机制的算法实现技术。实验表明,在数万至数百万数据总量情况下,Quick Pagc Soring的速度比Quick Sorting快10倍左右,大大提高了应用系统的响应速度。     

基于ART2的网络入侵检测算法

基于ART2的网络入侵检测算法是在自适应共振理论的基础上改进而来的。该算法对接收到的网络数据以及系统状态数据进行分析判断,实现入侵方式的自动分类,并且能够对新产生的入侵方式进行分类与记忆,实现了入侵检测系统的自适应性。该算法应用到入侵检测系统中能够解决入侵检测系统中可能出现的预分类不完全的问题,这对于检测新出现的入侵类型无疑具有很大的使用价值。     

Fast Four‐Way Parallel Radix Sorting on GPUs

Efficient sorting is a key requirement for many computer science algorithms. Acceleration of existing techniques as well as developing new sorting approaches is crucial for many real‐time graphics scenarios, database systems, and numerical simulations to name just a few. It is one of the most fundamental operations to organize and filter the ever growing massive amounts of data gathered on a daily basis. While optimal sorting models for serial execution on a single processor exist, efficient parallel sorting remains a challenge. In this paper, we present a hardware‐optimized parallel implementation of the radix sort algorithm that results in a significant speed up over existing sorting implementations. We outperform all known General Processing Unit (GPU) based sorting systems by about a factor of two and eliminate restrictions on the sorting key space. This makes our algorithm not only the fastest, but also the first general GPU sorting solution.     

Huffman算法的改进及其在图像压缩中的应用

本文改进了Huffman编码算法,主要是针对Huffman编码生成Huffman树构造中的排序方法的改进,提出一种基于"堆排序"的新方法。采用堆排序找到最小值实现Huffman编码,经过这种改进的Huffman编码方法对内存读写的次数大为减少,从而提高了响应速度。使得Huffman编码效率有所提高。通过对JPEG的Huffman压缩算法的分析以及采用4个JPG文件对改进的和传统的Huffman算法进行了仿真实验,对比分析表明改进算法的性能无论是压缩比率还是压缩时间方面都比经典的Huffman算法性能有所提高。     

维上带层次数据立方的自底向上计算

通过扩展 BUC算法 ,提出了 HBUC算法 ,自底向上地计算维上带层次的数据立方 .HBU C算法的关键在于对层次之间的映像关系进行了合理地编码 ,并选择了恰当的层次扫描路线 ,这些不仅能够保证 HBU C算法继承和扩展BUC算法的优化过程 :Write- Ancestors和 Collapsing,而且使粗粒度级的聚集计算因为共享细粒度级的排序结果而得到加速 ,从而大大提高了 HBUC的计算效率 .     

Evaluation of amplitude-based sorting algorithm to reduce lung tumor blurring in PET images using 4D NCAT phantom

PURPOSE: develop and validate a PET sorting algorithm based on the respiratory amplitude to correct for abnormal respiratory cycles. METHOD AND MATERIALS: using the 4D NCAT phantom model, 3D PET images were simulated in lung and other structures at different times within a respiratory cycle and noise was added. To validate the amplitude binning algorithm, NCAT phantom was used to simulate one case of five different respiratory periods and another case of five respiratory periods alone with five respiratory amplitudes. Comparison was performed for gated and un-gated images and for the new amplitude binning algorithm with the time binning algorithm by calculating the mean number of counts in the ROI (region of interest). RESULTS: an average of 8.87+/-5.10% improvement was reported for total 16 tumors with different tumor sizes and different T/B (tumor to background) ratios using the new sorting algorithm. As both the T/B ratio and tumor size decreases, image degradation due to respiration increases. The greater benefit for smaller diameter tumor and lower T/B ratio indicates a potential improvement in detecting more problematic tumors.