查找分为 静态查找表 和 动态查找表。
1、静态查找表
顺序查找 成功的平均查找长度为 (n+1)/2,也就是说查找的平均次数约为表长的一半,优点就是算法简单适应面广,对查找的表结构没什么要求,缺点就是查找长度太长效率低下。
折半查找 效率要比顺序查找高很多,但必须要求表的数据按顺序存储才能使用,因此删除和插入需要移动大量数据。所以折半查找适合表不易表动又经常查的情况。
分块查找 介于顺序查找和折半查找之间,又称为索引顺序查找,是对顺序查找的一种改进。
2、动态查找表
二叉排序树 又叫 二叉查找树:
1)左子树非空的话,所有值小于根节点。
2)右子树非空的话,所有值大于根节点。
3)左右子树本身就是二叉排序数。
二叉排序树查找过程,给定一个值,与根节点比较,相等则返回,小于则左子树查找,大于则右子树查找。
二叉排序树的插入节点过程,若是空二叉树,则新节点是根节点,若不是,则与根节点比较,小于则放在左子树,大于放在右子树。
二叉排序树删除过程较为复杂,分为三种情况,因为删除一个节点,不能把这个根节点上的树全部删除,且删完后,整个树还要保证有序性。
平衡二叉树(AVL树)
他左右子树都是平衡二叉树,且左子树右子树深度不会差超过1。只要有树上节点的平衡因子的绝对值大于1,则绝对不是平衡二叉树。
B-树
b-树的定义:一颗m阶的b-树,或为空树,或者满足:
1)树中每个节点最多m棵子树。
2)若根节点不是叶子节点,则至少两棵子树。
3)所有叶子节点都出现在同一层次上,并且不带信息。
...
3、哈希表
哈希表定义:根据设定的哈希函数和处理冲突的方法,将一组关键字映射到一个有限连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置。
哈希函数如何构造:常用哈希函数构造方法有 直接定址法、数字分析法、平方取中法、折叠法、随机数法和除留余数法等。
处理冲突方法:常见处理冲突的方法有 开放地址法、链地址法、再哈希法、建立一个公共溢出区。
内部排序:指待排序记录全部存放在内存中的排序过程。
外部排序:指待排序记录的数量很大,以至于内存不能容纳全部记录,再排序过程中尚需对外存进行访问的过程。
简单排序 有直接插入排序,冒泡排序,简单选择排序。
1、希尔排序
希尔排序又叫缩小增量排序,是对直接插入排序方法的改进。先分组,在把分组合并在一起排序。
2、快速排序
快速排序基本思想:通过一趟排序将待排序的记录分割成独立的两个部分,其中一部分记录的关键字均比另一部分小,然后在对这两部分记录进行排序。
若初始关键字有序或者基本有序时候,则会退化成冒泡排序。复杂度为O(n的二次方)
3、归并排序
指两个或者两个以上的有序文件合并成一个新的有序文件。
归并排序是把一个有n个记录的无序文件看成由n个长度为1的有序文件组成的文件,然后两个归并,如此重复,最后形成一个包含n个记录的有序文件为止。