归并排序

• 时间复杂度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]

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
 

文章来源: pengshiyu.blog.csdn.net，作者：彭世瑜，版权归原作者所有，如需转载，请联系作者。

原文链接：pengshiyu.blog.csdn.net/article/details/80699750