文章目录
时间线前言定义一图流逻辑
分类自顶向下自底向上
时间复杂度实现自底向上Python
自顶向下Python
思考
时间线
2020年7月3日——完成初稿 2020年7月4日——修改几个错别字
前言
归并排序可以说是分治法和递归的一个典型运用，而且归并排序的思想也是和分治法所契合的。
例如在分治法的思想上，
一个集合有多个对象，使用其它的排序，那么就需要对这个集合进行排序，工作区是在这个集合中
而归并排序是将这个集合拆分成若干个集合，而拆分规则是，将每一个对象单独放置在一个集合中，
那么这个集合就是有序的，然后不断地合并。这就是归并排序
定义
一图流
由于二路归并排序是归并排序的一个经典例子，所以这里描述了二路归并排序
逻辑
归并排序其实就是利用有规矩的归并的过程实现的。
首先，将包含k个对象的集合拆分城k个子集合，然后不断进行有规矩地合并：
将两个子集合的第一个对象进行比较，符合排序规则的(升序-小的，降序-大的)对象存入一个新集合中
当两个子集合都为空时，即两个子集合完成了有规矩地合并，而这个新集合是有序的。
当这个新集合的长度为k时，整个集合的排序工作也完成了。
分类
归并排序有两类，自顶向下和自底向上。两者的区别在于如何分解的。
自顶向下
自顶向下的分解是将含有k个对象的集合逐层分解，k->k//2…
自底向上
自底向上的分解是直接将含有k个对象的集合分成k个含有1个对象的子集合
时间复杂度
假设排序n个对象的时间复杂度是T(n)
T
n
=
{
1
i
f
n
=
1
2
T
(
n
/
2
)
i
f
n
>
1
最
终
：
T
n
=
0
(
n
l
o
g
n
)
Tn=\begin{cases} 1&if&n = 1\\ 2T(n/2)&if&n > 1 \end{cases}\\ 最终：Tn=0(nlogn)
Tn={12T(n/2)ififn=1n>1最终：Tn=0(nlogn)
实现
自底向上
Python
""" 自底向上 """
def merge_sort(worklist
):
for i
in range(len(worklist
)):
worklist
.append
([worklist
.pop
(0)])
"""
悟：做什么操作的时候，要考虑到这个操作的前提是什么，
然后应该考虑：
如果没有前提，那代表着什么，应该如何处理
如果有这个前提，那操作之后的结果会是什么
以上逻辑可以逆推导
例如：下面
->需要merge_list获取两个对象列表
->前提就是worklist有两个参数，就是worklist的长度大于1
->如果没有这个前提，那么，worklist只有1个对象
就带着算法已经执行完成，就是结果了(所有的分解对象合并到一个对象中)
"""
while len(worklist
) > 1:
worklist
.append
(merge_list
(worklist
.pop
(0),worklist
.pop
(0)))
return worklist
[0]
def merge_list(a
,b
):
result
= []
while len(a
) > 0 and len(b
) > 0:
if a
[0] > b
[0]:
result
.append
(b
.pop
(0))
else:
result
.append
(a
.pop
(0))
while len(a
) > 0:
result
.append
(a
.pop
(0))
while len(b
) > 0:
result
.append
(b
.pop
(0))
return result
自顶向下
Python
""" 自顶向下 """
def merge_sort(worklist
):
if len(worklist
) <= 1:
return worklist
else:
mid
= len(worklist
)//2
left
= merge_sort
(worklist
[:mid
])
right
= merge_sort
(worklist
[mid
:])
result
= merge_List
(left
,right
)
return result
def merge_List(a
,b
):
"""合并两个列表
arg1:list1
arg2:list2
注意：这里的处理的对象的长度是越来越长的
从长度为1，逐渐增加
还有，处理的对象都是有顺序的或者长度为1的
"""
result
= []
""" 如果两个列表都不为空 """
while len(a
) != 0 and len(b
) != 0:
if a
[0] < b
[0]:
result
.append
(a
.pop
(0))
else:
result
.append
(b
.pop
(0))
""" 上面的while保证：
一旦有一个列表为空，就马上停止
而且每一次操作，都是针对一个列表
所以：两个列表不可能都为空
"""
if len(a
) != 0 :
result
.extend
(merge_sort
(a
))
else:
result
.extend
(merge_sort
(b
))
return result
思考
归并排序是分治法的一种体现
无论自顶向下还是自底向上的归并排序，其实都有分治法的影子，区别在于如何分解
分解：将一个集合分解成子集合
求解：对子集合进行排序，即将子集合变成有序集合
组合：将有序的子集合合并
不断地重复求解和组合，最终得到有序的集合对象
