2019-03-17
阅读量:
770
如何使用哈希表进行排序?
在这种排序算法中,Hash函数f与Order Preserving Function的属性一起使用,该属性表明if
哈希函数:
f(x) = floor( (x/maximum) * SIZE )
where maximum => maximum value in the array,
SIZE => size of the address table (10 in our case),
floor => floor function
该算法使用地址表来存储值,这些值只是链接列表的列表(或数组)。Hash函数应用于数组中的每个值,以在地址表中查找其对应的地址。然后,通过将值与已经存在于该地址的值进行比较,以排序的方式将值插入其对应的地址。
例子:
Input : arr = [29, 23, 14, 5, 15, 10, 3, 18, 1]
Output:
After inserting all the values in the address table, the address table looks like this:
ADDRESS 0: 1 --> 3
ADDRESS 1: 5
ADDRESS 2:
ADDRESS 3: 10
ADDRESS 4: 14 --> 15
ADDRESS 5: 18
ADDRESS 6:
ADDRESS 7: 23
ADDRESS 8:
ADDRESS 9: 29






评论(0)


暂无数据
推荐帖子
0条评论
0条评论
0条评论