分段快速排序法的改进

• 作者: 杨红颖 王向阳
• 来源期刊: 小型微型计算机系统
• 学科: 工学
• 关键词: 排序 位块 段 映射 快速排序
• 年，卷（期）: 2001,（11）
• 页码范围: 1382-1385
• 页数: 4页
• 分类号: TP302
• 字数: 4817字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-1220.2001.11.029

摘要

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

作者信息

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