终止货架问题中的循环

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

令我沮丧的是，“break”语句似乎只是拒绝按我说的去做，而且越来越多的元素不断被插入。

比如让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) 循环简单地保持运行ning 并在满足条件时不断插入大小为 4 的块。

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

Answer 1

TLDR：使用 for:...else: 和嵌套 if:，而不是 for: 和嵌套 if:...else:。 for 循环的 else: 子句只有在循环中没有执行 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

终止货架问题中的循环

Terminating the loop in the shelf problem

python

insertion-sort