一种新的插入排序和分档检索法

作     者：杨大顺 陶明华 

作者机构：江苏镇江师范专科学校 

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：1990年第13卷第11期

页      面：853-859页

核心收录：

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：江苏省教委自然科学基金 

主　　题：插入排序 分档检索 

摘      要：本文首先提出一种谓之代码转换、分档统计转移插入的新排序方法(以下简称分档插入排序法)。给出排序算法、流程图和用BASIC及PASCAL语言编写程序进行实验的结果,算法分析和实验结果都表明在被排数据均匀分布的情况下,该排序方法的时间复杂性为O(N),附加存贮开销为2N+2(N为数据量),并且该排序方法在速度上明显快于QUICK SORT法。接着又提出一种以分档插入排序法为基础的分档检索法。给出检索算法和流程图。对该算法进行分析的结果表明:在被检索数据均匀分布的情况下,分档检索法的平均检索长度不超过1.39(1+(1/N)),附加存贮开销为N+1。