master公式 归并排序 小和问题 逆序对问题 荷兰国旗问题 快排

递归行为时间复杂度计算：master公式

T(N) = a * T(N/b) + O(N^d)

N：母问题规模

a：子问题计算次数

N/b：子问题规模

O(N^d)：每次递归除子问题外其他操作时间复杂度

1）log(b,a) > d  :  T(N) = O(N^log(b,a)) 

2）log(b,a) < d  :  T(N) = O(N^d) 

3）log(b,a) == d  :  T(N) = O(N^d * 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(N²),但这种情况并不常见

划分数有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);
    }
}