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
|
import random
def func(li):
if len(li) <= 1:
return li
mid = len(li) // 2
left = func(li[0:mid])
right = func(li[mid:])
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
result.extend(left), result.extend(right)
return result
a = [i for i in range(111)]
random.shuffle(a)
print(func(a))
|
使用索引的方法
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
|
import random
def func(li):
if len(li) <= 1:
return li
mid = len(li) // 2
left = func(li[0:mid])
right = func(li[mid:])
result = []
left_index, right_index = 0, 0
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
result.append(left[left_index])
left_index += 1
else:
result.append(right[right_index])
right_index += 1
result.extend(left[left_index:]), result.extend(right[right_index:])
return result
a = [i for i in range(111)]
random.shuffle(a)
print(func(a))
|
然而上面两种方法都不是太好, 因为都要开辟新的空间, 推荐下面写法
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
import random
def func(li): # 有返回值的写法
if len(li) <= 1:
return li
mid = len(li) // 2
left = func(li[:mid]) # 有返回值的话, 要用变量接收
right = func(li[mid:])
left_index = 0
right_index = 0
li_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index] < right[right_index]:
li[li_index] = left[left_index]
left_index += 1
else:
li[li_index] = right[right_index]
right_index += 1
li_index += 1
while left_index < len(left):
li[li_index] = left[left_index]
left_index += 1
li_index += 1
while right_index < len(right):
li[li_index] = right[right_index]
right_index += 1
li_index += 1
return li
a = [i for i in range(22)]
random.shuffle(a)
print(func(a))
import random
def func(li): # 无返回值的写法
if len(li) > 1:
mid = len(li) // 2
left, right = li[:mid], li[mid:]
func(left), func(right)
left_index, right_index, li_index = 0, 0, 0
while left_index < len(left) and right_index < len(right):
if left[left_index] < right[right_index]:
li[li_index] = left[left_index]
left_index += 1
else:
li[li_index] = right[right_index]
right_index += 1
li_index += 1
while left_index < len(left):
li[li_index] = left[left_index]
left_index += 1
li_index += 1
while right_index < len(right):
li[li_index] = right[right_index]
right_index += 1
li_index += 1
a = [i for i in range(22)]
random.shuffle(a)
func(a)
print(a)
|