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