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