你还不知道的Python算法：归并排序—Testfan打卡学测开1119

本期技术分享讲师Arthur老师

分享内容：

什么是二分查找？

本期语音讲解

本期文字解析

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

【算法描述】

归并操作的工作原理如下：

第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置

第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤3直到某一指针超出序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

【举个例子】：

指的是将两个顺序序列合并成一个顺序序列的方法。

如　设有数列

初始状态：6,202,100,301,38,8,1

第一次归并后：,,,，比较次数：3；

第二次归并后：，，比较次数：4；

第三次归并后：,比较次数：4；

总的比较次数为：3+4+4=11；

特点：稳定算法 （仅次于快速排序）

时间复杂度：O(n log n)

空间复杂度：O(n)

Python代码实现：

from random import randint

def MergeSort(lists):

if len(lists)

return lists

num = int( len(lists) / 2 )

left = MergeSort(lists[:num])

right = MergeSort(lists[num:])

return Merge(left, right)

def Merge(left,right):

r, l=0, 0

result=[]

while l

if left[l]

result.append(left[l])

l += 1

else:

result.append(right[r])

r += 1

result += list(left[l:])

result += list(right[r:])

return result

lst = []

for i in range(10):

lst.append(randint(1, 100))

print(MergeSort(lst))