归并排序算法。
归并排序法
归并排序算法,原理容易理解。但是到代码实现以及单步调试的时候,不是很明白了。
nlogn
当计算的值越大时,所需要的时间的比较。
把一个数组分成块,然后再进行分块,最后分成了一个一个的,然后再向上归并。
1 2 3 4 5 6 7 8
2 3 6 8 1 4 5 7
6 8 2 3 1 5 4 7
8 6 2 3 1 5 7 4
二分法,递归的方法
时间效率比空间效率重要。
两个已经排好序的元素数组,来比较数组头部的元素,谁更小,就放到头部。
i和j要比较的元素,k要放的位置,归并结束要放的最后一个元素的位置。
来自维基百科的图片讲解
拆分排序和合并排序
拆分
>>> a = range(1,10)
>>> a
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> len(a)
9
>>> mid = len(a) / 2
>>> mid
4
>>> a[:mid]
[1, 2, 3, 4]
>>> a[mid:]
[5, 6, 7, 8, 9]
拆分两部分之后,还需要继续拆分,直到不能再分为止。
#递归拆分
def split(lists):
#递归退出条件
length = len(lists) #长度
if length <= 1:
return lists
#取中间值
mid = length // 2
left = lists[:mid]
right = lists[mid:]
#递归拆分
split(left)
split(right)
if __name__ == '__main__':
a = [3]
print split(a)
除了列表结果为1的时候,会返回结果,其他时候都返回None
。拆分之后没有做后续处理,需要将拆分的列表合并和排序。
每次排序都是基于上次合并排序的结果。按照顺序抽取两个list的元素判断大小,并添加到新的列表中,完成合并排序的步骤。
def merge(left,right):
i = 0
j = 0
result = []
length_left = len(left)
length_right = len(right)
while i < length_left and j < length_right:
#逐个比较两个列表的元素
#小的添加到列表,大的留下继续比较
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j +=1
#最后加上未比较的元素
result.extend(left[i:])
result.extend(right[j:])
return result
最终的代码:参考写出的。
# -*- coding:utf-8 -*-
def split(lists):
#递归退出条件判断
length = len(lists)
if length <= 1:
return lists
#取整
mid = length // 2
left = lists[:mid]
right = lists[mid:]
#递归拆分
split(left)
split(right)
return merge(left,right)
def merge(left,right):
i = 0
j = 0
result = []
length_left = len(left)
length_right = len(right)
while i < length_left and j < length_right:
#逐个比较两个列表的元素
#小的添加到列表,大的留下继续比较
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j +=1
#最后加上未比较的元素
result.extend(left[i:])
result.extend(right[j:])
return result
def merge_sort(lists):
#递归退出条件判断
length = len(lists)
if length <= 1:
return lists
#递归拆分,取整
mid = length // 2
left = merge_sort(lists[:mid])
right = merge_sort(lists[mid:])
#合并排序
return merge(left,right)
if __name__ == '__main__':
a = [6,7,8,5,4,3,2,9,10,1]
print '排序前',a
print '排序后',merge_sort(a)
运行。
C:\Users\Administrator\Desktop\Algo>python2 spitsort1.py
排序前 [6, 7, 8, 5, 4, 3, 2, 9, 10, 1]
排序后 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
合并和排序
# -*- coding:utf-8 -*-
def merge1(left,right):
i = 0
j = 0
result = []
length_left = len(left)
length_right = len(right)
while i < length_left and j < length_right:
#逐个比较两个列表的元素
#小的添加到新的列表,大的留下继续排序
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
#最后加上未比较的元素
result.extend(left[i:])
result.extend(right[j:])
return result
if __name__ == '__main__':
a = [6,7,8,5,4]
b = [3,2,9,10,1]
print merge1(a,b)
结果
C:\Users\Administrator\Desktop\Algo>python2 merge.py
[3, 2, 6, 7, 8, 5, 4, 9, 10, 1]
把上面的函数简单合并一下。
# -*- coding:utf-8 -*-
def merge(left,right):
#合并和排序
i = 0
j = 0
result = []
length_left = len(left)
length_right = len(right)
while i < length_left and j < length_right:
#逐个比较两个列表的元素
#小的添加进新的列表,大的留下继续比较
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
#最后加上未比较的元素
result.extend(left[i:])
result.extend(right[j:])
return result
def merge_sort(lists):
#递归退出条件判断
length = len(lists)
if length <= 1:
return lists
#递归拆分,取整
mid = length // 2
left = merge_sort(lists[:mid])
right = merge_sort(lists[mid:])
#归并排序
return merge(left,right)
if __name__ == '__main__':
a = [6,7,8,5,4,3,2,9,10,1]
print '排序前',a
print '排序后',merge_sort(a)
结果
C:\Users\Administrator\Desktop\Algo>python2 splitsort2.py
排序前 [6, 7, 8, 5, 4, 3, 2, 9, 10, 1]
排序后 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]