Python 中的 INSERTION SORT 从 if 语句转换为基于 for 循环的高效解决方案

Question

我有以下代码对列表中的 4 个项目执行插入排序。它有效，但它使用 IF 语句。我对各种解决方案感兴趣，这些解决方案显示 a) 转换（基于我的代码和变量）到使用循环的更简单、更有效的算法，其中有重复，以及 b）关于 where/why 已实现的内容的明确解释。

使用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()

上述代码如何转化为基于loop/loop的解决方案 + 我也对递归解决方案，但出于 teaching/learning 目的再次直接从该解决方案派生。

例如，可以通过识别每次迭代完成 lengthoflist-1 次来开始。

所以：

 for i in range((len(list))-1):
    cv=list[i+1]
    etc

我知道会有一个外循环和一个内循环。这些是如何最好地构造的，并且再次明确解释如何从这个基于 if 的原始代码中派生出解决方案，这就是我所追求的。

Answer 1

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

l = [4, 1, 2, 6]

然后，我们需要简单地做一个 for-loop 循环遍历 l 中的索引。尽管（第二个元素）我们需要从索引 1 开始，因为 insertion 通过移动元素 left （如你所知）来工作，所以我们应该从第二个开始元素并转到最后一个（因此 l 的长度：len(l)）。

然后我们要开始whileloop。这将继续，而 i（index）中的当前元素在 list 小于其 left 和 [=24 的元素=] 大于 0（所以我们还没有结束）。

例如，在for-loop的第一次迭代中，i将是1，它在l中具有1的元素值。由于 1 大于 l[i-1]（这是 4）并且 i 即 1 是 > 0，我们输入 while.

在 while loop 中，我们所做的就是使用漂亮的语法 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]

Python 中的 INSERTION SORT 从 if 语句转换为基于 for 循环的高效解决方案

conversion from if statements to efficient for loop based solution for INSERTION SORT in Python

python

sorting

if-statement

insertion