归并排序学习笔记
代码
先上伪代码:
1 | def MERGE(A, p, q, r): |
再来Python:
1 | import math |
算法分析
归并排序顾名思义,就是把两个数列合并成一个,其中MERGE()
函数就是这个作用。
MERGE()
函数解析
行数 | 作用 |
---|---|
参数 | A 指待排序数列,p 指数列最小下标,q 指数列中间下标,r 指数列最大下标 |
1~2 |
p~n1 指的是对半分后靠左的子序列,同样的,n2~q 指的是靠右的子序列 |
3 |
新建靠左的子序列和靠右的子序列 |
4~7 |
把A[p..n1] 与A[n2~r] 复制到L[] 和R[] |
8~9 |
把L[] 和R[] 的最后一个数设为正无穷,方便比较 |
10~11 |
略 |
12 |
进入一层循环,用于归并数列 |
13~18 |
比较L[i] 和R[j] ,把比较小的先放入数列 |
MERGE_SORT()
函数解析
行数 | 作用 |
---|---|
1 |
如果p < r 为真,则代表数列存在 |
2 |
确定q ,也就是数列中间下标 |
3~4 |
如果还能分,则继续分,不能的话,就是第7 行的事了 |
5 |
归并 |
6 |
略 |
7 |
如果数列没了,返回,进行归并 |
时间复杂度
归并排序的时间复杂度为:
$$ \theta(N \log N) $$
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.