前一篇介紹了遞歸與尾遞歸，本篇將基于遞歸介紹快速排序等相關(guān)內(nèi)容。
閱讀本文你將收獲：
- 分而治之思想：簡稱
D&C，一種遞歸式解決問題方案。 - 快速排序：利用
D&C思想，實現(xiàn)的一種高效排序方法。
一、“分而治之”思想（D&C）
分而治之：（
divide and conquer，D&C）是一種著名的遞歸式解決問題的方法。
某一種解決問題的算法用處有限，而D&C為我們提供的是一種思路。
當我們面對一個復(fù)雜問題手足無措時，我們應(yīng)該自問：“D&C能解決該問題么？”
那么，D&C是什么？
1.1 什么是D&C？
使用D&C解決問題的過程分為兩個步驟：
- 找出基線條件，這個條件盡可能簡單。（基線條件的定義見上篇）
- 不斷將問題分解（縮小規(guī)模），直到全部符合基線條件。
1.2 D&C的實例
場景：假設(shè)你是一位農(nóng)場主，你有一塊長方形（168m x 64m）的地。
問題：現(xiàn)在你需要把這塊地分成若干個正方形的地（方便管理和種菜），問最大能拆分成多大的小正方形。（注意：不能留空地哦，最大利用土地資源）
方案一：找出“長”和“寬”中，相同的最大的公約數(shù)即可。（我的第一反應(yīng)是這樣算）
方案二：使用D&C思想，先從大長方形中去掉幾個最大的正方形，再去掉小長方形的幾個最大正方形，不斷尋找，直到?jīng)]有小長方形為止。
步驟：
- 找到基線條件：長是寬的整數(shù)倍
- 不斷分解：去除所有最大正方形后，對小長方形進行分解
圖解如圖：
第一次：找到兩個邊長為64m的大正方形，去除后，留下64m x 40m的小長方形。
第二次：找到一個邊長為40m的小正方形，去除后，留下40m x 24m的小長方形。
第三次：找到一個邊長為24m的小正方形，去除后，留下24m x 16m的小長方形。
第四次：找到一個邊長為16m的小正方形，取出后，留下16m x 8m的小長方形。
第五次：找到兩個邊長為8m的小正方形，正好分完。
因此，該農(nóng)場分為小正方形田地的最大邊長為8m。
而解決問題的思想，就是用的D&C思想。
我們再來回顧一下D&C思想的核心：
- 找出簡單的基線條件。
- 確定如何縮小問題的過，使其符合基線條件。
二、快速排序
快速排序（QuickSort）利用的就是D&C思想。它是一種高效的排序方案。
2.1 快排的思想（基于D&C）
- 基線條件：當排序數(shù)組元素個數(shù)小于2個時，直接返回。
- 縮小規(guī)模：每次從待排序數(shù)組中選取一個元素（基準值），把小于等于該元素的元素放在一側(cè)，把大于該元素的元素放在另一側(cè)。再對兩邊的小數(shù)組做重復(fù)操作。
2.2 快排的示例
基于Python，實現(xiàn)了一個快排：
代碼如下：
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中，選取的數(shù)組的最后一個元素為基準值，把小于等于基準值的元素放在左側(cè)，大于基準值的元素放在右側(cè)。
