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

New Sorting Algorithm for Classification and Straight Insertion

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

some sorting methods that the expected time complexity is of O（n） were discussed in the related papers in the past few years. But, the analysis of algorithm shows that there are two drawbacks in these algorithms, （1） require a large amount of extra space and （2） the property of the expected time complexity is limited to uniformly distributed inputs. So, a new sorting algorithm consisted of classification, in situ permutation and straight insertion is presented in this paper. The algorithm analysis and experimental results show that the new sorting algorithm has nothing to do with data distribution, has the time complexity of O（a）, requires no more than 0. 5a extra space only, and is obviously quicker than that of Quick Sort, Heap Sort, Proportion Split Sort etc.