摘要
提出一种由分"档"、整体置换和局部直接插入排序所组成的新排序算法分"档"直接插入排序法.算法分析和实验结果表明:在待排序数据非极不均匀分布的情况下,分"档"直接插入排序算法的时间复杂度可以达到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 results 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.
出处
《沈阳化工学院学报》
CAS
2004年第1期62-66,共5页
Journal of Shenyang Institute of Chemical Technolgy
关键词
排序
档
置换
直接插入排序
sorting
class
permutation
straight insertion
