从if语句到Python中基于循环的插入排序高效解决方案的转换

2024-03-28 19:03:26 发布

您现在位置:Python中文网/ 问答频道 /正文

下面的代码对列表中的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的代码中导出解决方案的清晰解释,是我想要的。你知道吗


Tags: and代码ifshiftmainwithelement语句
1条回答
网友
1楼 · 发布于 2024-03-28 19:03:26

首先,从不命名一个列表"list",因为它覆盖了内置的list()函数。相反,我将其命名为l

l = [4, 1, 2, 6]

然后,我们只需要做一个for-loop循环遍历l中的索引。我们需要从索引1开始(第二个元素),因为insertion的工作方式是将元素向左移动(如您所知),因此我们应该从第二个元素开始,然后转到最后一个元素(因此llen(l))。你知道吗

然后我们要开始whileloop。当list中位于i(the index)的当前元素小于其左侧的元素并且i大于0(因此我们还没有结束)。你知道吗

例如,在for-loop的第一次迭代中,i将是1,它在l中具有1的元素值。由于1大于l[i-1](这是4),而i1> 0,我们输入while。你知道吗

whileloop中,我们所做的就是用漂亮的语法stolen from here将当前元素和左边的元素切换。你知道吗

最后,在while中要做的最后一件事是将索引减少1,也就是说,将当前位置移到左边,这样如果它再次小于左边的元素,我们就可以切换到另一个开关。你知道吗

在解释完这些之后,下面是代码:

for i in range(1, len(l)):
    while l[i] < l[i-1] and i > 0:
        l[i-1], l[i] = l[i], l[i-1]
        i -= 1

l修改为:

[1, 2, 4, 6]

相关问题 更多 >