算法札记11——归并排序

浏览: 1272

归并排序

算法思想

归并排序算法会把序列分成长度相同的两个子序列,当无法继续往下分时(也就是每个子序列中只有一个数据时),就对子序列进行归并。归并指的是把两个排好序的子序列合并成一个有序序列。该操作会一直重复执行,直到所有子序列都归并为一个整体为止。
https://www.cnblogs.com/onepixel/articles/7674659.html

栗子

image.png

image.png

时间复杂度

时间复杂度是O(nlogn)

代码实现

# coding: utf-8

def merge_sort(alist):
# 归并排序
n = len(alist)
# 当长度小于1,直接返回
if n <= 1:
return alist

# 取整函数,将原数据分成两个部分
mid = n // 2
# 采用归并排序后形成的左边有序新序列
left_li = merge_sort(alist[:mid])

# 采用归并排序后形成的右边有序新序列
right_li = merge_sort(alist[mid:])

# 将两个有序的子序列进行合并
# merge(left, right)
left_pointer, right_pointer = 0, 0
result = []

while left_pointer < len(left_li) and right_pointer < len(right_li):
if left_li[left_pointer] < right_li[right_pointer]:
result.append(left_li[left_pointer])
left_pointer += 1
else:
result.append(right_li[right_pointer])
right_pointer += 1

# 若某边已合并完毕,某边还有剩下,直接将该边中的元素追加到列表
result += left_li[left_pointer:]
result += right_li[right_pointer:]
return result

li = [2, 9, 7 ,4, 8, 5, 10, 3, 1, 6]
print("排序前li:", li)
sort_li = merge_sort(li)
print("排序后li:", li)
print("返回值:", sort_li)

image.png

image.png

# baidubaike

def MergeSort(lists):
if len(lists) <= 1:
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<len(left) and r<len(right):
# 若左边小于右边,追加到左边列表,指针右移
if left[l] <= right[r]:
result.append(left[l])
l += 1
else:
# 反之追加到右边,同时指针右移
result.append(right[r])
r += 1

# 如果某边的元素还有剩余直接全部追击到列表中
result += list(left[l:])
result += list(right[r:])
return result
print (MergeSort([1, 2, 3, 4, 5, 6, 7, 90, 21, 23, 45]))
推荐 0
本文由 皮大大 创作,采用 知识共享署名-相同方式共享 3.0 中国大陆许可协议 进行许可。
转载、引用前需联系作者,并署名作者且注明文章出处。
本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责。本站是一个个人学习交流的平台,并不用于任何商业目的,如果有任何问题,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。

0 个评论

要回复文章请先登录注册