保研数据结构复习_装填因子

作者：酷酷是懒虫 | 2024-08-09 22:46:25

踩

装填因子

选择排序

基本思想：每一趟从待排序的元素中选出最小的元素，顺序放在已排好序的子表的最后，直到全部元素排序完成。

适用于从大量的元素中选择一部分排序元素，例如从10000个元素中选择出关键字大小为前10位的元素

堆排序（树形选择排序）

最大堆中父节点大于或等于两个子节点，最小堆父节点小于或等于两个子节点。

目标：使所有元素的哈希地址尽可能均匀地分布在m个连续内存单元上

1.直接定址法

2.除留余数法

最经常使用的一种哈希函数

3.数字分析法

装填因子：指哈希表中已存入的元素数n与哈希地址空间大小m的比值，即a=n/m。

装填因子越小，冲突的可能性就越小

开放定址法：

1.线性探测法

容易产生堆积问题。

2.平方探测法

可以避免出现堆积问题

缺点：

不一定能探测到哈希表上的所有单元，但最少能探测到一半单元。

拉链法：

所有哈希地址为i元素对应的结点构成一个单链表。在这种方法中，哈希表中每个单元中存放的不再是元素本身，而是相应同义词单链表的

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/酷酷是懒虫/article/detail/955497