Python排序：跨品牌归并相同取货地址的商品

需求明确 #

• 输入列表已按品牌完成排序，需保持品牌分组的整体顺序不变
• 不同品牌中取货地址相同的商品必须连续排列
• 每个品牌组内的商品原始相对顺序需完整保留（稳定排序要求）

示例输入 #

items = [
    {"brand": "Adidas", "pick_up_address": 1},
    {"brand": "Adidas", "pick_up_address": 2},
    {"brand": "Adidas", "pick_up_address": 2},
    {"brand": "Adidas", "pick_up_address": 3},
    {"brand": "Adidas", "pick_up_address": 3},
    {"brand": "Adidas", "pick_up_address": 4},
    {"brand": "Adidas", "pick_up_address": 5},
    {"brand": "Adidas", "pick_up_address": 5},
    {"brand": "Adidas", "pick_up_address": 5},
    {"brand": "Adidas", "pick_up_address": 5},
    {"brand": "Nike", "pick_up_address": 2},
    {"brand": "Nike", "pick_up_address": 2}
]

期望输出 #

sorted_items = [
    {"brand": "Adidas", "pick_up_address": 1},
    {"brand": "Adidas", "pick_up_address": 3},
    {"brand": "Adidas", "pick_up_address": 3},
    {"brand": "Adidas", "pick_up_address": 4},
    {"brand": "Adidas", "pick_up_address": 5},
    {"brand": "Adidas", "pick_up_address": 5},
    {"brand": "Adidas", "pick_up_address": 5},
    {"brand": "Adidas", "pick_up_address": 5},
    {"brand": "Adidas", "pick_up_address": 2},
    {"brand": "Adidas", "pick_up_address": 2},
    {"brand": "Nike", "pick_up_address": 2},
    {"brand": "Nike", "pick_up_address": 2}
]

解决方案思路 #

核心逻辑是通过取货地址的最后出现位置作为排序依据，结合Python内置的稳定排序特性实现需求：

1. 遍历原列表，统计每个取货地址最后一次出现的索引位置
2. 以该索引位置为排序键，对原列表进行稳定排序：
   • 同地址的商品会因为排序键相同，保持原有的相对顺序（原列表已按品牌排序，因此同地址的不同品牌商品自然连续，且品牌组内原序保留）
   • 最后出现位置越靠前的地址，排序优先级越高，确保不同地址的分组顺序符合示例要求

代码实现 #

# 统计每个取货地址的最后出现索引
last_occurrence = {}
for idx, item in enumerate(items):
    addr = item["pick_up_address"]
    last_occurrence[addr] = idx  # 持续更新，最终保存最后一次出现的索引

# 稳定排序：按地址最后出现索引升序排列
sorted_items = sorted(items, key=lambda x: last_occurrence[x["pick_up_address"]])

# 验证输出（可选）
for item in sorted_items:
    print(item)

方案说明 #

• 稳定排序特性确保了原列表中同地址元素的相对顺序不变，既保留了品牌组内的原始顺序，也保证了不同品牌的同地址商品连续排列
• 原列表已按品牌排序，因此同地址的商品在原列表中是按品牌分组的，排序后自然保持该分组结构
• 统计最后出现索引的操作时间复杂度为O(n)，排序操作时间复杂度为O(n log n)，整体效率较高

内容的提问来源于stack exchange，提问作者Roni Jack Vituli