计算机二级公共基础知识 查找和排序思维导图
计算机二级公共基础知识 查找和排序
树图思维导图提供 计算机二级公共基础知识 查找和排序 在线思维导图免费制作，点击“编辑”按钮，可对 计算机二级公共基础知识 查找和排序 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：080b45e1a601ef7262793d4f7d6ad67a
思维导图大纲
计算机二级公共基础知识 查找 排序思维导图模板大纲
查找
查找
根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素
查找结果
（查找成功：找到；查找不成功：没找到。）
平均查找长度
查找过程中关键字和给定值比较的平均次数
查找分为
顺序查找（线性查找）和二分法查找（折半查找）
Tips
二分查找只适用于顺序存储的有序表，最坏比较log2n次，而采用链式存储结构的表只能用顺序查找，最坏比较n次
对于长度为n的有序线性表，最坏情况只需比较(log2n)+1次，而顺序查找需要比较n次
排序
含义
将一个无序序列整理成按值非递减顺序排列的有序序列
方法
交换类排序法
冒泡排序（O（n2））、快速排序
插入类排序法
简单插入排序、折半插入排序、希尔排序（将整个无序序列分割成若干个子序列分别插入）
选择类排序法
简单选择排序、堆排序
最坏需要比较的次数
快速排序法、简单插入排序法、简单选择排序法最坏需要比较的次数为n(n-1)/2
希尔排序：O(n^1.5)次
堆排序：O(nlog(2^(n)）次
注意
只有希尔排序和堆排序是列外，其余排序的最坏需要比较次数相同
循坏链表中寻找最大项的时间复杂度为o（n-1）
有序链表查找的时间复杂度为o（n）
相关思维导图模板
树图思维导图提供 904名中国成年人第三磨牙相关知识、态度、行为和病史的横断面调查 在线思维导图免费制作，点击“编辑”按钮，可对 904名中国成年人第三磨牙相关知识、态度、行为和病史的横断面调查 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：10b9a8a2dd2fb4593f8130ef16c320fc
树图思维导图提供 Linux 网络基础知识 在线思维导图免费制作，点击“编辑”按钮，可对 Linux 网络基础知识 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：199680f0e48eac8a1aeaadb90447d4f4
沪公网安备 31011502019485号
上海工商