分治思想的运用

1. 分:整体问题变为局部问题。
2. 合:然后利用局部问题的解，得到整体问题的解。

有的问题在分阶段起关键作用，有的问题在合阶段起关键作用(比如归并排序,分阶段并没有得到解决,合并阶段完成才得到排序结果)

一些比较形象的分治思想的应用。

分治思想，对应的编程实现方式一般是递归的。

排序问题和分治思想

排序的分治思路:每次处理后,一个或多个树被放在了最终的位置.(排序后的应该在的位置)。或者一个或多个数的相对位置被调整到了和最终的相对位置一致。//如果所有数的相对位置一致，那么这个数组自然就有序了。

递归的编码方式:树形处理顺序,压栈,压栈…,弹栈,弹栈, // 分 [] | A类问题 [] / \ 问题规模更小的A类问题 [] /\ /\ 问题规模再小的A类问题 // 治: 有时合就是治的一种方法.

快速排序: 每次把一个数放在合适的位置,在分的阶段解决问题?

归并排序: 每次把多个数的相对位置调整正确,在合的阶段解决问题? 注意合并之后这些数也没有在最终应该在的位置,只是相对位置已经是最终的相对位置了。

快速排序partition函数扩展

O(n) 时间复杂度内求无序数组中的第 K 大元素。

归并排序总结

归并排序是否稳定排序? 归并排序的空间复杂度是多少？ 归并排序为什么使用不广泛,有啥缺陷?