- 归并排序动态图如下：
- 归并排序的思路就是分治的思想，具体思路如下：
1、将一串数分为两部分，对两部分分别排序，然后将两部分已经有序的数再合到一起
2、对1中分成的每一部分，递归的进行上述1的操作
具体代码实现如下：
def merge_sort(datas):
if len(datas)<=1:
return datas
mid=len(datas)//2
left=merge_sort(datas[:mid])
right=merge_sort(datas[mid:])
return merge(left,right)
def merge(left,right):
datas=[]
i=0
j=0
while i<len(left) and j < len(right):
if left[i]<right[j]:
datas.append(left[i])
i+=1
else:
datas.append(right[j])
j+=1
if i<len(left):
for index in range(i,len(left)):
datas.append(left[index])
if j<len(right):
for index in range(j,len(right)):
datas.append(right[index])
print("-----------------------------------------------------------------------------------")
print("left:",left)
print("right:",right)
print("datas:",datas)
print("-----------------------------------------------------------------------------------")
return datas
if __name__=="__main__":
datas=[10,9,8,7,6,5,4,3,2,1,0]
datas=merge_sort(datas)
print("经过归并排序后结果：", datas)
执行结果如下：
----------------------------------------------------------------------------------
left: [10]
right: [9]
datas: [9, 10]
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
left: [7]
right: [6]
datas: [6, 7]
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
left: [8]
right: [6, 7]
datas: [6, 7, 8]
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
left: [9, 10]
right: [6, 7, 8]
datas: [6, 7, 8, 9, 10]
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
left: [4]
right: [3]
datas: [3, 4]
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
left: [5]
right: [3, 4]
datas: [3, 4, 5]
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
left: [1]
right: [0]
datas: [0, 1]
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
left: [2]
right: [0, 1]
datas: [0, 1, 2]
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
left: [3, 4, 5]
right: [0, 1, 2]
datas: [0, 1, 2, 3, 4, 5]
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
left: [6, 7, 8, 9, 10]
right: [0, 1, 2, 3, 4, 5]
datas: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
-----------------------------------------------------------------------------------
经过归并排序后结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
最好的情况下
def merge_sort(datas):
if len(datas)<=1:
return datas
mid=len(datas)//2
left=merge_sort(datas[:mid])
right=merge_sort(datas[mid:])
return merge(left,right)
def merge(left,right):
datas=[]
i=0
j=0
while i<len(left) and j < len(right):
if left[i]<right[j]:
datas.append(left[i])
i+=1
else:
datas.append(right[j])
j+=1
if i<len(left):
for index in range(i,len(left)):
datas.append(left[index])
if j<len(right):
for index in range(j,len(right)):
datas.append(right[index])
print("-----------------------------------------------------------------------------------")
print("left:",left)
print("right:",right)
print("datas:",datas)
print("-----------------------------------------------------------------------------------")
return datas
if __name__=="__main__":
datas = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
datas = merge_sort(datas)
print("经过归并排序后结果：", datas)
执行结果如下：
-----------------------------------------------------------------------------------
left: [0]
right: [1]
datas: [0, 1]
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
left: [3]
right: [4]
datas: [3, 4]
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
left: [2]
right: [3, 4]
datas: [2, 3, 4]
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
left: [0, 1]
right: [2, 3, 4]
datas: [0, 1, 2, 3, 4]
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
left: [6]
right: [7]
datas: [6, 7]
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
left: [5]
right: [6, 7]
datas: [5, 6, 7]
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
left: [9]
right: [10]
datas: [9, 10]
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
left: [8]
right: [9, 10]
datas: [8, 9, 10]
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
left: [5, 6, 7]
right: [8, 9, 10]
datas: [5, 6, 7, 8, 9, 10]
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
left: [0, 1, 2, 3, 4]
right: [5, 6, 7, 8, 9, 10]
datas: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
-----------------------------------------------------------------------------------
经过归并排序后结果： [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 
