一种新的插入排序和分档检索法 |
| |
引用本文: | 杨大顺,陶明华.一种新的插入排序和分档检索法[J].计算机学报,1990,13(11):853-859. |
| |
作者姓名: | 杨大顺 陶明华 |
| |
作者单位: | 江苏镇江师范专科学校
(杨大顺),江苏镇江师范专科学校(陶明华) |
| |
基金项目: | 江苏省教委自然科学基金 |
| |
摘 要: | 本文首先提出一种谓之代码转换、分档统计转移插入的新排序方法(以下简称分档插入排序法)。给出排序算法、流程图和用BASIC及PASCAL语言编写程序进行实验的结果,算法分析和实验结果都表明在被排数据均匀分布的情况下,该排序方法的时间复杂性为O(N),附加存贮开销为2N+2(N为数据量),并且该排序方法在速度上明显快于QUICK SORT法。接着又提出一种以分档插入排序法为基础的分档检索法。给出检索算法和流程图。对该算法进行分析的结果表明:在被检索数据均匀分布的情况下,分档检索法的平均检索长度不超过1.39(1+(1/N)),附加存贮开销为N+1。
|
关 键 词: | 插入排序 分档检索 |
本文献已被 CNKI 维普 等数据库收录! |
|