一种新的分“档”置换插入排序算法

作者：杨红颖; 王向阳

来源：小型微型计算机系统, 2006, (06): 996-1001.

• 排序
• 档
• 置换
• 直接插入排序 sorting
• classification
• permutation
• straight insertion

近年来,人们提出了众多时间复杂度为O(n)的排序算法.但分析研究结果表明,上述排序方法都不同程度上存在着以下两点不足:(1)附加存储空间开销大;(2)排序效率过分依赖于关键字的均匀分布.基于此,本文提出了一种由分“档”、整体置换和局部直接插入排序所组成的新排序算法——分“档”置换插入排序法.算法分析和实验结果都表明:该排序方法与待排序数据分布无关,其时间复杂度为O(n),而附加存储空间开销少于0.5n,同时排序速度明显优于QuickSort、HeapSort、按字节桶分配链接排序、ProportionSplitSort等算法.

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