摘要
提出了一种由分“档”、整体置换和局部直接插入排序所组成的新排序算法———分“档”直接插入排序法。算法分析和实验结果都表明 :在待排序数据非极不均匀分布的情况下 ,分“档”直接插入排序算法的时间复杂度可达到O(n) ,而附加存储空间开销却仅仅 [(n +1) /2 ],同时排序速率明显优于QuickSort、HeapSort按字节桶分配链接排序、ProportionSplitSort等算法。
In this paper,a new sorting algorithm consisted of classification,in situ permutation and straight insertion is presented.The algorithm analysis and experimental resutls show that the new sorting algorithm has the time complexity of O(n),requires no more than [(n+1)/2] extra space only,and is obviously quicker than that of Quick Sort,Heap Sort,Proportion Split Sort etc.
出处
《航空计算技术》
2000年第3期1-4,14,共5页
Aeronautical Computing Technique
基金
国家自然科学基金!(699740 32 )资助
