归并排序
- 时间复杂度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]
