只能解决一种问题的算法，用处必然是有限的．所以今天介绍一种解决问题的思路，一个可以让我们使用的工具．Divide and Conquer分而治之
先来说明一下D&C的工作原理:
(1) 找出简单的基线条件(2) 确定如何缩小问题的规模，使其符合基线条件．
首先看一个例子
102030
比如我们要把上面几个数字相加，你首先想到的是什么? 我开始的时候，想到的是循环，我想你们应该也有和我想得一样的吧．
那好，今天我们换个思路，用我们的D&C的思想来解决．
上面的基线条件是什么？如何缩小它的规模，来符合我们的基线条件？
我们在计算一个整形数组的和的时候，最简单的情况是什么？
1.数组为空 2.数组只有一个元素
大多数情况下，我们要计算数组的和，那这个数组一般情况下是不会为空的．所以，我们的最理想的情况就是数组只有一个元素．基线条件已确定．
接下来，该如何将它分解到基线情况呢？
1.把第一个元素拆出来: 10 + sum(20+30)2.把第二个元素拆出来: 10 + sum(20 + sum(30))
一层一层递进，就可以求出数组所有元素的和． 好，下面看一下python代码:
def sum(L):#递归的退出条件if l == []:return 0return l[0] + sum(l[1:])
D&C思想了解了后，最后我们再看一下快速排序
快速排序是一种常用的排序算法，比选择排序快的多．
对一个数组进行排序，那什么情况是基线呢？其实和数组求和一样．如果这个数组是空，或者数组的只有一个元素，那么排序就很简单了，就是它自己．
先对一个含有三个元素的数组排序
7210
应用快速排序时，得先选择一个元素作为基准值(pivot),一般情况下，我们选择第一个元素作为基准值．
对于上面的数组，选择7作为基准值．
然后，向后遍历，遇到一个小于基准值的元素，放到基准值的左边．遇到一个大于基准值的元素，放到基准值的右边．这被称为分区(partitioning).
看一下现在的情况:
一个由所有小于基准值的数字组成的字数组;基准值;一个由所有大于基准值的数组组成的字数组．
现在，对于这个只有三个元素的数组，已经排序完毕．
然后，看一下含有４个元素的数组
128215
首先，12作为基准值，进行排序，第一轮完毕之后，是这个样子的:
821215
现在，排列情况是:
| <基准值 | 基准值 | ＞基准值 |
大于基准值的部分，只有一个元素，不需要排序了． 小于基准值的部分，两个元素，同样，我们按照上面的方法,递归调用，进行排序．最后，得到了:
281215
那，对于5个元素，6个元素，上千，上万的元素呢？同样啊，进行递归的调用，就可以排序了．
快速排序的python代码:
def quick_sort(arr):if len(arr) < 2:return arrelse:pivot = arr[0]less = [i for i in arr[1:] if i < pivot]greater = [j for j in arr[1:] if j > pivot]return quick_sort(less) + [pivot] + quick_sort(greater)print(quick_sort([2,8,12,15,32,4,56,12]))
输出结果:
[2, 4, 8, 12, 15, 32, 56]
快速排序的时间复杂度为O(nlogn)
注意:递归的退出条件一定要给出
最后，看一下快速排序的ｃ语言实现
#include<stdio.h>#define N 5int arr[N] = {23,65,156,545,32};void quick_sort(int arr[],int low,int high){//base valueint pivot = arr[low];int i = low;int j = high;if(i > j)return;while(i < j){while((i < j) && (arr[j] >= pivot))j--;if(i < j)arr[i] = arr[j];while((i < j) && (arr[i] <= pivot))i++;if(i < j)arr[j] = arr[i];}arr[i] = pivot;quick_sort(arr,low,i-1);quick_sort(arr,j+1,high);}void main(){int i;quick_sort(arr,0,4);for(i = 0;i < 5;i++){printf("%d n",arr[i]);}}
c语言的代码相对于python代码有点复杂．ｃ代码中定义了两个指针，来指向正在遍历的元素，一个指向小于pivot的，一个指向大于pivot的．
