归并模板
归并属于分治算法,有三个步骤
- 分成子问题
- 递归处理子问题
- 合并子问题
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
个数
边界分析
什么不用 mid - 1
作为分隔线呢
即 merge_sort(q, l, mid - 1 ), merge_sort(q, mid, r)
因为 mid = l + r >> 1
是向下取整,mid
有可能取到 l
(数组只有两个数时),造成无限划分
解决办法: 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];
}
不过最好不要这样写,很奇葩,不对称
为什么 用 mid 作为分隔线时不会造成无限划分呢?
因为此时 mid
是向下取整的, merge_sort(q, l, mid )
中的 mid
一定不会取到 r
值
∴ merge_sort(q, l, mid )
不会无限划分
摊还分析
摊还分析是一种分析时间复杂度的方法
主要有三种:
- 聚合分析(记账法)
- 核方法
- 势能法
聚合分析(记账法)最符合直观感觉,
聚合分析归并排序的时间复杂度
归并排序属于分治法, 很容易写出递归式:$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)$
作者:醉生梦死
链接:https://www.acwing.com/solution/content/16778/
来源:AcWing