分“档”直接插入排序算法研究  

An New Sorting Algorithm for Classification and Straight Insertion

作　　者：冯春杨[1] 闫萍[2] 崔洪玲[1] 

机构地区：[1]辽宁大学高职学院,辽宁沈阳110036 [2]沈阳化工学院,辽宁沈阳110142

出　　处：《沈阳化工学院学报》2004年第1期62-66,共5页Journal of Shenyang Institute of Chemical Technolgy

摘　　要：　提出一种由分"档"、整体置换和局部直接插入排序所组成的新排序算法分"档"直接插入排序法.算法分析和实验结果表明:在待排序数据非极不均匀分布的情况下,分"档"直接插入排序算法的时间复杂度可以达到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.

关 键 词：排序 档 置换 直接插入排序 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]