高级检索

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

    Grading-Locating Sorting and Its Development Towards Grading-Locating Searching

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

       

      Abstract: Based on the analysis of the deficiencies of "Wang Xiang yang’ twice grading sorting", an algorithm of equal probability grading function is proposed. Assuming any data of n in a distribution function is known, they only need to be calculated all in one time, and there would be m grades, realizing an order on the grades (in the grade it is still non orderly). Let m≥n , in each grade an expected data volume are made not to be bigger than 1. The grades going to be sorted now nearly become orderly. It needs only very few time consumption to fulfil sorting in the grade. Thus an orderly and an equal probability gradational searching table can be set up. On this basis an algorithm of grading locating searching is put forward It has the advantages as follows: ① For a certain number to be searched, there is no need to make a "comparison" on it, but only to "calculate" on it, directly ensuring a data "grade" in the table as a searching target; ② high efficient searches such as binary search in the scope of this "grade" could be used; ③ it is suitable for any datum, especially the searching table of prodigious data; and ④ it avoids searching in all the scope of this table, and at the same time, it avoids the phenomenon of "collision" as well.

       

    /

    返回文章
    返回