算法图解四（快速排序）

给大家分享快速排序之前，讲一下D&C算法。（分而治之算法）

EX:

将一块长方形的土地，分成最多正方形，且不浪费，怎么做？

这时候就要用到D&C算法。将长方形的宽，作为最大的正方形的边。首先切除一个正方形。再从剩下的长方形中再切出一个（以长方形宽为边的正方形）。用这个方法直到找出最小的一个正方形。大功告成！

图片来自《算法图解》 图片来自《算法图解》 图片来自《算法图解》 图片来自《算法图解》

EX:

用递归算法求一个列表中所有数字之和？下列Code 使用D&C算法

（1）找出简单的基准条件。

（2）缩小问题的规模，使其符合基准条件。

快速排序就是建立D&C算法的基础之上的算法。

（1）选出基准值。

（2）将数组分成两个子数组。小于基准值的元素和大于基准值的元素。

（3）对这个两个子数组进行快速排序。

算法时间：

二分查找O(logn)<快速排序O(nlogn)<选择排序O(n*2)

PS:

如果你阅读之后，有所收获。请记得点赞哦。o(*￣︶￣*)o。你的支持将是我写作的动力。