摘要
针对分段快速排序法因分段映射策略不理想而造成算法复杂度显著增加之问题,文章提出了一种由按位块分段、分段映射和局部快速排序所组成的新排序算法——按位块分段快速排序法(以下简称为“按位块分段快速排序”)。算法分析和实验结果都表明:在待排序数据均匀分布或正态分布的情况下,按位块分段快速排序法的时间复杂度可以达到O(N),而附加存储空间开销却仅仅为N+M(M为分段数目,1≤M≤N),同时排序速度明显优于QuickSort、分段快速排序、分“档”统计插入排序和ProportionSplitSort等算法。
In this paper, a new algorithm consisted of separating segment, mapping and quick sort according bit field is presented o The algorithm analysis and experimental results show that the new sorting algorithm has the time complexity of O（N）, requires no more than N＋M（here M is the number of segment , 1≤M≤N） extra space only, and is obviously quicker than that of Quick Sort, Proportion Spht Sort et al.
出处
《微电子学与计算机》
CSCD
北大核心
2006年第8期136-139,143,共5页
Microelectronics & Computer
基金
辽宁省自然科学基金项目(20032100)
计算机软件新技术国家重点实验室(南京大学)开放基金项目(A2004-05)
关键词
排序
位块
段
映射
快速排序
Sorting, Bit field, Segment, Mapping, Quick sort
