一种新的按位块分段快速排序算法

作者：杨红颖; 王向阳

来源：微电子学与计算机, 2006, (08): 136-139+143.

DOI：10.19304/j.cnki.issn1000-7180.2006.08.040

• 排序
• 位块
• 段
• 映射
• 快速排序 Sorting
• Bit field
• Segment
• Mapping
• Quick sort

针对分段快速排序法因分段映射策略不理想而造成算法复杂度显著增加之问题,文章提出了一种由按位块分段、分段映射和局部快速排序所组成的新排序算法——按位块分段快速排序法(以下简称为“按位块分段快速排序”)。算法分析和实验结果都表明:在待排序数据均匀分布或正态分布的情况下,按位块分段快速排序法的时间复杂度可以达到O(N),而附加存储空间开销却仅仅为N+M(M为分段数目,1≤M≤N),同时排序速度明显优于QuickSort、分段快速排序、分“档”统计插入排序和ProportionSplitSort等算法。

• 单位
  南京大学; 沈阳师范大学; 辽宁沈阳; 计算机软件新技术国家重点实验室