| 分段快速排序法的改进 |
| |
| 引用本文： | 王向阳,杨红颖. 分段快速排序法的改进[J]. 小型微型计算机系统, 2001, 22(11): 1382-1385 |
| |
| 作者姓名： | 王向阳 杨红颖 |
| |
| 作者单位： | 辽宁师范大学计算机与信息技术学院, |
| |
| 基金项目： | 国家自然科学基金(项目编号69974032)资助 |
| |
| 摘 要： | 针对分段快速排序法^[1]因分段映射策略不理想而造成算法复杂度显著增加之问题，本文提出了一种由按位块分段、分段映射和局部快速排序所组成的新排序算法－按位块分段快速排序法（以下简称为“按位块分段快速排序”）。算法分析和实验结果都表明：在待排序数据均匀分布或正态分布的情况下，按位块分段快速排序法的时间复杂度可以达到O(N),是附加存储空间开销却仅仅为N＋M（M为分段数目，1≤M≤N），同时排序速度明显优于QuickSort^[2]、分段快速排序^[1]、分“档”统计插入排序^[5]和Proportion Split Sort^[7]等算法。
|
| 关 键 词： | 分段快速排序法 数组 计算机 算法 |
| 文章编号： | 1000-1220(2001)11-1382-04 |
FAST SORTING METHOD OF SEPARATING SEGMENT ACCORDING BIT FIELD |
| |
| WANG Xiang yang YANG Hong ying. FAST SORTING METHOD OF SEPARATING SEGMENT ACCORDING BIT FIELD[J]. Mini-micro Systems, 2001, 22(11): 1382-1385 |
| |
| Authors: | WANG Xiang yang YANG Hong ying |
| |
| Abstract: | |
| |
| Keywords: | Sorting Bit field Segment Mapping Quick sort |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
