Merge Sort#
Merge Sort的Python实现
1def merge(l1, l2):
2 result = []
3
4 i = j = 0
5
6 while i < len(l1) and j < len(l2):
7
8 if l1[i] > l2[j]:
9 result.append(l2[j])
10 j += 1
11
12 elif l1[i] < l2[j]:
13 result.append(l1[i])
14 i += 1
15 else:
16 result.append(l1[i])
17 result.append(l2[j])
18 i += 1
19 j += 1
20
21 while i < len(l1):
22 result.append(l1[i])
23 i += 1
24
25 while j < len(l2):
26 result.append(l2[j])
27 j += 1
28
29 return result
30
31
32def merge_sort(my_list):
33
34 if len(my_list) == 1:
35 return my_list
36
37 mid_index = int(len(my_list) / 2)
38
39 left = merge_sort(my_list[:mid_index])
40 right = merge_sort(my_list[mid_index:])
41
42 return merge(left, right)
43
44
45result = merge_sort([6, 6, 3, 1, 8, 7, 2, 6])
46print(result)