无法使用插入排序对 Python 中的列表列表进行排序

Question

我目前正在制作一个 Python 程序，它接收杂货的名称、它所在的过道、它在过道上的位置以及价格。它将数据保存在一个列表列表中，每个内部列表包含 4 个元素。该程序试图创建通过过道的最佳路线，奇数过道向上遍历（位置 1 到位置 N），偶数过道向下遍历（位置 N 到 1）。代码如下：

def sort_aisles(data):
    for item in range(1, len(data)):
        key = data[item]
        j = item - 1

        while j >= 0 and key[1] < data[j][1]:
            print('start first while loop', data)
            print()
            if data[j][1] == data[j + 1][1]:
                if int(data[item][1]) % 2 == 0:
                    # even
                    while j >= 0 and key[2] > data[j][2]:
                        print('start even while loop', data)
                        print()
                        data[j + 1] = data[j]
                        j = j - 1
                        print('end even while loop', data)
                        print()
                else:
                    # odd
                    while j >= 0 and key[2] < data[j][2]:
                        print('start odd while loop', data)
                        print()
                        data[j + 1] = data[j]
                        j = j - 1
                        print('end odd while loop', data)
                        print()
            data[j + 1] = data[j]
            j = j - 1

        data[j + 1] = key
        print('end first while loop', data)
        print()
    return data


def display_route(data):
    total = 0
    for item in range(len(data)):
        total += float(data[item][3])
        print('{:<15} Aisle {:>2} Location {:>2} + {:>6.2f} = {:>6.2f}'.format(data[item][0].title(), data[item][1], data[item][2], float(data[item][3]), total))


def main():
    # Prompt
    data = []
    input_data = input('Name, aisle, location, price? ')
    data.append(input_data.split(','))
    print()
    while input_data.lower() != 'done':
        input_data = input('Name, aisle, location, price? ')
        data.append(input_data.split(','))
        print()
    data.pop()
    # Remove whitespace
    data = [[element.strip() for element in items] for items in data]
    # Testing
    sorted_data = sort_aisles(data)
    display_route(sorted_data)


if __name__ == '__main__':
    main()

这里有一个更具体的提示：

想法：

从位置 1 沿着通道 1 到 N，然后向上
- 从位置 N 到 1 的通道 2，等等。
商店可以有任意数量的过道和任意数量的位置。每条过道。
从loc穿过奇数过道。 1 到 N，甚至从 loc。 N 到 1.

算法：

提示：
- 项目名称
- 通道数
- 地点编号
- 价格
输入直到完成（不包括完成）
用户在每个值之间输入逗号
可能是额外的空格before/after逗号
保留清单清单（项目）；列表中的每个项目都有名称、过道、位置。和价格
数据[n][1] = 第 n 个通道，数据[m][2] = 第 m 个位置。
排序项目列表
- 奇数过道按位置升序排序
- 甚至按位置降序排列

我的问题是排序。我目前正在使用嵌套插入排序，但它没有按我预期的方式排序。我一直用来测试的示例输入如下：

Name, aisle, location, price? peanut butter, 3, 5, 1.75

Name, aisle, location, price? fuji apples, 2, 8, 1.50

Name, aisle, location, price? bananas, 2, 1, 2.00

Name, aisle, location, price? potato chips , 3, 3, 2.50

Name, aisle, location, price? cookies,10,5,0.75

Name, aisle, location, price? done

Fuji Apples Aisle 2 Location 8 + 1.50 = 1.50

Bananas Aisle 2 Location 1 + 2.00 = 3.50

Potato Chips Aisle 3 Location 3 + 2.50 = 6.00

Peanut Butter Aisle 3 Location 5 + 1.75 = 7.75

Cookies Aisle 10 Location 5 + 0.75 = 8.50

我试图使用 print 语句来显示每个循环中发生的事情，但它们最终让我更加困惑。这是带有调试信息的 pastebin link：https://pastebin.com/JWpTPkjJ

例如，第五行表示它是第一个 while 循环的结尾，但是 while 循环之前刚刚输出了该消息。

至于我尝试过的方法，最初我有两个函数：一个是先使用单一插入排序对过道进行排序，效果非常好，另一个是之后使用与第一个基本相同的代码对位置进行排序sort_aisles 函数中的 if 语句。这些位置没有正确排序，甚至导致过道 10 上的饼干出于某种原因跳到顶部，所以我将它们合并在一起，这至少将饼干移到了正确的位置，但破坏了之前物品的顺序。

我确定问题出在我的排序算法上，但我一直无法弄清楚出了什么问题。任何有关修复排序算法的帮助将不胜感激。如果 post 有点长，我深表歉意，但我觉得所有细节都很重要。

Answer 1

因此，我们希望在奇数通道上按一个方向（升序）对偶数通道中的物品进行排序（降序）。这意味着我们需要在奇数通道上按位置编号排序，在偶数通道上按位置编号的负数排序。然后我们需要走每条过道，按过道号排序。

我们可以通过为.sort()方法编写一个关键函数来做到这一点。对于正在排序的列表中的每个项目，键函数 return 是一个值，它将以正确的顺序对项目进行排序。由于我们希望物品首先按过道排序，然后按该过道中的位置（升序或降序）排序，因此我们的关键函数将 return 两个值：过道编号和位置编号（在甚至过道）。

过道是您记录中的第二个数字[1]，过道中的位置是第三个项目[2]。所以：

def shop_sequence(record):
    return record[1], record[2] if record[1] % 2 else -record[2]

现在我们只需使用该键函数进行排序：

data.sort(key=shop_sequence)

无法使用插入排序对 Python 中的列表列表进行排序

Trouble sorting list of lists in Python with Insertion Sort

python

sorting

algorithm