![](https://csdnimg.cn/release/download_crawler_static/87213823/bg6.jpg)
基本思想:从表中的第一个元素开始,将给定的值与表中逐个元素的关键字进行比较,直到
两者相符,查到所要找的元素为止。否则就是表中没有要找的元素,查找不成功。
在平均情况下,利用顺序查找法在线性表中查找一个元素,大约要与线性表中一半的元素进
行比较,最坏情况下需要比较 n 次。
顺序查找一个具有 n 个元素的线性表,其平均复杂度为 O(n)。
下列两种情况下只能采用顺序查找:
1)如果线性表是无序表(即表中的元素是无序的),则不管是顺序存储结构还是链式存储
结构,都只能用顺序查找。
2)即使是有序线性表,如果采用链式存储结构,也只能用顺序查找。
2、二分法查找
思想:先确定待查找记录所在的范围,然后逐步缩小范围,直到找到或确认找不到该记录为
止。
前提:必须在具有顺序存储结构的有序表中进行。
查找过程:
1)若中间项(中间项 mid=(n-1)/2,mid 的值四舍五入取整)的值等于 x,则说明已查到;
2)若 x 小于中间项的值,则在线性表的前半部分查找;
3)若 x 大于中间项的值,则在线性表的后半部分查找。
特点:比顺序查找方法效率高。最坏的情况下,需要比较 log2n 次。
*:二分法查找只适用于顺序存储的线性表,且表中元素必须按关键字有序(升序)排列。
对于无序线性表和线性表的链式存储结构只能用顺序查找。在长度为 n 的有序线性表中进行
二分法查找,其时间复杂度为 O(log2n)。
1.8 排序技术
排序是指将一个无序序列整理成按值非递减顺序排列的有序序列,即是将无序的记录序列调
整为有序记录序列的一种操作。
1、交换类排序法(方法:冒泡排序,快速排序)。
2、插入类排序法(方法:简单插入排序,希尔排序)。
3、选择类排序法(方法:简单选择排序,堆排序)。
总结:各种排序法比较:
本章应考点拨:本章内容在笔试中会出现 5-6 个题目,是公共基础知识部分出题量比较多
的一章,所占分值也比较大,约 10 分。