归并排序
算法思想
归并排序算法会把序列分成长度相同的两个子序列,当无法继续往下分时(也就是每个子序列中只有一个数据时),就对子序列进行归并。归并指的是把两个排好序的子序列合并成一个有序序列。该操作会一直重复执行,直到所有子序列都归并为一个整体为止。
https://www.cnblogs.com/onepixel/articles/7674659.html
栗子
image.png
时间复杂度
时间复杂度是
代码实现
def merge_sort(alist):
n = len(alist)
if n <= 1:
return alist
mid = n // 2
left_li = merge_sort(alist[:mid])
right_li = merge_sort(alist[mid:])
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
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]))