归并排序算法思路
归并排序主要思想是分治法(divide and conquer),就是要将n个元素的序列划分为两个序列,再将两个序列划分为4个序列,
直到每个序列只有一个元素,最后,再将两个有序序列归并成一个有序的序列。
两个序列要归并成一个有序的序列,我们每次从两个列表开头元素选取较小的一个,直到某一个列表到达底部,再将另一个剩下部分顺序取出。添加到第一个队列后面
算法实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
# Filename : lean001.py # author by : www.py40.com #python归并排序算法 def mergeSort(seq): if len(seq)<=1: return seq mid=int(len(seq)/2) left=mergesort(seq[:mid]) right=mergesort(seq[mid:]) return merge(left,right) def merge(left,right): result=[] i,j=0,0 while i<len(left) and j<len(right): if left[i]<=right[j]: result.append(left[i]) i+=1 else: result.append(right[j]) j+=1 result+=left[i:] result+=right[j:] return result a = [1,15,12,3,56,42,1,44,32,25,6,7,32] a = mergeSort(a) print("result:"+str(a)) |
运行结果
1 2 |
C:\Users\Administrator>E:\python\learn\lean001.py result:[1, 1, 3, 6, 7, 12, 15, 25, 32, 32, 42, 44, 56] |
未经允许不得转载:Python在线学习 » Python-归并排序