查找
1.顺序查找
顺序查找即从表的一端开始，用逐一比较的办法顺序查找关键字
2.折半查找（二分查找）
1）先用待查记录的关键字key和正中元素相比，若相等，则查找成功，返回该位置；
2）若key比正中元素小，则缩小至左半部内查找；若key比正中元素大，则缩小至右半部内查找；
3）在新的范围内，再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。
注：单链表不能进行折半查找（因全部元素的定位只能从头指针head开始）
3.分块查找（索引顺序查找）
1）先根据关键字查索引表（顺序查找或折半查找），确定子表和子表的起始位置
2）然后在子表内顺序查找对应的记录（因为块内无序）
4.哈希表查找
1）线性探测法
2）二次探测法
Hi=(Hash(key)+di) mod m （i=1,2,……，k，k<=m/2）
其中：Hash(key)为哈希函数
m为哈希表长度，m要求是某个4k+3的质数；
di为增量序列 1^2，-1^2，2^2，-2^2，…，k^2, -k^2.
3）链地址法(拉链法）
基本思想：将具有相同哈希地址的记录链成一个单链表，m个哈希地址就设m个单 链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构
排序
1.直接插入排序
（1）将第一个记录看做是长度为1的有序序列；
（2）从第2个元素开始，每一趟将1个新元素插入到已排好序的有序表中适当的位置，得到长度增1的有序表；（每一趟确定一个元素的最终位置）
（3）n-1趟插入后元素全部有序。
2.希尔排序
先将整个待排序记录序列分割成若干子序列(减少记录个数),分别进行直接插入排序，然后增加每个子序列中的记录数，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序（将下标相隔某个增量dk的记录组成一个子序列,让增量dk逐趟缩小，直到dk＝1为止。）
3.冒泡排序
每趟不断将相邻记录两两比较，若发生逆序，则进行交换
4.快速排序
从待排序列中任取一个元素 (通常取第一个) 作为枢轴，所有比它小的元素一律交换到前面，所有比它大的元素一律交换到后面，形成左右两个子表；然后再对各子表重新选择枢轴元素并依此规则调整，直到每个子表的元素只剩一个。此时为有序序列。
5.简单选择排序
首先，在n个记录中选择最小者放到r[1]位置（r[1]位置元素交换到最小者原先位置）；然后，从剩余的n-1个记录中选择最小者放到r[2]位置；…如此进行下去，直到全部有序为止
6.归并排序
将两个（或以上）的有序表合并成新的有序表
把一个长度为n 的无序序列看成是 n 个长度为 1 的有序子序列 ，两两归并，得到 （n / 2)向上取整 个长度为 2 的子序列 ；再做两两归并，…，如此重复，直到最后得到一个长度为 n 的有序序列。
