Divide and conquer (D&C) is an algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

D&C

分而治之，提供的是解决问题的一种思路。使用D&C解决问题的过程包括两个步骤：
1.找出基线条件，这种条件必须尽可能简单。
2.不断将问题分解（或者缩小规模），直到符合基线条件

快速排序

下面以快排为例进行讲解，对排序算法来说，最简单的数组就是“不用排序”的数组。

1.空数组
2.数组中只有一个数字

因此基线条件为数组为空或者只包含一个元素。这时候只需原样返回数组即可。

要使用D&C，需要将数组分解，直到满足基线条件。首先，从数组中选择一个元素作为基准值（pivot）。找出比基准值大的元素和比基准值小的元素。这个过程被称为分区（patitioning）。
现在你将数组分成了三个部分：

1.小于基准值的数组成的子数组
2.基准值
3.大于基准值的数组成的子数组

快排代码：

1
2
3
4
5
6
7
8
def quicksort(arr):
  if  len(arr)<2:
    return arr
  else:
    pivot = arr[0]
    less = [i for i in arrray[1:] if i <= pivot]
    greater = [i for i in arrray[1:] if i > pivot]
    return quicksort(less) + [pivot] + quicksort(greater)

参考书目：
[^1]: 《算法图解》【美】Aditya Bhargava. 编著