下面的代码对列表中的4项执行插入排序。它工作,但它使用IF语句。我对各种解决方案感兴趣,这些解决方案表明a)转换(基于我的代码和变量)到使用循环的更简单、更有效的算法,其中存在重复;b)清楚地解释在哪里/为什么实现了什么。你知道吗
使用IF语句的插入排序代码:
def main():
list=[4,1,2,6]
print("original list:",list)
cv=list[1]
if cv<list[0]:
list[1]=list[0]
list[0]=cv
print("Compare element 1 with 0:",list)
cv=list[2]
if cv<list[1]:
list[2]=list[1]
list[1]=cv
print("Compare element 2 with 1 & shift 1 upto 2:",list)
if cv<list[0]:
list[1]=list[0]
list[0]=cv
print("Compare element 2 with 0 and shift 0 and 1 up:",list)
cv=list[3]
if cv<list[2]:
list[3]=list[2]
list[2]=cv
print("Compare element 3 with 2 & shift 2 upto 3:",list)
if cv<list[1]:
list[2]=list[1]
list[1]=cv
print("Compare element 3 with 1 and shift 1 and 2 up:",list)
if cv<list[0]:
list[1]=list[0]
list[0]=cv
print("Compare element 3 with 0 and shift 0 up:",list)
main()
上面的代码如何转化为基于循环的解决方案呢?我也对递归的解决方案很感兴趣,但是出于教学目的还是直接从这个解决方案派生出来的。你知道吗
例如,一开始可以重新计算每个迭代执行lengthoflist-1次。你知道吗
所以:
for i in range((len(list))-1):
cv=list[i+1]
etc
我知道会有一个外环和一个内环。这些是如何最好地构造的,同样,一个关于如何从这个原始的基于if的代码中导出解决方案的清晰解释,是我想要的。你知道吗
首先,从不命名一个列表
"list"
,因为它覆盖了内置的list()
函数。相反,我将其命名为l
:然后,我们只需要做一个
for-loop
循环遍历l
中的索引。我们需要从索引1
开始(第二个元素),因为insertion
的工作方式是将元素向左移动(如您所知),因此我们应该从第二个元素开始,然后转到最后一个元素(因此l
:len(l)
)。你知道吗然后我们要开始
while
loop
。当list
中位于i
(theindex
)的当前元素小于其左侧的元素并且i
大于0
(因此我们还没有结束)。你知道吗例如,在
for-loop
的第一次迭代中,i
将是1
,它在l
中具有1
的元素值。由于1
大于l[i-1]
(这是4
),而i
即1
即> 0
,我们输入while
。你知道吗在
while
loop
中,我们所做的就是用漂亮的语法stolen from here将当前元素和左边的元素切换。你知道吗最后,在
while
中要做的最后一件事是将索引减少1
,也就是说,将当前位置移到左边,这样如果它再次小于左边的元素,我们就可以切换到另一个开关。你知道吗在解释完这些之后,下面是代码:
将
l
修改为:相关问题 更多 >
编程相关推荐