热线电话:13121318867

登录
2019-03-17 阅读量: 770
如何使用哈希表进行排序?

在这种排序算法中,Hash函数fOrder Preserving Function的属性一起使用,该属性表明if

 x <= y,f(x)<= f(y)

哈希函数:

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.0000
1
关注作者
收藏
评论(0)

发表评论

暂无数据
推荐帖子