一、归并排序基本思想
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
分而治之
分解：将列表越分越小，直至分成一个元素。
一个元素是有序的。
合并：将两个有序列表归并，列表越来越大。
可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。
二、合并相邻有序子序列过程
三、归并排序代码
1、一次归并代码
def merge(li, low, mid, high):
i = low
j = mid + 1
ltmp = []
while i <= mid and j <= high:
if li[i] <= li[j]:
ltmp.append(li[i])
i += 1
else:
ltmp.append(li[j])
j += 1
while i <= mid:
ltmp.append(li[i])
i += 1
while j <= high:
ltmp.append(li[j])
j += 1
li[low:high + 1] = ltmp
2、归并排序
def _merge_sort(li，low，high)： if low < high：#至少两个元素 mid = (low + high) // 2 _merge_sort(li，low，mid) _merge_sort(li,mid+1,high) #merage(li,low,mid,high) print(li[low:high+1])
四、归并排序过程打印
1、归并排序归并过程
1、归并排序之归并
1、实现代码
def merge(li, low, mid, high):
i = low
j = mid + 1
ltmp = []
while i<=mid and j<=high: # 只要左右两边都有数
if li[i] < li[j]:
ltmp.append(li[i])
i += 1
else:
ltmp.append(li[j])
j += 1
# while执行完，肯定有一部分没数了
while i <= mid:
ltmp.append(li[i])
i += 1
while j <= high:
ltmp.append(li[j])
j += 1
li[low:high+1] = ltmp
li = [2,4,5,7,1,3,6,8]
merge(li, 0, 3, 7)
print(li)
2、测试结果
[1, 2, 3, 4, 5, 6, 7, 8]
2、一次的完整归并
1、实现代码
def merge(li, low, mid, high):
i = low
j = mid + 1
ltmp = []
while i<=mid and j<=high: # 只要左右两边都有数
if li[i] < li[j]:
ltmp.append(li[i])
i += 1
else:
ltmp.append(li[j])
j += 1
# while执行完，肯定有一部分没数了
while i <= mid:
ltmp.append(li[i])
i += 1
while j <= high:
ltmp.append(li[j])
j += 1
li[low:high+1] = ltmp
# li = [2,4,5,7,1,3,6,8]
# merge(li, 0, 3, 7)
# print(li)
def merge_sort(li, low, high):
if low < high: #至少有两个元素，递归
mid = (low + high) //2
merge_sort(li, low, mid)
merge_sort(li, mid+1, high)
merge(li, low, mid, high)
li = list(range(20))
import random
random.shuffle(li)
print(li)
merge_sort(li, 0, len(li)-1)
print(li)
2、测试结果
[1, 9, 10, 4, 0, 11, 18, 5, 7, 8, 17, 15, 19, 2, 14, 16, 6, 12, 13, 3] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
2、打印归并过程
1、实现代码
def merge(li, low, mid, high):
i = low
j = mid + 1
ltmp = []
while i<=mid and j<=high: # 只要左右两边都有数
if li[i] < li[j]:
ltmp.append(li[i])
i += 1
else:
ltmp.append(li[j])
j += 1
# while执行完，肯定有一部分没数了
while i <= mid:
ltmp.append(li[i])
i += 1
while j <= high:
ltmp.append(li[j])
j += 1
li[low:high+1] = ltmp
def merge_sort(li, low, high):
if low < high: #至少有两个元素，递归
mid = (low + high) //2
merge_sort(li, low, mid)
merge_sort(li, mid+1, high)
merge(li, low, mid, high)
print(li[low:high+1])
li = list(range(10))
import random
random.shuffle(li)
print(li)
merge_sort(li, 0, len(li)-1)
print(li)
2、range(20)测试结果
[10, 6, 4, 18, 0, 12, 5, 15, 14, 17, 7, 8, 11, 13, 2, 1, 19, 3, 9, 16] [6, 10] [4, 6, 10] [0, 18] [0, 4, 6, 10, 18] [5, 12] [5, 12, 15] [14, 17] [5, 12, 14, 15, 17] [0, 4, 5, 6, 10, 12, 14, 15, 17, 18] [7, 8] [7, 8, 11] [2, 13] [2, 7, 8, 11, 13] [1, 19] [1, 3, 19] [9, 16] [1, 3, 9, 16, 19] [1, 2, 3, 7, 8, 9, 11, 13, 16, 19] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
3、range(10)测试结果
[3, 1, 9, 5, 8, 7, 6, 4, 0, 2] [1, 3] [1, 3, 9] [5, 8] [1, 3, 5, 8, 9] [6, 7] [4, 6, 7] [0, 2] [0, 2, 4, 6, 7] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
五、归并排序性能分析
六、快速排序、堆排序、归并排序-小结
