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

• 作者: 杨红颖 王向阳
• 来源期刊: 微电子学与计算机
• 关键词: 排序 位块 段 映射 快速排序
• 年，卷（期）: 2006,（8）
• 页码范围: 136-139,143
• 页数: 5页
• 分类号: TP302
• 语种: 中文
• DOI: 10.3969/j.issn.1000-7180.2006.08.041

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨红颖	辽宁师范大学计算机与信息技术学院	94	1241	22.0	29.0