整理自高教版《全国计算机等级考试二级教程——公共基础知识》和人邮版《全国计算机等级考试教程 二级公共基础知识》
查找技术
查找是指在一个给定的数据结构中查找某个指定的元素。
顺序查找
顺序查找又称顺序搜索，是从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到（即查找成功），若都不相等则表示线性表中没有要找的元素（查找失败）。
虽然顺序查找的效率不高，但是下列两种情况只能采用顺序查找：
- 线性表为无序表
- 线性表是有序线性表，但是采用链式存储结构
在最坏的情况下，顺序查找需要比较n次。
二分法查找
二分法查找（又称对分查找）只适用于顺序存储的有序表。
在此说的有序表是指线性表中的元素按值非递减排列（允许相邻元素值相等）。
对分查找的方法如下：
- 将x与线性表的中间项进行比较
- 若中间值等于x，则查找结束
- 若x小于中间项的值，则在线性表的前半部分以相同的方法进行查找
- 若x大于中间项的值，则在线性表的后半部分以相同的方法进行查找
- 这个过程一直进行到查找成功或子表长度为0（线性表中没有这个元素）为止
在最坏的情况下，二分查找需要比较log2n次。
排序技术
排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。
交换类排序法
交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。
冒泡排序法
冒泡排序法是通过相邻数据元素的交换逐步将线性表变成有序的一种排序方法。
假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍从后往前的扫描，需要的比较次数为n(n-2)/2。但这个工作量不是必需的，一般情况下要小于这个工作量。
快速排序法
快速排序法也是一种互换类的排序法，但由于它比冒泡排序法速度快，因此称之为快速排序法。
快速排序法在最坏情况下需要进行n（n-1）/2次，但实际排序效率要比冒泡排序法高得多。
插入类排序法
所谓插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。
简单插入排序法
在简单插入排序法中，每一次比较后最多移掉一个逆序，因此，这种排序方法的效率与冒泡排序法相同，在最坏情况下，简单插入排序法需要n(n-1)/2次比较。
希尔排序法
希尔排序法属于插入类排序，但它对简单插入排序做了较大的改进。
希尔排序的效率与所选取的增量序列有关。增量序列取h=n/2k(k=1,2,……,[log2n])（其中n为待排序序列的长度）时，在最坏的情况下，希尔排序所需要的比较次数为**O（n1.5）**。
选择类排序法
简单选择排序法
选择排序法的基本思想如下：
扫描整个线性表，从中选出最小的元素，将它交换到表的最前面，然后对剩下的子表采用同样的方法，直到子表为空为止。
简单选择排序法在最坏情况下需要比较n(n-1)/2次。
堆排序法
具有n个元素的序列（h1,h2,……,hn）当且仅当满足
（i=1,2,……,n/2）时称之为堆。
堆排序的方法对于规模较小的线性表并不合适，但对于较大规模的线性表来说是很有效的。在最坏情况下，堆排序需要比较的次数为O（nlog2n）。
