数据结构与算法（4）

1、排序（明天做一个让大家一看就能搞定八大排序的图）

直接选择排序、希尔排序、快速排序和堆排序是不稳定排序，其他排序为稳定排序

2、哈夫曼树：一类带权路径长度最短的树。树的带权路径长度为树中所有叶子节点的带权路径长度之和WPL。

3、查找：

（1）顺序查找：平均查找长度为(n +1 )/2次，时间复杂度为O(n)

（2）二分法查找：线性表节点必须按关键码值排序，且线性表是以顺序存储方式存储的。查找成功比较次数log2n，查找失败比较次数log2n+1

（3）分块查找：先是块间查找，然后块内查找。

（4）散列表（哈希表Hash）的存储和查找：处理冲突的方法：开地址法（线性探测法）、拉链法等

负载因子(装填因子)=表实际存储的结点个数/表的最大能存储结点个数（即表长）

二叉排序树：每个结点左子树的所有关键码值都小于该结点关键码值，右子树所有结点关键码值都大于该结点关键码值。对称周游二叉排序树，得到一个有序序列，时间复杂度O（log2n）

B树和B+树：M阶树，每个结点至多有M-1个关键码，至少有M/2(取上界)-1个关键码。B树适合随机查找，不适合顺序查找。B+树适合顺序查找。