摘要
文章在文献［１］的基础上，提出了一种由分“档”、整体置换和局部快速排序所组成的新排序算法——分“档”快速排序法。算法分析和实验结果都表明：在待排序数据均匀分布或正态分布的情况下，分“档”快速排序算法的时间复杂度可以达到Ｏ（ｎ），而附加存储空间开销却仅仅为［（ｎ＋１）／２］，同时排序速度明显优于Ｑｕｉｃｋ Ｓｏｒｔ［２］、快速分组排序［５］、分“档”统计插入排序［１］和 Ｐｒｏｐｏｒｔｉｏｎ Ｓｐｌｉｔ Ｓｏｒｔ［４］等算法。
In this paper,a new algorithm consisted of classification,in situ permutation and quick sort 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+l)2] extra space only,and is obviously quicker than that of Quick Sort,Proportion Split Sort et al.
出处
《计算机工程与应用》
CSCD
北大核心
2001年第13期110-112,共3页
Computer Engineering and Applications
基金
国家自然科学基金资助(编号:69974032)
