分治思想
分治是一种编程思想 递归是一种编程技巧 分治一般由递归来实现
归并排序 稳定 主要看 子数组 排序后 merge 合并的函数如何执行 可以按先后顺序 合并 merge 函数 保证算法的稳定性
不仅递归求解的问题可以写成递推公式, 递归代码的时间复杂度也可以写成递推公式
时间复杂度是非常稳定 不管 数据之前顺序如何 都要重新拍一遍 不管是最好情况、最坏情况,还是平均情况,时间复杂度都是 O(nlogn)
每次合并都要频繁的申请新的内存空间 存储合并后的数据 虽然最大也就是 申请 元素个数个大小 n个大小 而且用完就释放 但是 频繁的 申请 释放 也会造成不小的资源开销 复制移动 更新 因为用完就释放所以 空间复杂度是 O(n) 虽然归并排序稳定但是, 归并排序不是原地排序算法,所以还是没有快速排序那样风靡各大技术 的底层排序
原地分区函数的实现思路非常巧妙 用交换代替插入 节约了时间和内存资源 但是 破坏了稳定性 老师画的图 一目了然
归并由上到下 快排由下到上
两个极端情况下的时间复杂度