终止货架问题中的循环

Question

我目前正在做架子问题(我希望这是相当有名的？)从本质上讲，我被赋予了一个架子(集合)块(元素)的场景，我应该根据它们的大小重新排列它们。这是插入排序介绍的一部分。

这个问题的第一部分涉及到我编写一个函数insert_animation(block_pos, shelf, high)。这个函数接受不同大小的块组成的货架，例如[Block size: 2, Block size: 6, Block size: 1, Block size: 4, Block size: 8, Block size: 3, Block size: 9]。给我函数shelf.insert(position, block) (在给定位置插入块)和shelf.pop(position)函数(在位置删除元素)。

对于这个问题，我应该首先从货架上弹出索引(整数) block_pos处的元素，将弹出元素与从0到high的范围内的每个元素进行比较，然后在相同或更大的值的元素之前插入弹出元素。如果没有这样的值(即弹出元素大于所有值)，则将在high位置(即范围的最后一个位置)插入弹出元素。

我想我理解这个逻辑，并想出了这样一个代码：

def insert_animate(block_pos, shelf, high):
    if block_pos == 0:
        return shelf
    p = shelf.pop(block_pos)
    for i in range(high):
        if p.size <= shelf[i].size:
            shelf.insert(i, p)
            break
        else:
            shelf.insert(high, p)
    return shelf

令我沮丧的是，“中断”这句话似乎只是拒绝按我说的做，越来越多的元素被插入其中。

例如，让s = [Block size: 2, Block size: 6, Block size: 1, Block size: 4, Block size: 8, Block size: 3, Block size: 9] (这是一段要求教授给出的程序才能运行的代码，而不是只在Python上工作)。

假设现在我想要print(insert_animate(3, s, 3))。我希望

[Block size: 2, Block size: 4, Block size: 6, Block size: 1, Block size: 8, Block size: 3, Block size: 9]

4码块在6码块之前被弹出和插入的地方。我希望合理吗？

但通过上面的代码，我得到了

[Block size: 2, Block size: 4, Block size: 6, Block size: 1, Block size: 4, Block size: 8, Block size: 3, Block size: 9]

正如我所看到的，问题在于break只是不能工作，而for i in range(high)循环只是在满足条件时继续运行，并继续插入大小为4的块。

今天我已经想了好几个小时了，但还是想不出什么办法来解决这个问题。这只是我后来所有问题的冰山一角，但我认为这是问题的根源，所以如果有人能就这件事提供任何建议，我会非常感激的！

Answer 1

TLDR:将for:...else:与嵌套if:一起使用，而不是将for:与嵌套if:...else:一起使用。只有在循环中没有执行else:时，for循环的break子句才会触发--这相当于没有找到有效位置，因此需要在末尾插入元素。

当前的代码为每个不小的元素插入p，直到找到一个较小的元素：

def insert_animate(block_pos, shelf, high):
    if block_pos == 0:
        return shelf
    p = shelf.pop(block_pos)
    for i in range(high):
        if p.size <= shelf[i].size:
            shelf.insert(i, p)
            break   # stop once smaller element is found
        else:       # triggers *for each i* with p.size > shelf[i].size
            shelf.insert(high, p)  # insert until loop is stopped
    return shelf

将其更改为只在所有元素都不较小的情况下触发：

def insert_animate(block_pos, shelf, high):
    if block_pos == 0:
        return shelf
    p = shelf.pop(block_pos)
    for i in range(high):
        if p.size <= shelf[i].size:
            shelf.insert(i, p)
            break
    else:  # triggers *for all i* with p.size > shelf[i].size
        shelf.insert(high, p)  # insert at most once
    return shelf