国二计算机考试内部队列知识点思维导图
简单介绍国二计算机考试内部队列知识点内容
树图思维导图提供 国二计算机考试内部队列知识点思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 国二计算机考试内部队列知识点思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：2f464798af1f0ee5ad2d1436c12d252a
思维导图大纲
内部队列思维导图模板大纲
选择排序
堆排序
输出堆顶元素
步骤
把堆顶元素输出，把堆底元素放到堆顶
从堆顶开始和自己的左右孩子比较并调整下坠（从上到下，每次比较一个或两个元素）
插入元素
步骤
把元素放在堆底
从堆底开始依次和父节点比较交换，元素不断上升（每次比较一个元素，和父节点）
删除元素
把元素删除，用堆底元素替代
堆底元素不断下坠
建堆
特点
建立大根堆或小根堆，时间复杂度为O（n）,插入删除调整堆时间复杂度为log2n
最大/最小元素在堆顶；第二大/小元素在第二层；第三大/小元素在第二或第三层
左右孩子数值相等，优先和左孩子交换
步骤
把所有元素排成完全二叉树
从第一个非叶结点到根结点依次和自己孩子们比较调整（从下到上，从右到左）
第一轮到根节点处根节点可能和孩子结点交换后孩子结点不满足堆要求，此时从上向下调整
简单选择排序
从待排元素中选择一个最小的元素放在前面
元素移动次数很少，但比较次数和初始状态无关，为n(n-1)/2
归并排序
归并趟数：logk(n)向上取整
这里的一趟也就是树形结构中的一层
两个有序段归并，最少比较次数是一个段元素都小于另一个段；最大比较次数是两者交错进行
基数排序
注意分配和收集的细节（从左当到右，从上到下）
基数排序不能对float和double类型的数进行排序
效率
n个元素；d趟分配和收集；r个辅助队列
空间复杂度：O（r）；时间复杂度：O（d(n+r)）
时间复杂度与序列初始状态无关
过程
相关思维导图模板
树图思维导图提供 作业帮思维脑图 在线思维导图免费制作，点击“编辑”按钮，可对 作业帮思维脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：0fa2dfe58ee459432166d72cafc50675
树图思维导图提供 系统需求分析与设计文档描述实践（作业名称） 在线思维导图免费制作，点击“编辑”按钮，可对 系统需求分析与设计文档描述实践（作业名称） 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：53431533c8b70140e2fb252631ff8c4b
沪公网安备 31011502019485号
上海工商