接前面两篇,今天继续讲合并排序法。
合并排序法(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)。
怎么样,晕了木有?反正我觉得,写的都有点晕乎啦~
如有疑惑,欢迎留言探讨哦~~