分档定位排序以及向分档定位查找的发展

作     者：陈启星 罗启宇 

作者机构：长沙职工大学长沙410008 中国电子国际贸易公司北京100036 

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2003年第40卷第5期

页      面：706-711页

核心收录：

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

主　　题：等概分档 分档映射 分档排序 定位排序 分档查找 

摘      要：分析了“王向阳二次分档排序的不足 给出了等概分档映射算法 ,对已知分布函数的n个任意数据 ,仅需遍历计算一次 ,就可以分为m档 ,实现档之间有序化 (档内仍无序 ) 令m≥n ,可以使得每档数据量期望值不大于 1,待排序序列已经接近有序化了 ,只需用很少的时耗即可完成档内排序 ,从而建立一个有序且等概分档的查找表 在此基础上 ,提出了分档定位查找算法 ,其优势是 :①对于待查找的某个数 ,不需要进行“比较 ,而只要进行“计算 ,就可以直接在该查找表中确定一个数据“档作为查找目标 ;②可以在该“档范围内使用折半查找等高效查找 ;③适用于任意数据且数据量很大的查找表 ;④在避免了全程查找的同时也避免了“冲突