合并算法误区
合并算法误区
提问于 2020-12-01 15:49:44
这里的Python学生，
我一直在学习基本的算法，我有一些困难，完全理解MergeSort。我相信我理解分而治之的方法，如何在每个循环周期内创建名称空间，以及算法如何分割元素。我有点困惑的地方是它如何重新组合/合并元素，然后依次处理排序的值。
我想我能理解从结果第21行到第37行的一切。即如何将nlist转换为[27, 43]。我的具体问题是关于results第38行，以及在结果第21行是[43, 27]的righthalf是如何处理nlist即[27, 43] (results第38行)的值的。
因为我没有看到nlist的任何变量赋值给righthalf,
也就是说，righthalf = nlist不在“结果”行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]回答 2
Stack Overflow用户
回答已采纳
发布于 2020-12-02 03:18:04
尤里卡!在这件事上花了几个小时.我已经找到了。
当一个可变对象(在本例中是一个列表)作为参数传递到函数中时(‘右旋焓’)，并且这个参数是递归地变异的('nlist')，这个参数也会发生变异，并且这个变化会在函数之外反映出来。这表示python的“调用对象引用”属性。https://www.geeksforgeeks.org/is-python-call-by-reference-or-call-by-value/
在这种特殊情况下
将'nlist'
- 'nlist‘中的
- ’右焓‘- 43，27作为参数传递到合并函数中，
- 递归函数在递归函数中被突变为27，43在递归函数中，
- 都指向内存中相同的参考位置，’右焓‘也是变异的，不需要传统的赋值
。
righthalf = nlist谢谢大家！
Stack Overflow用户
发布于 2020-12-01 16:18:27
假设您面前有两个排序列表。要获得合并列表，请在两个列表的前面取两个元素中最小的元素，然后重复，直到两个列表都用完为止。
[*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]
[]
[]页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/65093843
复制相关文章
相似问题
腾讯云开发者
