归并排序
- 时间复杂度O(nlogn)
- 空间复杂度O(n)
假设现在的列表分两段有序,将其合成为一个有序列表
- 分解: 将列表越分越小,直至分成一个元素
- 一个元素是有序的
- 合并:将两个有序的列表合并,列表越来越大
代码实现
# 归并排序
import random
import sys
sys.setrecursionlimit(10000) # 设置递归深度默认1000
# 一次归并,合并有序序列
def merge(lst, low, mid, high):
i = low
j = mid + 1
lst_temp = []
while i<=mid and j <= high:
if lst[i] <= lst[j]:
lst_temp.append(lst[i])
i += 1
else:
lst_temp.append(lst[j])
j += 1
while i <= mid:
lst_temp.append(lst[i])
i += 1
while j <= high:
lst_temp.append(lst[j])
j += 1
lst[low: high+1] = lst_temp
#归并排序
def merge_sort(lst, low, high):
if low < high:
mid = (low + high)//2
merge_sort(lst, low, mid)
merge_sort(lst, mid+1, high)
merge(lst, low, mid, high)
lst = list(range(10))
random.shuffle(lst)
merge_sort(lst, 0, 9)
print(lst)
#[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]