最后一期更新，考试之前应该不会再出该专题了，之后有时间会出一些有关链表的代码题，其他章节只挑选重点的总结~
一.查找
1.顺序查找
又被称为线性查找，对顺序表和链表都使用~基本思想是从某一端开始，逐个检查关键字是否满足给定的条件~
2.折半查找
适用于有序的顺序表：首先将给定值key与表中中间位置的元素比较，若相等，则查找成功，返回该元素的存储位置，若不等，则所需查找的元素只能在中间元素以外的前半不分或者后半部分，然后在缩小的范围内继续进行同样的查找，如此重复直到找到为止
3.分块查找
分块查找又称为索引顺序查找，将查找表分为若干个小的子块，块内元素可以无序，但块之间是有序的~即将查找的过程分为两步：第一步是在索引表猴子那个确定待查记录所在的块，第二步则是在快内顺序查找~
4.二叉排序树（BST）
又被称为二叉查找树，若左子树非空，则左子树上所有的结点的值均小于根节点的值，而右子树则均大于，这样在查找节点时可以达到类似分块查找的效果~
5.平衡二叉树
AVL树，为了防止树的高度增长过快而降低二叉排序树的性能，规定在插入和删除二叉树结点时，要保证任意结点的左右子树高度差的绝对值不超过1，将这样的二叉排序树称为平衡二叉树，简称平衡树~
6.散列表
- 散列函数：将查找表中的关键字映射成该关键字对应位置地址的函数
- 散列冲突：将2个或更多的关键字映射再同一地址
- 哈希函数的种类：直接定址、除留取余、数字分析、平方取中
- 处理冲突的方法：开放定址、拉链法（链接到同一个位置上的链表）
- 要会计算平均查找长度ASL~
二.排序
1.插入排序
- 直接插入：将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。
- 折半插入：先折半查找出元素待插入的位置，再统一地一定待插入位置之后的所有元素
- 希尔排序：把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
2.交换排序
- 冒泡排序：它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
- 快速排序：快速排序采用的是分治思想，即在一个无序的序列中选取一个任意的基准元素pivot，利用pivot将待排序的序列分成两部分，前面部分元素均小于或等于基准元素，后面部分均大于或等于基准元素，然后采用递归的方法分别对前后两部分重复上述操作，直到将无序序列排列成有序序列。
3.选择排序
- 简单选择：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
- 堆排序：利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
4.归并排序
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
5.基数排序
它是通过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
6.外部排序
- 多路归并排序：多路归并是外部排序(External Sort)的基础，实现也比较简单，和最简单的归并排序中的二路归并是基本一样的，只不过路数是浮动的k（不是重点~）