计算机考试知识点查找技术与排序技术思维导图
本思维导图主要总结国家计算机等级考试公共基础知识部分知识点查找技术与排序技术
树图思维导图提供 计算机考试知识点查找技术与排序技术思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 计算机考试知识点查找技术与排序技术思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：8eb35ecb657dbe16c3d297cb49828fb3
思维导图大纲
计算机考试知识点查找技术与排序技术思维导图模板大纲
查找技术
概念
查找就是从给定的一个数据结构中，找出指定的数据元素。
本节中只学习对线性表的查找，常用的查找方法有顺序查找和二分法查找。
1．顺序查找
顺序查找的过程是：
从线性表的第一个元素开始，依次将线性表中的数据与要查找的数据进行比较
如果找到了相等的数据，则查找成功， 停止向下查找
如果比较完了线性表中的所有数据元素，没有找到相等的数据，则查找失败。
2．二分法查找
二分法查找又称为折半查找，只能应用于顺序存储的有序表。
有序表是指线性表中的元素已经按值非递减（从整体上看是升序，但相邻的元素的值可以相同）排列。
排序技术
概念
排序就是将一组无序的数据按照一定的顺序排列起来。
本节中所指的顺序是非递减顺序（整体上呈升序，但相邻的数据可以相等），基本排序算法主要有交换类排序、插入类排序和选择类排序 3 大类。
1．交换类排序
交换排序就是借助数据元素之间的互相交换进行排序的方法。常用的交换排序方法有冒泡排序和快速排序。
（1）冒泡排序
冒泡排序的过程简单，它的基本思想是通过对相邻元素进行比较，并根据比较的结果交换位置，从而逐步由任意序列变为有序序列。
过程是：
先从头往后扫描、然后从后往头扫描、再重复上述过程
（2）快速排序
快速排序就是一种可以通过一次交换而消除多个逆序的排序方法，因此相对冒泡排序法而言，速度要快。
2．插入类排序
插入排序，就是将无序序列中的各个元素依次插入到已经排好序的线性表中。常用的插入排序的方法有简单插入排序和希尔排序。
（1）简单插入排序
简单插入排序的方法是：
在初始序列中， 将只包含第 1 个元素的子序列看成是一个有序序列，然后从第 2 个元素起，依次将每个元素插入到前 1 个有序子序列中。
（2）希尔排序
希尔排序的基本思想是：
将整个无序序列分割成若干个子序列，对每个子序列分别进行简单插入排序，最后再对全体元素进行一次简单插入排序。
与简单插入排序的子序列构成方式不同，希尔排序是将原序列中相隔某个增量h 的元素构成一个子序列。
在排序过程中逐步减少这个增量，最后当 h 减到 1 时，进行一次插入排序，排序就完成了。
希尔排序的效率与所选取的增量序列有关。通过希尔排序法对长度为 n 的线性表进行排序，如果选取了上述增量序列，最坏情况下，需要比较的次数为 O(n1.5)。
3．选择类排序
常用的选择排序有两种，简单选择排序和堆排序。
（1）简单选择排序
简单选择排序的基本步骤是：
①在一组n 个数据中选择出最小值；
②若它不是这组数据中的第 1 个数据，则将它与这组数据中的第 1 个数据互换位置；
③对剩下的子表采用同样的方法，直到子表空为止。
（2）堆排序法
在学习堆排序之前，我们先来看一下堆的定义，堆的定义如下：
相关思维导图模板
树图思维导图提供 计算机考试知识点文件的读写思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 计算机考试知识点文件的读写思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：3addfcccb8839b09c49d9cf6c7c011d1
树图思维导图提供 计算机考试知识点文件指针思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 计算机考试知识点文件指针思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：3b7318d886411679e5e0eb18447fbd02
沪公网安备 31011502019485号
上海工商