我遇到了mergeSort算法的以下实现:
def merge_sort(x):
merge_sort2(x,0,len(x)-1)
def merge_sort2(x,first,last):
if first < last:
middle = (first + last) // 2
merge_sort2(x,first,middle)
merge_sort2(x,middle+1,last)
merge(x,first,middle,last)
def merge(x,first,middle,last):
L = x[first:middle+1]
R = x[middle+1:last+1]
L.append(999999999)
R.append(999999999)
i=j=0
for k in range(first,last+1):
if L[i] <= R[j]:
x[k] = L[i]
i += 1
else:
x[k] = R[j]
j += 1
x = [17, 87, 6, 22, 41, 3, 13, 54]
x_sorted = merge_sort(x)
print(x)
我得到了大部分。但是,我不明白的是合并函数的以下四行:
L = x[first:middle+1]
R = x[middle+1:last+1]
L.append(999999999)
R.append(999999999)
首先:为什么切片以middle+1结束?在Python中切片数组包括最后一个元素,对吗?那么,难道不应该从第一:中间?那么,+1有什么用呢? 第二:为什么我要把这个巨大的数字附加到清单上?为什么没有它就不能工作?没有,我查过了。但我不知道为什么。你知道吗
实际上,您并不需要意大利面条式的嵌套函数,只要从https://rosettacode.org/wiki/Sorting_algorithms/Merge_sort#Python重复即可
索引不应该有+1,因为如果Python片段是相同的索引,那么它们就不会重叠
此外,merge的
heapq
实现比您可以编写的更为优化(=)问题1:在Python中对数组进行切片包括最后一个元素,对吗?
不,像范围函数Python切片不包括最后一个元素。你知道吗
问题2:关于下面的片段。你知道吗
如果不将这些大的数字追加到列表中,您的合并代码可能与下面的代码有所不同。你知道吗
正如@Cedced\u Bro在评论部分指出的那样,那些最大的数字被用来知道一方的终点已经到达。 如果您观察上面的代码片段,如果一个列表中的数字用完了,那么理想情况下,我们会退出for循环,并在temp数组中插入其他列表的剩余元素(如果有的话)。你知道吗
附加这些大的数字是避免这两个for循环的智能方法。但它有一些不必要的成本,将999999999与其他列表中的剩余元素进行比较。你知道吗
相关问题 更多 >
编程相关推荐