Skip to content

Instantly share code, notes, and snippets.

@vimiix
Last active Feb 8, 2018
Embed
What would you like to do?
归并排序
# !/usr/bin/python3
# coding=utf-8
# Time: O(n*logn)
# Space: O(n)
# 合并
def merge(l1, l2):
index1 = index2 = 0
r = []
while index1 < len(l1) and index2 < len(l2):
if l1[index1] < l2[index2]:
r.append(l1[index1])
index1 += 1
else:
r.append(l2[index2])
index2 += 1
if index1 == len(l1):
r += l2[index2:]
if index2 == len(l2):
r += l1[index1:]
return r
# 分解
def merge_sort(l):
if len(l) <= 1:
return l
middle = len(l) // 2
l1 = merge_sort(l[:middle])
l2 = merge_sort(l[middle:])
return merge(l1, l2)
if __name__ == "__main__":
arr = [3,5,1,6,8,4,9]
sorted_arr = merge_sort(arr)
print(sorted_arr)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment