递归行为
利用递归求整个数组的最大值，代码如下。
int find_Max(int a[], int L, int R)
{
if (L == R)
{
return a[L];
}
int mid = L + ((R - L) >> 1);//mid是数组的中点
int leftMax = find_Max(a, L, mid);
int rightMax = find_Max(a, mid+1, R);
return std::max(leftMax, rightMax);
}类似一个二叉树，不知道的结果压栈继续算，已经知道的结果从栈里弹出。
递归行为的时间复杂度估计：
只要是满足子问题等规模的递归，都可以用master公式计算时间复杂度。
master公式：T(N)=a*T(N/b)+O(N^d)，T(N)指的是母问题的数据量是N级别的，a是子问题的调用次数，b是子问题的规模（这个问题中每个子问题的规模都一样），O(N^d)是除去子问题的调用之外，剩下的过程的时间复杂度。find_Max就满足master公式，find_Max 的T (N)=2*T(N/2)+O(1)。
知道master公式的a、b、d三个参数后，时间复杂度如何求呢？
时间复杂度=
O(N^d)，若logb(a) < d;
O(N^(logb(a))) ，若logb(a) > d;
O(N^d*logN)， 若logb(a) = d;
归并排序：
先把待排序数组分成等大的左右两个子数组，然后分别将左右数组排序（递归调用），最后将左右两个数组按序合在一起后拷贝给原数组，完成排序。以下程序中的mergeSort（）为归并排序，merge（）的功能为将分开的左右两个数组按序合在一起后拷贝给原数组。代码如下：
#include<iostream>
#include<vector>
void merge(std::vector<int>& arr, int L, int mid, int R);
void mergeSort(std::vector<int>& arr, int L, int R)
{
if (L == R) {
return;
}
int mid = L + ((R - L) >> 1);
mergeSort(arr, L, mid);
mergeSort(arr, mid + 1, R);
merge(arr, L, mid, R);
}
void merge(std::vector<int>& arr, int L, int mid, int R)
{
std::vector<int> help(R - L + 1);
int n1 = L;
int n2 = mid + 1;
int i = 0;
while (n1 <= mid && n2 <= R)
{
help[i++] = arr[n1] < arr[n2] ? arr[n1++] : arr[n2++];
}
while (n1 <= mid)
{
help[i++] = arr[n1++];
}
while (n2 <= R)
{
help[i++] = arr[n2++];
}
for (i = L; i <= R; i++)
{
arr[i] = help[i - L];
}
}
int main() {
std::vector<int> arr = { 12, 11, 13, 5, 6, 7,5,1,2,3,8,2,35,3 };
int n = (int)arr.size();
mergeSort(arr, 0, n - 1);
std::cout << "排序后的数组：";
for (int i = 0; i < n; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}归并排序的时间复杂度：应用master公式：T (N)=2*T(N/2)+O(N)，a=2，b=2，d=1，logb（a）=d，时间复杂度为O(N*logN)。
归并排序的额外空间复杂度：O(N)。
归并排序时间复杂度较好的原因：没有浪费比较行为，每次比较都产生了有序。
归并排序的扩展问题：
1.小和问题：在一个数组中，每一个数左边比当前的数小的数累加起来，叫做这个数组的小和。求一个数组的小和。代码如下：
#include<iostream>
#include<vector>
int merge(std::vector<int>& arr, int L, int mid, int R);
int mergeSort(std::vector<int>& arr, int L, int R)
{
if (L == R) {
return 0;
}
int mid = L + ((R - L) >> 1);
return mergeSort(arr, L, mid) + mergeSort(arr, mid + 1, R) + merge(arr, L, mid, R);
}
int merge(std::vector<int>& arr, int L, int mid, int R)
{
int small_sum = 0;
std::vector<int> help(R - L + 1);
int n1 = L;
int n2 = mid + 1;
int i = 0;
while (n1 <= mid && n2 <= R)
{
small_sum += arr[n1] < arr[n2] ? (R - n2 + 1) * arr[n1] : 0;
help[i++] = arr[n1] < arr[n2] ? arr[n1++] : arr[n2++];
}
while (n1 <= mid)
{
help[i++] = arr[n1++];
}
while (n2 <= R)
{
help[i++] = arr[n2++];
}
for (i = L; i <= R; i++)
{
arr[i] = help[i - L];
}
return small_sum;
}
int main() {
std::vector<int> arr = {1, 4, 5};
int n = (int)arr.size();
int small_sum = mergeSort(arr, 0, n - 1);
std::cout << "排序后的数组：";
for (int i = 0; i < n; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
std::cout << "小和等于:" << small_sum << std::endl;
return 0;
}2.逆序对问题：在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，求逆序对的数量。
逆序对问题和上面的小和问题是等效的。只不过小和问题是左边比右边的数小，而逆序对问题则相反。
快速排序
先解决荷兰国旗问题，再递归。时间复杂度为O(N*logN)。
荷兰国旗问题：给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。额外空间复杂度0(1)，时间复杂度O(N)。
快速排序的代码如下：
int* partition(int* arr, int L, int R)
{
int less = L - 1;
int more = R;
int* a = new int[2];
while (L < more){
if (arr[L] < arr[R]){
std::swap(arr[++less], arr[L++]);
}
else if (arr[L] > arr[R]){
std::swap(arr[--more], arr[L]);
}
else{
L++;
}
}
std::swap(arr[more], arr[R]);
a[0] = less + 1;
a[1] = more;
return a;
}
void quickSort(int* arr, int L, int R)
{
if (L < R) {
std::swap(arr[rand() % (R - L + 1) + L], arr[R]);
int* a = partition(arr, L, R);
quickSort(arr, L, a[0] - 1);
quickSort(arr, a[1] + 1, R);
}
}