算法理解了就很简单，写代码也容易，但是表达清楚原理就很麻烦。如果没看懂就去看大神的博客吧。
分治法
分治法其实很常见，在并归排序的过程也用上了。
接下来举一个例子：
寻找平面内最近的一对点
https://blog.csdn.net/weixin_37540865/article/details/78201399。
- 暴力：计算n个点两两距离，O(N^2)
- 分治：
- 对于所有有点，按照一个轴排序O(nlog(n))，一分为二
- 找到左右各自最短距离dl, dr
- 合并起来
![]()
这里复杂就复杂在合并的时候考虑的情况太多。如果这个点的x坐标和中间数的差值大于d，那么就不用考虑这个点了。也就是说我们仅仅需要考虑如下中间的带状区域里的点：
d=min(dl,dr)
然后需要对灰色带里的两边分别排序，从上到下各自遍历一遍：
- 遍历的时候，只需要看对面的上下d距离的正方形里有没有点，然后计算距离就好了，这一步的复杂度是O(1)
- 左遍历一遍，高2d，长度为d的矩形内最多最多边角6个点，因为如果超过6个点就不满足最小距离是d
我虽然理解了，表达实在是费劲，没理解的还是去看上面那篇博客吧
第k大数
仿照快速排序，随机选一个值当做阈值，然后一分为二，如果左边只有k-1个数，那么就选对了；如果一边多一边少，就继续在多的那边选