归并排序和基数排序思维导图
归并排序和基数排序详解
树图思维导图提供 归并排序和基数排序 在线思维导图免费制作，点击“编辑”按钮，可对 归并排序和基数排序 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：da402d582cf8c881a01901c0b4ab0090
思维导图大纲
归并排序和基数排序思维导图模板大纲
归并排序
思想
归并
把两个或多个有序子序列合并为1个
k路归并
k合一
每选出一个元素需要对比关键字k - 1次
n个元素下归并趟数⌈logn⌉（以k为底），这里同样是树高，却是向上取整，因为这里的n是叶子数不是树的总结点数！
实现过程
其实是一棵倒立的二叉树
代码
也要会背，尤其会归并
算法思想
low < high，将序列从中间mid = （low + high）/ 2分开
对左半部分[low,mid]递归归并排序，右半部分[mid+1，high]递归，将左右两个子表Merge成一个
性能
空间复杂度
O(n)，来自辅助数组
时间复杂度
O(nlogn)，每趟归并O(n)，归并趟数O(logn)
算法排序码比较次数和元素移动次数为right - left + 1
稳定
常常用于文件排序
归并问题
两个有序序列各有M、N个元素，比较次数为
最少：min（M,N）次
其中一个序列全小于另一个序列
最多：M+N-1次
两个表的指针交替动
时间复杂度O(m + n)，也可为O(max(m,n))，因为2max(m,n)≥m + n
二路归并排序递归算法采取策略：分治
归并排序适合并行处理
基数排序
思想
将整个关键字分为d位，作d次“排序码”的比较
按关键字位“权重递增”（也称LSD，如“个十百”）次序，做d趟“分配”与“收集”
若当前处理关键字位可能取r个值，需建立r个队列
分配：顺序扫描根元素，根据当前处理的关键字位，拆相应队列，一趟O(n)
收集：各队列中结点一次出队并链接，一趟O(r)
举例说明
第一趟，基于个位“分配”；最终收集结果：438->888->168->007->666->996->985->233->211->111->520
性能
空间复杂度
O(r)，r个辅助队列
时间复杂度
O(d(n+r))，一趟分配O(n)，一趟收集O(r)，总共d趟分配收集
稳定
最大最重要特点：
不基于比较和移动进行排序
擅长处理
关键字可以拆分为d组，且d较小
每组关键字取值范围不大，即r较小
元素个数n较大
类基数排序
LSD：权重递减；MSD：权重递增
如果要求有两个数据项m和n，先看m，m小的元素在前，大的在后；在m相同的情况下，再看n，n小的在前，大的在后
可以类比LSD，此时m的权重 ＞ n的权重
因此：先排n，后排m，并且为了不破坏“m相同看n”，后排m的算法要稳定！
沪公网安备 31011502019485号
上海工商