前一篇介绍了递归与尾递归，本篇将基于递归介绍快速排序等相关内容。
阅读本文你将收获：
- 分而治之思想：简称
D&C，一种递归式解决问题方案。 - 快速排序：利用
D&C思想，实现的一种高效排序方法。
一、“分而治之”思想（D&C）
分而治之：（
divide and conquer，D&C）是一种著名的递归式解决问题的方法。
某一种解决问题的算法用处有限，而D&C为我们提供的是一种思路。
当我们面对一个复杂问题手足无措时，我们应该自问：“D&C能解决该问题么？”
那么，D&C是什么？
1.1 什么是D&C？
使用D&C解决问题的过程分为两个步骤：
- 找出基线条件，这个条件尽可能简单。（基线条件的定义见上篇）
- 不断将问题分解（缩小规模），直到全部符合基线条件。
1.2 D&C的实例
场景：假设你是一位农场主，你有一块长方形（168m x 64m）的地。
问题：现在你需要把这块地分成若干个正方形的地（方便管理和种菜），问最大能拆分成多大的小正方形。（注意：不能留空地哦，最大利用土地资源）
-
方案一：找出“长”和“宽”中，相同的最大的公约数即可。（我的第一反应是这样算）
-
方案二：使用D&C思想，先从大长方形中去掉几个最大的正方形，再去掉小长方形的几个最大正方形，不断寻找，直到没有小长方形为止。
步骤：
- 找到基线条件：长是宽的整数倍
- 不断分解：去除所有最大正方形后，对小长方形进行分解
图解如图：
第一次：找到两个边长为64m的大正方形，去除后，留下64m x 40m的小长方形。
第二次：找到一个边长为40m的小正方形，去除后，留下40m x 24m的小长方形。
第三次：找到一个边长为24m的小正方形，去除后，留下24m x 16m的小长方形。
第四次：找到一个边长为16m的小正方形，取出后，留下16m x 8m的小长方形。
第五次：找到两个边长为8m的小正方形，正好分完。
因此，该农场分为小正方形田地的最大边长为8m。
而解决问题的思想，就是用的D&C思想。
我们再来回顾一下D&C思想的核心：
- 找出简单的基线条件。
- 确定如何缩小问题的过，使其符合基线条件。
二、快速排序
快速排序（QuickSort）利用的就是D&C思想。它是一种高效的排序方案。
2.1 快排的思想（基于D&C）
- 基线条件：当排序数组元素个数小于2个时，直接返回。
- 缩小规模：每次从待排序数组中选取一个元素（基准值），把小于等于该元素的元素放在一侧，把大于该元素的元素放在另一侧。再对两边的小数组做重复操作。
2.2 快排的示例
基于Python，实现了一个快排：
代码如下：
def quickSort(arr):
if len(arr) < 2:
return arr
else:
pivot = arr[0]
less = [i for i in arr[1:] if i <= pivot]
greater = [i for i in arr[1:] if i > pivot]
return quickSort(less) + [pivot] + quickSort(greater)
print quickSort([10, 2, 6, 4, 7, 2])
解读一下代码：
PS：基准值一般可以选取第一个元素，也可以选择最后一个元素。
2.3 快排的动画演示
本Demo中，选取的数组的最后一个元素为基准值，把小于等于基准值的元素放在左侧，大于基准值的元素放在右侧。
网友评论