以下代码是本网站的副本 http://interactivepython.org/runestone/static/pythonds/SortSearch/TheMergeSort.html
def mergeSort(alist):
print("Splitting ",alist)
if len(alist)>1:
mid = len(alist)//2
lefthalf = alist[:mid]
righthalf = alist[mid:]
mergeSort(lefthalf)
mergeSort(righthalf)
i=0
j=0
k=0
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
alist[k]=lefthalf[i]
i=i+1
else:
alist[k]=righthalf[j]
j=j+1
k=k+1
while i < len(lefthalf):
alist[k]=lefthalf[i]
i=i+1
k=k+1
while j < len(righthalf):
alist[k]=righthalf[j]
j=j+1
k=k+1
print("Merging ",alist)
alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)
在上面的代码中,有两个几乎相同的while循环
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
alist[k]=lefthalf[i]
i=i+1
以及
while i < len(lefthalf):
alist[k]=lefthalf[i]
i=i+1
k=k+1
添加last while循环的原因是什么? 谢谢您!你知道吗
首先,记住合并排序的工作原理:它合并已排序的子列表以创建较长的已排序子列表,直到对整个列表进行排序。(一般情况下是一个按定义排序的单项子列表。)
第一个
while
循环从源子列表获取项,直到到达或的末尾。此时,另一个子列表中可能仍有项。但是,已知这些项都大于(或等于)输出列表中的项。另外两个while
循环(实际上只执行其中一个,因为另一个已经满足终止条件)将这些剩余的项复制到输出列表。如果没有这些循环,您可能会丢失一些项目。你知道吗相关问题 更多 >
编程相关推荐