Python——关于排序算法（合并排序法）
接前面两篇，今天继续讲合并排序法。
合并排序法（merge sort）
先来看一下百度百科的定义：
合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。合并排序也叫归并排序。 百度百科
合并排序法有一定难度，我们先从后半部分的conquer说起吧，
如果有2个已经排好序的列表a = [3，5，6，9]和b = [2，4，7，8],以及目标c = []
用合并排序法操作：
第一轮：
取a和b中( [3，5，6，9]和[2，4，7，8])首位数字，最小值2存入c第一个位置：
c = [2,]
第二轮：
取a和b中余下部分数字( [3，5，6，9]和[4，7，8])的首位数字，最小值3存入c的第二个位置：
c = [2，3，]
第三轮：
取a和b中余下部分数字( [5，6，9]和[4，7，8])的首位数字，最小值4存入c的第三个位置：
c = [2，3，4]
第四轮：
取a和b中余下部分数字( [5，6，9]和[7，8])的首位数字，最小值5存入c的第四个位置：
c = [2，3，4，5]
第五轮：
取a和b中余下部分数字( [6，9]和[7，8])的首位数字，最小值6存入c的第五个位置：
c = [2，3，4，5，6]
第六轮：
取a和b中余下部分数字( [9]和[7，8])的首位数字，最小值7存入c的第六个位置：
c = [2，3，4，5，6，7]
第七轮：
取a和b中余下部分数字( [9]和[8])的首位数字，最小值8存入c的第七个位置：
c = [2，3，4，5，6，7，8]
第八轮：
取a（或b）中余下部分数字 [9]，全部存入c后面的位置：
c = [2，3，4，5，6，7，8，9]
排序完成。
coding
#!/usr/bin/env python3.6
# -*- coding: utf-8 -*-
# @Time : 2019-03-27 19:43
# @Author : Ed Frey
# @File : merge_sort.py
# @Software: PyCharm
from time import clock
def timer(f):
def _f(*args):
t0 = clock()
f(*args)
return clock() - t0
return _f
def _merge(num1:list,num2:list):
num = []
i = 0
j = 0
while i < len(num1) and j < len(num2):
if num1[i] <= num2[j]:
num.append(num1[i])
i += 1
else:
num.append(num2[j])
j += 1
print(num)
while i < len(num1):
num.append(num1[i])
i += 1
print(num)
while j < len(num2):
num.append(num2[j])
j += 1
print(num)
return num
if __name__ == '__main__':
num1 = [3,5,6,9]
num2 = [2,4,7,8]
time = timer(_merge)(num1,num2)
print(time)运行结果如下：
[2]
[2, 3]
[2, 3, 4]
[2, 3, 4, 5]
[2, 3, 4, 5, 6]
[2, 3, 4, 5, 6, 7]
[2, 3, 4, 5, 6, 7, 8]
[2, 3, 4, 5, 6, 7, 8, 9]
6.699999999998374e-05
运行时间感觉比前面讲的冒泡法、选择排序法、插入排序法略久一点点，其实不然，可能是因为print多了几个吧。而且，随着n的增大，这个时间上的优势会不断扩大。
前方高能，追加一个_merge_sorted函数需要好好? 这个函数是用的递归方法，对递归陌生的童鞋需要慢慢领会一下了。
#!/usr/bin/env python3.6
# -*- coding: utf-8 -*-
# @Time : 2019-03-27 19:43
# @Author : Ed Frey
# @File : merge_sort.py
# @Software: PyCharm
from time import clock
def timer(f):
def _f(*args):
t0 = clock()
f(*args)
return clock() - t0
return _f
def _merge(num1:list,num2:list):
num = []
i = 0
j = 0
while i < len(num1) and j < len(num2):
if num1[i] <= num2[j]:
num.append(num1[i])
i += 1
else:
num.append(num2[j])
j += 1
while i < len(num1):
num.append(num1[i])
i += 1
while j < len(num2):
num.append(num2[j])
j += 1
print(num)
return num
def _merge_sorted(num:list):
if len(num) <= 1:
return num
m = len(num)//2
a = _merge_sorted(num[:m])
b = _merge_sorted(num[m:])
return _merge(a,b)
if __name__ == '__main__':
num = [9,8,5,6,2,4,7,3]
time = timer(_merge_sorted)(num)
print(time)
运行结果：[8, 9]
[5, 6]
[5, 6, 8, 9]
[2, 4]
[3, 7]
[2, 3, 4, 7]
[2, 3, 4, 5, 6, 7, 8, 9]
0.00013299999999993872
运行时间还是先忽略哈，感兴趣的童鞋，可以用这四节的函数，分别测试几十位、上百位数字的排序，快慢一目了然哈。
从运行结果再反向分析一下合并排序法的思路，把
[9,8,5,6,2,4,7,3]拆分成[9,8,5,6][2,4,7,3],len大于1就一直拆分————>分支1:[9,8,5,6]————>[9,8][5,6]————>[9][8][5][6]然后开始合并————>[8,9][5,6]————>[5,6,8,9]分支2:[2,4,7,3]————>[2,4][7,3]————>[2][4][7][3],然后开始合并————>[2,4][3,7]————>[2,3,4,7]接下来是最后的合并：[2, 3, 4, 5, 6, 7, 8, 9]小结合并排序法总的平均时间复杂度为O(N*logN)。解释起来可能会有点绕，那我直接引用前几天的《Python——关于算法与数据结构》中的一个猜数字游戏的例子：
“当要猜的数字范围不断变大，比如猜100万以内的数字，折中取数字猜，最多只需要20次即可（2的10次方是1024,20次方刚好100万多一点）”
这里的20其实就是100万取对数得来的，合并排序，首选是要divide，自然是用猜数字的方法来分组。分组完再反回头来合并，合并就是上面例子中的取最小值不断存入c的过程，时间复杂度为O（N）。一分一合，就出来这么个结果：O(N*logN）。
怎么样，晕了木有？反正我觉得，写的都有点晕乎啦～
如有疑惑，欢迎留言探讨哦～～