你还不知道的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))

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181119B0AE0L00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券