归并排序算法误解
mergesort algorithm misunderstanding
Python同学，
我一直在研究基本算法，但在完全理解 MergeSort 时遇到了一些困难。
我相信我理解分而治之的方法，如何在每个循环周期内创建命名空间，以及算法如何拆分元素。我有点困惑的是它如何 reassembles/merges 元素，连续采用排序值。
我想我理解从结果行 21 到 37 的所有内容。即 nlist 如何转换为 [27, 43]。
我的具体问题是关于 results 第 38 行以及结果第 21 行 [43, 27] 的 righthalf 如何取 nlist 的值，即 [27, 43]（results 第 38 行).
因为我没有看到 nlist 到 righthalf,
的任何变量赋值
即righthalf = nlist 不在 'results' 第 37 和 38 行之间的代码流中
MergeSort 算法（带有诊断打印语句）：
def mergeSort(nlist):
print("Splitting ", nlist)
if len(nlist) > 1:
mid = len(nlist) // 2
lefthalf = nlist[: mid]
righthalf = nlist[mid :]
print('wow', 'lefthalf', lefthalf)
mergeSort(lefthalf)
print('this is the right1', righthalf)
mergeSort(righthalf)
print('this is the right2', righthalf)
i = j = k = 0
print("cool")
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
print('bot', 'k', 'i', 'j', 'lefthalf', 'righthalf', k, i, j, lefthalf, righthalf)
nlist[k] = lefthalf[i]
print('nlist[k]', nlist[k], nlist)
i = i + 1
else:
print('me')
nlist[k] = righthalf[j]
print('k', 'nlist[k]', k, nlist[k], nlist)
print(righthalf)
j = j + 1
k = k + 1
while i < len(lefthalf):
print('cot', 'k', 'i', 'lefthalf', k, i, lefthalf)
nlist[k] = lefthalf[i]
print('nlist[k]', nlist[k], nlist)
i = i + 1
k = k + 1
while j < len(righthalf):
print('dot', 'k', 'j', 'righthalf', k, j, righthalf)
nlist[k] = righthalf[j]
print('nlist[k]', nlist[k], nlist)
j = j + 1
k = k + 1
print("Merging ", nlist)
nlist = [14, 46, 43, 27, 57, 41, 45, 21, 70]
mergeSort(nlist)
print(nlist)
结果
1 Splitting [14, 46, 43, 27, 57, 41, 45, 21, 70]
2 wow lefthalf [14, 46, 43, 27]
3 Splitting [14, 46, 43, 27]
4 wow lefthalf [14, 46]
5 Splitting [14, 46]
6 wow lefthalf [14]
7 Splitting [14]
8 Merging [14]
9 yah righthalf [46]
10 this is the right1 [46]
11 Splitting [46]
12 Merging [46]
13 this is the right2 [46]
14 cool
15 bot k i j lefthalf righthalf 0 0 0 [14] [46]
16 nlist[k] 14 [14, 46]
17 dot k j righthalf 1 0 [46]
18 nlist[k] 46 [14, 46]
19 Merging [14, 46]
20 yah righthalf [43, 27]
21 this is the right1 [43, 27]
22 Splitting [43, 27]
23 wow lefthalf [43]
24 Splitting [43]
25 Merging [43]
26 yah righthalf [27]
27 this is the right1 [27]
28 Splitting [27]
29 Merging [27]
30 this is the right2 [27]
31 cool
32 me
33 k nlist[k] 0 27 [27, 27]
34 [27]
35 cot k i lefthalf 1 0 [43]
36 nlist[k] 43 [27, 43]
37 Merging [27, 43]
38 this is the right2 [27, 43]
39 cool
40 bot k i j lefthalf righthalf 0 0 0 [14, 46] [27, 43]
41 nlist[k] 14 [14, 46, 43, 27]
42 me
43 k nlist[k] 1 27 [14, 27, 43, 27]
44 [27, 43]
45 me
46 k nlist[k] 2 43 [14, 27, 43, 27]
47 [27, 43]
48 cot k i lefthalf 3 1 [14, 46]
49 nlist[k] 46 [14, 27, 43, 46]
50 Merging [14, 27, 43, 46]
51 yah righthalf [57, 41, 45, 21, 70]
52 this is the right1 [57, 41, 45, 21, 70]
53 Splitting [57, 41, 45, 21, 70]
54 wow lefthalf [57, 41]
55 Splitting [57, 41]
56 wow lefthalf [57]
57 Splitting [57]
58 Merging [57]
59 yah righthalf [41]
60 this is the right1 [41]
61 Splitting [41]
62 Merging [41]
63 this is the right2 [41]
64 cool
65 me
66 k nlist[k] 0 41 [41, 41]
67 [41]
68 cot k i lefthalf 1 0 [57]
69 nlist[k] 57 [41, 57]
70 Merging [41, 57]
71 yah righthalf [45, 21, 70]
72 this is the right1 [45, 21, 70]
73 Splitting [45, 21, 70]
74 wow lefthalf [45]
75 Splitting [45]
76 Merging [45]
77 yah righthalf [21, 70]
78 this is the right1 [21, 70]
79 Splitting [21, 70]
80 wow lefthalf [21]
81 Splitting [21]
82 Merging [21]
83 yah righthalf [70]
84 this is the right1 [70]
85 Splitting [70]
86 Merging [70]
87 this is the right2 [70]
88 cool
89 bot k i j lefthalf righthalf 0 0 0 [21] [70]
90 nlist[k] 21 [21, 70]
91 dot k j righthalf 1 0 [70]
92 nlist[k] 70 [21, 70]
93 Merging [21, 70]
94 this is the right2 [21, 70]
95 cool
96 me
97 k nlist[k] 0 21 [21, 21, 70]
98 [21, 70]
99 bot k i j lefthalf righthalf 1 0 1 [45] [21, 70]
100 nlist[k] 45 [21, 45, 70]
101 dot k j righthalf 2 1 [21, 70]
102 nlist[k] 70 [21, 45, 70]
103 Merging [21, 45, 70]
104 this is the right2 [21, 45, 70]
105 cool
106 me
107 k nlist[k] 0 21 [21, 41, 45, 21, 70]
108 [21, 45, 70]
109 bot k i j lefthalf righthalf 1 0 1 [41, 57] [21, 45, 70]
110 nlist[k] 41 [21, 41, 45, 21, 70]
111 me
112 k nlist[k] 2 45 [21, 41, 45, 21, 70]
113 [21, 45, 70]
114 bot k i j lefthalf righthalf 3 1 2 [41, 57] [21, 45, 70]
115 nlist[k] 57 [21, 41, 45, 57, 70]
116 dot k j righthalf 4 2 [21, 45, 70]
117 nlist[k] 70 [21, 41, 45, 57, 70]
118 Merging [21, 41, 45, 57, 70]
119 this is the right2 [21, 41, 45, 57, 70]
120 cool
121 bot k i j lefthalf righthalf 0 0 0 [14, 27, 43, 46] [21, 41, 45, 57, 70]
122 nlist[k] 14 [14, 46, 43, 27, 57, 41, 45, 21, 70]
123 me
124 k nlist[k] 1 21 [14, 21, 43, 27, 57, 41, 45, 21, 70]
125 [21, 41, 45, 57, 70]
126 bot k i j lefthalf righthalf 2 1 1 [14, 27, 43, 46] [21, 41, 45, 57, 70]
127 nlist[k] 27 [14, 21, 27, 27, 57, 41, 45, 21, 70]
128 me
129 k nlist[k] 3 41 [14, 21, 27, 41, 57, 41, 45, 21, 70]
130 [21, 41, 45, 57, 70]
131 bot k i j lefthalf righthalf 4 2 2 [14, 27, 43, 46] [21, 41, 45, 57, 70]
132 nlist[k] 43 [14, 21, 27, 41, 43, 41, 45, 21, 70]
133 me
134 k nlist[k] 5 45 [14, 21, 27, 41, 43, 45, 45, 21, 70]
135 [21, 41, 45, 57, 70]
136 bot k i j lefthalf righthalf 6 3 3 [14, 27, 43, 46] [21, 41, 45, 57, 70]
137 nlist[k] 46 [14, 21, 27, 41, 43, 45, 46, 21, 70]
138 dot k j righthalf 7 3 [21, 41, 45, 57, 70]
139 nlist[k] 57 [14, 21, 27, 41, 43, 45, 46, 57, 70]
140 dot k j righthalf 8 4 [21, 41, 45, 57, 70]
141 nlist[k] 70 [14, 21, 27, 41, 43, 45, 46, 57, 70]
142 Merging [14, 21, 27, 41, 43, 45, 46, 57, 70]
143 [14, 21, 27, 41, 43, 45, 46, 57, 70]
假设您面前有两个排序列表。要获得合并列表，您需要在两个列表的头部取最小的两个元素，并重复直到用完两个列表。
[*14, 27, 43, 46]
[ 21, 41, 45, 57, 70]
[ 27, 43, 46]
[*21, 41, 45, 57, 70]
[*27, 43, 46]
[ 41, 45, 57, 70]
[ 43, 46]
[*41, 45, 57, 70]
[*43, 46]
[ 45, 57, 70]
[ 46]
[*45, 57, 70]
[*46]
[ 57, 70]
[]
[*57, 70]
[]
[*70]
[]
[]
尤里卡！在花费了大量时间之后...我找到了它。
当可变对象（在本例中为列表）作为参数传递给函数时 ('righthalf')，并且该参数被递归变异 ('nlist')，该参数也是突变，这种变化反映在函数之外。这表示 python 的“通过对象引用调用”属性。
https://www.geeksforgeeks.org/is-python-call-by-reference-or-call-by-value/
在这种特定情况下
- 'righthalf' - [43, 27] 作为参数传递给合并排序函数，
- 递归函数将其接收为 'nlist'
- 'nlist' 在递归函数中被变异为 [27, 43]，
- 由于两者都指向内存中的相同引用位置，'righthalf'
也发生了变异，不需要传统的赋值
righthalf = nlist
谢谢大家！
Python同学，
我一直在研究基本算法，但在完全理解 MergeSort 时遇到了一些困难。
我相信我理解分而治之的方法，如何在每个循环周期内创建命名空间，以及算法如何拆分元素。我有点困惑的是它如何 reassembles/merges 元素，连续采用排序值。
我想我理解从结果行 21 到 37 的所有内容。即 nlist 如何转换为 [27, 43]。
我的具体问题是关于 results 第 38 行以及结果第 21 行 [43, 27] 的 righthalf 如何取 nlist 的值，即 [27, 43]（results 第 38 行).
因为我没有看到 nlist 到 righthalf,
即righthalf = nlist 不在 'results' 第 37 和 38 行之间的代码流中
MergeSort 算法（带有诊断打印语句）：
def mergeSort(nlist):
print("Splitting ", nlist)
if len(nlist) > 1:
mid = len(nlist) // 2
lefthalf = nlist[: mid]
righthalf = nlist[mid :]
print('wow', 'lefthalf', lefthalf)
mergeSort(lefthalf)
print('this is the right1', righthalf)
mergeSort(righthalf)
print('this is the right2', righthalf)
i = j = k = 0
print("cool")
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
print('bot', 'k', 'i', 'j', 'lefthalf', 'righthalf', k, i, j, lefthalf, righthalf)
nlist[k] = lefthalf[i]
print('nlist[k]', nlist[k], nlist)
i = i + 1
else:
print('me')
nlist[k] = righthalf[j]
print('k', 'nlist[k]', k, nlist[k], nlist)
print(righthalf)
j = j + 1
k = k + 1
while i < len(lefthalf):
print('cot', 'k', 'i', 'lefthalf', k, i, lefthalf)
nlist[k] = lefthalf[i]
print('nlist[k]', nlist[k], nlist)
i = i + 1
k = k + 1
while j < len(righthalf):
print('dot', 'k', 'j', 'righthalf', k, j, righthalf)
nlist[k] = righthalf[j]
print('nlist[k]', nlist[k], nlist)
j = j + 1
k = k + 1
print("Merging ", nlist)
nlist = [14, 46, 43, 27, 57, 41, 45, 21, 70]
mergeSort(nlist)
print(nlist)
结果
1 Splitting [14, 46, 43, 27, 57, 41, 45, 21, 70]
2 wow lefthalf [14, 46, 43, 27]
3 Splitting [14, 46, 43, 27]
4 wow lefthalf [14, 46]
5 Splitting [14, 46]
6 wow lefthalf [14]
7 Splitting [14]
8 Merging [14]
9 yah righthalf [46]
10 this is the right1 [46]
11 Splitting [46]
12 Merging [46]
13 this is the right2 [46]
14 cool
15 bot k i j lefthalf righthalf 0 0 0 [14] [46]
16 nlist[k] 14 [14, 46]
17 dot k j righthalf 1 0 [46]
18 nlist[k] 46 [14, 46]
19 Merging [14, 46]
20 yah righthalf [43, 27]
21 this is the right1 [43, 27]
22 Splitting [43, 27]
23 wow lefthalf [43]
24 Splitting [43]
25 Merging [43]
26 yah righthalf [27]
27 this is the right1 [27]
28 Splitting [27]
29 Merging [27]
30 this is the right2 [27]
31 cool
32 me
33 k nlist[k] 0 27 [27, 27]
34 [27]
35 cot k i lefthalf 1 0 [43]
36 nlist[k] 43 [27, 43]
37 Merging [27, 43]
38 this is the right2 [27, 43]
39 cool
40 bot k i j lefthalf righthalf 0 0 0 [14, 46] [27, 43]
41 nlist[k] 14 [14, 46, 43, 27]
42 me
43 k nlist[k] 1 27 [14, 27, 43, 27]
44 [27, 43]
45 me
46 k nlist[k] 2 43 [14, 27, 43, 27]
47 [27, 43]
48 cot k i lefthalf 3 1 [14, 46]
49 nlist[k] 46 [14, 27, 43, 46]
50 Merging [14, 27, 43, 46]
51 yah righthalf [57, 41, 45, 21, 70]
52 this is the right1 [57, 41, 45, 21, 70]
53 Splitting [57, 41, 45, 21, 70]
54 wow lefthalf [57, 41]
55 Splitting [57, 41]
56 wow lefthalf [57]
57 Splitting [57]
58 Merging [57]
59 yah righthalf [41]
60 this is the right1 [41]
61 Splitting [41]
62 Merging [41]
63 this is the right2 [41]
64 cool
65 me
66 k nlist[k] 0 41 [41, 41]
67 [41]
68 cot k i lefthalf 1 0 [57]
69 nlist[k] 57 [41, 57]
70 Merging [41, 57]
71 yah righthalf [45, 21, 70]
72 this is the right1 [45, 21, 70]
73 Splitting [45, 21, 70]
74 wow lefthalf [45]
75 Splitting [45]
76 Merging [45]
77 yah righthalf [21, 70]
78 this is the right1 [21, 70]
79 Splitting [21, 70]
80 wow lefthalf [21]
81 Splitting [21]
82 Merging [21]
83 yah righthalf [70]
84 this is the right1 [70]
85 Splitting [70]
86 Merging [70]
87 this is the right2 [70]
88 cool
89 bot k i j lefthalf righthalf 0 0 0 [21] [70]
90 nlist[k] 21 [21, 70]
91 dot k j righthalf 1 0 [70]
92 nlist[k] 70 [21, 70]
93 Merging [21, 70]
94 this is the right2 [21, 70]
95 cool
96 me
97 k nlist[k] 0 21 [21, 21, 70]
98 [21, 70]
99 bot k i j lefthalf righthalf 1 0 1 [45] [21, 70]
100 nlist[k] 45 [21, 45, 70]
101 dot k j righthalf 2 1 [21, 70]
102 nlist[k] 70 [21, 45, 70]
103 Merging [21, 45, 70]
104 this is the right2 [21, 45, 70]
105 cool
106 me
107 k nlist[k] 0 21 [21, 41, 45, 21, 70]
108 [21, 45, 70]
109 bot k i j lefthalf righthalf 1 0 1 [41, 57] [21, 45, 70]
110 nlist[k] 41 [21, 41, 45, 21, 70]
111 me
112 k nlist[k] 2 45 [21, 41, 45, 21, 70]
113 [21, 45, 70]
114 bot k i j lefthalf righthalf 3 1 2 [41, 57] [21, 45, 70]
115 nlist[k] 57 [21, 41, 45, 57, 70]
116 dot k j righthalf 4 2 [21, 45, 70]
117 nlist[k] 70 [21, 41, 45, 57, 70]
118 Merging [21, 41, 45, 57, 70]
119 this is the right2 [21, 41, 45, 57, 70]
120 cool
121 bot k i j lefthalf righthalf 0 0 0 [14, 27, 43, 46] [21, 41, 45, 57, 70]
122 nlist[k] 14 [14, 46, 43, 27, 57, 41, 45, 21, 70]
123 me
124 k nlist[k] 1 21 [14, 21, 43, 27, 57, 41, 45, 21, 70]
125 [21, 41, 45, 57, 70]
126 bot k i j lefthalf righthalf 2 1 1 [14, 27, 43, 46] [21, 41, 45, 57, 70]
127 nlist[k] 27 [14, 21, 27, 27, 57, 41, 45, 21, 70]
128 me
129 k nlist[k] 3 41 [14, 21, 27, 41, 57, 41, 45, 21, 70]
130 [21, 41, 45, 57, 70]
131 bot k i j lefthalf righthalf 4 2 2 [14, 27, 43, 46] [21, 41, 45, 57, 70]
132 nlist[k] 43 [14, 21, 27, 41, 43, 41, 45, 21, 70]
133 me
134 k nlist[k] 5 45 [14, 21, 27, 41, 43, 45, 45, 21, 70]
135 [21, 41, 45, 57, 70]
136 bot k i j lefthalf righthalf 6 3 3 [14, 27, 43, 46] [21, 41, 45, 57, 70]
137 nlist[k] 46 [14, 21, 27, 41, 43, 45, 46, 21, 70]
138 dot k j righthalf 7 3 [21, 41, 45, 57, 70]
139 nlist[k] 57 [14, 21, 27, 41, 43, 45, 46, 57, 70]
140 dot k j righthalf 8 4 [21, 41, 45, 57, 70]
141 nlist[k] 70 [14, 21, 27, 41, 43, 45, 46, 57, 70]
142 Merging [14, 21, 27, 41, 43, 45, 46, 57, 70]
143 [14, 21, 27, 41, 43, 45, 46, 57, 70]
假设您面前有两个排序列表。要获得合并列表，您需要在两个列表的头部取最小的两个元素，并重复直到用完两个列表。
[*14, 27, 43, 46]
[ 21, 41, 45, 57, 70]
[ 27, 43, 46]
[*21, 41, 45, 57, 70]
[*27, 43, 46]
[ 41, 45, 57, 70]
[ 43, 46]
[*41, 45, 57, 70]
[*43, 46]
[ 45, 57, 70]
[ 46]
[*45, 57, 70]
[*46]
[ 57, 70]
[]
[*57, 70]
[]
[*70]
[]
[]
尤里卡！在花费了大量时间之后...我找到了它。
当可变对象（在本例中为列表）作为参数传递给函数时 ('righthalf')，并且该参数被递归变异 ('nlist')，该参数也是突变，这种变化反映在函数之外。这表示 python 的“通过对象引用调用”属性。 https://www.geeksforgeeks.org/is-python-call-by-reference-or-call-by-value/
在这种特定情况下
- 'righthalf' - [43, 27] 作为参数传递给合并排序函数，
- 递归函数将其接收为 'nlist'
- 'nlist' 在递归函数中被变异为 [27, 43]，
- 由于两者都指向内存中的相同引用位置，'righthalf' 也发生了变异，不需要传统的赋值
righthalf = nlist
谢谢大家！