归并排序算法的实现

待证问题: tmp 保存的是 q[l…mid] , q[mid+1…r] 中从小到大排序的所有数
证明(第一个 while 循环)
循环不变式: tmp[0…k-1] 保存上述俩数组中从小到大排序的最小 k 个数

初始

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

保持

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

若 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个数

终止

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

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

为什么 用 mid 作为分隔线时不会造成无限划分呢

因为此时 mid 是向下取整的, merge_sort(q, l, mid ) 中的 mid 一定不会取到 r 值

∴ merge_sort(q, l, mid ) 不会无限划分

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

主要有三种:

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

聚合分析归并排序的时间复杂度
归并排序属于分治法, 很容易写出递归式:

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

1.直观

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

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

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

一共有 n 个元素, 所以摊还总代价为 n, 算法的时间复杂度为 O(n)O(n)
摊还代价, 我们自己设定的一个理想代价, 只有一个要求: 总的摊还代价大于总的实际代价, 所以总摊还代价是总实际代价的上界

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

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

得到 f(n)=O(n)f(n)=O(n) 后, 根据递推式的计算方法(代入法, 递归树法, 主方法)容易计算出 T(n)=O(nlogn)T(n)=O(nlog⁡n), 即归并排序的时间复杂度为 O(nlogn)O(nlog⁡n)
总结归并思路
有数组 q, 左端点 l, 右端点 r

确定划分边界 mid

递归处理子问题 q[l…mid], q[mid+1…r]

合并子问题

主体合并

至少有一个小数组添加到 tmp 数组中

收尾

可能存在的剩下的一个小数组的尾部直接添加到 tmp 数组中

复制回来

tmp 数组覆盖原数组

代码实现:

#include 

using namespace std;

const int N = 1e5 + 10;

int a[N], tmp[N];

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;
    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 (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    merge_sort(a, 0, n - 1);

    for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);

    return 0;
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/39790/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43