递归行为时间复杂度计算：master公式
T(N) = a * T(N/b) + O(Nd)
N：母问题规模
a：子问题计算次数
N/b：子问题规模
O(Nd)：每次递归除子问题外其他操作时间复杂度
1）log(b,a) > d : T(N) = O(Nlog(b,a))
2）log(b,a) < d : T(N) = O(Nd)
3）log(b,a) == d : T(N) = O(Nd * logN)
使用master公式的前提：子问题等规模
如使用递归求数组最大值：
// 将数组分为左右两个子数组，分别求两个子数组最大值，返回两个最大值中更大者
int process(vector<int>& nums, int l,int r){
if(l == r){ // 递归结束条件
return nums[l];
}
int m = l + ((r - l) >> 1); // 括号保证 >> 运算先于 +
int leftMax = process (nums, l, m);
int rightMax = process (nums, m+1, r); //是 m+1 不是 m
return max(leftMax, rightMax);
}
int getMax(vector<int>& nums){
return process(nums, 0, nums.size() - 1);
}
/*
此递归中 a = 2 ,b = 2, d = 0
log(b,a) > d : T(N) = O(N ^ log(b,a)) = O(N)
此递归算法的时间复杂度与遍历数组找最大值算法相同
如果递归算法改为：
计算数组前2/3部分和后2/3部分最大值，返回两个最大值中更大者
由于子问题都是 2*N/3 规模，依然可以使用master公式
*/归并排序
1）整体就是一个简单递归，左边排好序，右边排好序，让其整体有序
2）让其整体有序的过程采用了外排序的方法（排到外部数组里再拷贝回来）
时间复杂度O(N*logN) 空间复杂度O(N)
void merge(vector<int>& nums, int l, int m, int r){
// 存放两半数组merge后结果，最后拷贝到nums数组
vector<int> help(r - l + 1, 0);
// 三个指针，分别指向help数组，左右两半数组
int i = 0;
int p1 = l;
int p2 = m +1;
// 两半数组中最小的放入help
while(p1 <= m && p2 <= r){
help[i++] = nums[p1] <= nums[p2] ? nums[p1++] : nums[p2++];
}
// 两半数组中一个已遍历完，另一个数组中还未遍历的依次拷贝到help
while(p1 <= m){
help[i++] = nums[p1++];
}
while(p2 <= r){
help[i++] = nums[p2++];
}
// 将排好序的help数组拷贝到nums相应位置
for(i = 0; i < help.size(); i++){
nums[l + i] = help[i];
}
}
void process(vector<int>& nums, int l,int r){
if(l == r){ // 递归结束条件
return;
}
int m = l + ((r - l) >> 1);
// 先把左右两半部分排好序
process(nums, l, m);
process(nums, m+1, r); // 是 m + 1 不是 m
// 左右两半部分都已排好序，最后merge在一起
merge(nums, l, m, r);
}
int mergeSort(vector<int>& nums){
process(nums, 0, nums.size() - 1);
}
/*
计算mergeSort时间复杂度：master公式
a = 2 ,b = 2, d = 1
log(b,a) == d : T(N) = O((N ^ d) * logN) = O(N*logN)
*/为什么选择、冒泡、插入排序时间复杂度为O(N^2)，归并排序为O(N*logN):
因为它们浪费了许多比较行为，以选择排序为例：
第一次在0~N-1范围比较，只搞定了一个数
第二次在1~N-1范围比较，只搞定了一个数
第三次在2~N-1范围比较，只搞定了一个数。。。
每次比较都是独立的，第一次比较的结果不会用到第二次比较中去
而归并排序没有浪费比较行为：
归并排序每次比较的信息留下来了，每次比较得到一个有序的部分
这个有序的部分会在下次比较里与另一个有序部分merge出一个更大有序部分
每次比较后的信息是一层层往下传递的
小和问题
在一个数组中，每一个数的左边比当前数小的所有数累加起来，叫做这个数组的小和。求一个数组的小和。
例子：[1,3,4,2,5]
1左边比1小的数，没有
3左边比3小的数，1
4左边比4小的数，1,3
2左边比2小的数，1
5左边比5小的数，1,3,4,2
所以小和为1+1+3+1+1+3+4+2=16
使用归并排序，边排序边求小和。
与归并排序唯一的不同是：
只有在左边与右边相等时把右边的数移到help数组
即只有左边数比右边小时才把左边数记到help数组，同时计算小和(因为此时左边数比所有右边数都小)
int merge(vector<int>& nums, int l, int m, int r){
vector<int> help(r - l + 1, 0);
int i = 0;
int p1 = l;
int p2 = m + 1;
int res = 0;
while(p1 <= m && p2 <= r){
/*
找左边数小于右边数，找到则左边数小于右边数及右边数以右所有数
左右边数相等时让右边数右移增大，因为我们找的是左边数小于右边数
也只有这样，右边数以右的所有数大于左边数的事实才能被检测到
*/
res += nums[p1] < nums[p2] ? nums[p1] * (r - p2 + 1) : 0;
help[i++] = nums[p1] < nums[p2] ? nums[p1++] : nums[p2++];
}
while(p1 <= m){
help[i++] = nums[p1++];
}
while(p2 <= r){
help[i++] = nums[p2++];
}
for(i = 0; i < help.size(); i++){
nums[l + i] = help[i];
}
return res;
}
int process(vector<int>& nums, int l,int r){
if(l == r){
return 0;
}
int m = l + ((r - l) >> 1);
return process(nums, l, m) + process(nums, m+1, r) + merge(nums, l, m, r);
}
int smallSum(vector<int>& nums){
if(nums.empty() || nums.size() < 2){
return 0;
}
return process(nums, 0, nums.size() - 1);
}逆序对问题
在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有的逆序对。
边排序边检测：
小和问题是左边的数比右边所有数小，则。。。
逆序对问题是左边的数比右边的数大，则。。。
int merge(vector<int>& nums, int l, int m, int r){
vector<int> help(r - l + 1, 0);
int i = 0;
int p1 = l;
int p2 = m + 1;
int res = 0;
while(p1 <= m && p2 <= r){
/*
左边数比右边数大，则左边数及左边数以右所有数都大于右边数
因为要找左边数大于右边数，所以左右边数相等时左边数右移增大
只有这样，左边数以右所有数大于右边数这一事实才能被检测到
*/
res += nums[p1] > nums[p2] ? (m - p1 + 1) : 0;
help[i++] = nums[p1] <= nums[p2] ? nums[p1++] : nums[p2++];
}
while(p1 <= m){
help[i++] = nums[p1++];
}
while(p2 <= r){
help[i++] = nums[p2++];
}
for(i = 0; i < help.size(); i++){
nums[l + i] = help[i];
}
return res;
}
int process(vector<int>& nums, int l,int r){
if(l == r){
return 0;
}
int m = l + ((r - l) >> 1);
return process(nums, l, m) + process(nums, m+1, r) + merge(nums, l, m, r);
}
int inversePair(vector<int>& nums){
if(nums.empty() || nums.size() < 2){
return 0;
}
return process(nums, 0, nums.size() - 1);
}荷兰国旗问题
给定一个数组arr和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于数组的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)
维护一个 < 区域右边界指针和 > 区域左边界指针
初始边界分别在数组首元素左边和最后一个元素右边
从左到右遍历arr[i]：
1）arr[i] < num : arr[i]和 < 区域下一个元素交换，<区域右扩，i++
2）arr[i] == num ：i++
3）arr[i] > num ：arr[i]和 > 区域前一个元素交换，i原地不动
当i和有边界重合，算法结束
void swap(vector<int>& nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
void flag(vector<int>& nums, int value){
int less = -1;
int more = nums.size();
int i = 0;
while(i < more){
if(nums[i] < value){
swap(nums, i++, ++less);
}
else if(nums[i] == value){
i++;
}
else{
swap(nums, i, --more);
}
}
}快速排序
随机选一个数放在数组最后作划分，把前面的数组划分为小于等于大于划分值的三部分，再对大于和小于部分作上述操作，递归
时间复杂度O(N*logN)
注:最坏状况复杂度O(N2),但这种情况并不常见
划分数有N种可能，对应数组中N个元素
N种情况等概率，都为1/N
N种情况下时间复杂度不同
对这N种情况下时间复杂度取数学期望:O(N*logN)
快速排序通常比其他O(N*logN)算法更有效率
void swap(vector<int>& nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
pair<int, int> partition(vector<int>& nums, int l, int r){
// less:小于区域最右一个元素 more:大于区域最左一个元素
int less = l - 1;
int more = r;
int i = l;
while(i < more){
if(nums[i] < nums[r]){
swap(nums, i++, ++less);
}
else if(nums[i] == nums[r]){
i++;
}
else{
swap(nums, i, --more);
}
}
swap(nums, more, r);
return pair<int, int>{less + 1, more};
}
void quickSort(vector<int>& nums, int l, int r){
if(l < r){
swap(nums, r, l + (rand() % (r - l + 1)));
// #include <utility>
pair<int, int> p = partition(nums, l, r);
quickSort(nums, l, p.first - 1);
quickSort(nums, p.second + 1, r);
}
}