归并模板

归并属于分治算法，有三个步骤

1. 分成子问题
2. 递归处理子问题
3. 合并子问题

void merge_sort(int q[], int l, int r)
{
    //递归的终止情况
    if(l >= r) return;

    //第一步：分成子问题
    int mid = l + r >> 1;

    //第二步：递归处理子问题
    merge_sort(q, l, mid ), merge_sort(q, mid + 1, r);

    //第三步：合并子问题
    int k = 0, i = l, j = mid + 1, tmp[r - l + 1];
    while(i <= mid && j <= r)
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];

    for(k = 0, i = l; i <= r; k++, i++) q[i] = tmp[k];
}

待证问题:tmp 保存的是 q[l..mid] , q[mid+1..r] 中从小到大排序的所有数
证明(第一个 while 循环)

循环不变式: tmp[0..k-1] 保存上述俩数组中从小到大排序的最小 k 个数

1.初始

k = 0, tmp[0..k-1] 为空，显然成立

2.保持

假设某轮循环开始之前，循环不变式成立

若 q[i] <= q[j], 则 tmp[k] = q[i]

其中, q[i] <= q[i+1..mid], q[i] <= q[j] <= q[j+1..r]

∴ q[i] 是剩下的所有数中最小的一个

当 q[i] > q[j] 时，同理可以得到 tmp[k] = q[j] 是剩下数中最小的一个

∴ tmp[k] 是剩下数中最小的一个

∴ k自增之后，下轮循环开始之前，tmp[0..k-1]保存从小到大排序的最小k个数

3.终止

i > mid 或 j > r

则 q[l..mid] 和 q[mid+1..r] 其中一个数组的数都已遍历

tmp[0..k-1]保存从小到大排序的最小k个数

边界分析

即 merge_sort(q, l, mid - 1 ), merge_sort(q, mid, r)

解决办法: mid 向上取整就可以了, 即 mid = l + r + 1 >> 1,如下所示:

void merge_sort(int q[], int l, int r)
{
    if(l >= r) return;

    int mid = l + r + 1>> 1;//注意mid是向上取整
    merge_sort(q, l, mid - 1 ), merge_sort(q, mid, r);

    int k = 0, i = l, j = mid, tmp[r - l + 1];
    while(i < mid && j <= r)
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    while(i < mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];

    for(k = 0, i = l; i <= r; k++, i++) q[i] = tmp[k];

}

不过最好不要这样写,很奇葩,不对称

摊还分析

摊还分析是一种分析时间复杂度的方法

主要有三种:

• 聚合分析(记账法)
• 核方法
• 势能法

聚合分析(记账法)最符合直观感觉,

聚合分析归并排序的时间复杂度

归并排序属于分治法, 很容易写出递归式:$T(n)=2T(n/2)+f(n)$

其中, $2T(n/2)$ 是子问题的时间复杂度, $f(n)$ 是合并子问题的时间复杂度

1.直观

直观上我们感觉 f(n)=O(n), 事实也正是如何, 因为每次 while 都会把一个元素添加到数组中, 一共有 n 个元素, 所以 while 循环的次数为 n , 时间复杂度为 O(n)

2.摊还分析的聚合分析

对于每次迭代中选出并添加到数组中的元素, 我们给它的摊还代价设为 1(记账为 1)

一个元素只能计费一次, 因为马上就被添加到数组中了

一共有 n 个元素, 所以摊还总代价为 n, 算法的时间复杂度为 $O(n)$

摊还代价, 我们自己设定的一个理想代价, 只有一个要求: 总的摊还代价大于总的实际代价, 所以总摊还代价是总实际代价的上界

实际代价, 实际操作的代价

3.计算归并排序的递归式

得到 $f(n)=O(n)$ 后, 根据递推式的计算方法(代入法, 递归树法, 主方法)容易计算出 $T(n)=O(nlogn)$, 即归并排序的时间复杂度为 $O(nlogn)$