算法图解 | 分而治之与快速排序算法
分而治之D&C
分而治之不是一种解决问题的算法，而是一种希望问题分解，将复杂的问题划分为多个简单问题来解决的思想。
分而治之的思想重点：
（1）找出简单的基线条件
（2）确定如何缩小问题的规模，使其符合基线条件。
快速排序
例如快速排序问题，一个列表进行排序，如下图
首先选择列表中的一个元素作为基准元素，其他的元素都与这个元素做比较，找出小于这个基准值的值、大于基准值的值。这称为“分区”，这时有，
1）一个由所有小于基准值的数字组成的子数组；
2）基准值
3）一个由所有大于基准值的数组组成的子数组
然后再将“小于v”和“大于v”的数据块作为子数组，同样选择基准值，再进行上述类似操作，当执行到数据块中只有1个元素或者0个元素时，即完成排序。
这个问题中的基线条件是执行到数据块中只有1个或者0个元素；
例如下面的数组，进行排序：
根据选择的基准值，对这个数组进行分区的各种可能方式如下：
假设你将3用作基准值，可对得到的子数组进行快速排序。
还有一个例子，如下图：
图片来自极客学院
快速排序代码：
算法复杂度
看一下其他的算法的复杂度（O表示法表示）
快速排序的性能高度依赖于你选择的基准值。
最糟情况：算法复杂度O(n^2)
假设总是将第一个元素用作基准值，且要处理的数组是有序的。由于快速排序算法不检查输入数组是否有序，因此它依然尝试对其进行排序。
注意，数组并没有被分成两半，相反，其中一个子数组始终为空，这导致调用栈非常长。
这个示例展示的是最糟情况，在最糟情况下，栈长为O(n)，在调用栈的每层都涉及O(n)个元素，完成每层所需的时间都为O(n)。因此整个算法需要的时间为O(n) * O(n) = O(n^2)。
最佳情况：算法复杂度O(n log n)
假设总是将中间的元素用作基准值，在这种情况下，调用栈如下。
调用栈短得多！因为每次都将数组分成两半，所以不需要那么多递归调用。很快就到达
了基线条件，因此调用栈短得多。
这个示例展示的是最佳情况，在最佳情况下，栈长为O(log n)，每一层运行时间为O(n),所以整个算法需要的时间为O(n) * O(log n) = O(n log n)。
平均情况：算法复杂度O(n log n)
最佳情况也是平均情况。只要每次都随机地选择一个数组元素作为基准值，快速排序的平均运行时间就将为O(n log n)。快速排序是最快的排序算法之一，也是D&C典范。
如何选择基准值?
实现快速排序时，请随机地选择用作基准值的元素。快速排序的平均运行时间为O(n log n)。
总结
1）D&C将问题逐步分解。使用D&C处理列表时，基线条件很可能是空数组或只包含一个元
素的数组。
2）实现快速排序时，请随机地选择用作基准值的元素。快速排序的平均运行时间为O(n log n)。
3）大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在。
更多细节参考《算法图解》
私信发送“算法”获取《算法图解》PDF,发送“算法地图”获取机器学习算法地图。
閱讀更多 AI深度學習求索 的文章
