这一章主要介绍分而治之算法（divide and conquer，D&C），后面要介绍的快排就是一种分治算法。时间复杂度为O(nlogn)。
    在介绍例子的时候引入了欧几里得算法，也称为辗转相除法。
    有公式：gcd(a,b) = gcd(b,a mod b)
    也就是说，b和a mod b的最大公约数，一定是a,b的最大公约数，…… 这正好符合题目的思想。
    因此分治的工作原理：
    1.找到简单的基线条件。
    2.确定如何缩小问题的规模，使其符合基线条件。

    用分治法求一个数组中所有元素的和。（其实本题中不算严格的分治，只是去领会一下分治和循环有什么差别）
    执行代码：
    #include
    using namespace std;
    int sum_arr(int arr[], int len)
    {
    int sum = 0;
    if(len == 1 )
    {
    sum = arr[0]; //数组长度为1时，sum就等于它本身的值
    }
    else{
    int first = arr[0];
    for(int i=0;i {
    arr[i] = arr[i+1];
    }
    len -= 1;
    sum = first + sum_arr(arr,len);
    }
    return sum;
    }
    int main()
    {
    int list[] = {1,2,3,4,5,6,7,8,9,10,11,12};
    int length = sizeof(list)/sizeof(int);
    cout< return 0;
    }

    下面开始学快速排序：
    首先，回忆考研时我对快排的理解。当时我并不知道它运用到了分治的算法，我只知道它还是比较麻烦的，先设置一个基准值，用最左边的值与基准值比较，再去最右边比较，来回几趟进行比较再排序。
    但是当我今天再看快排时，果然用到了分治的影子。时间复杂度就是这么算出来的。
    快排的两个条件：
    1.基线条件：当数组为空或者只含有一个元素时，数组是有序的，返回数组本身；
    2.递归条件：由所有小于基准值的元素组成一个子数组，由所有大于基准值的元素组成一个子数组。并且返回
    quicksort(左子数组）+基准值+quicksort(右子数组）；
    image.png
    这么一来又复习了一遍数学归纳法：
    image.png
    以上是快排的分治的思想，找到基线条件，并将问题缩小规模求解。

    至于时间复杂度：
    首先对于已经有序的数列，如果基准值的选择每次都选择第一个元素，将导致：
    image.png
    图中表达的就是需要选择n趟基准值（趟数），而每次都需要遍历数组所有元素，小的放基准值左边，大的放右边，即对数组全体元素操作，时间复杂度为O(n),这么一来总的时间复杂度就为O(n^2).即最差情况。

    但是，倘若每次基准值是随机选的，若取中间那个元素作为基准值：
    image.png
    只需要选择logn趟基准值数组就能俺顺序分开，但是每一趟的操作数仍然是O(n).（因为仍然是遍历找基准值的左右数组）
    所以总的时间复杂度为O(nlogn)。这是最佳情况的复杂度，代表的也是平均情况复杂度。
    image.png