用 python 优雅实现：序列 A 依照序列 B 排序

2024-05-22
湖南
本文字数：1738 字
阅读完需：约 6 分钟

序列排序是日常开发常见的需求。实现方式有很多，哪种方式最简洁明了？

需求：已知序列 A、B 拥有相同的元素，要求序列 A 依照序列 B 排序进行排序。

# 假设序列 A 和序列 B 是如下：A = [4, 1, 6, 3, 5, 2]B = [1, 2, 3, 4, 5, 6]

复制代码

冒泡排序

通过重复遍历待排序列表，比较相邻元素，交换顺序错误的元素，逐步将最大或最小的元素“冒泡”到列表的一端，就像气泡在液体中上升一样。

# 复制 A 以避免修改原列表sorted_A = A[:]  
# 参照冒泡排序算法for i in range(len(sorted_A)):    for j in range(i + 1, len(sorted_A)):        # 检索A中元素在B的位置        if B.index(sorted_A[i]) > B.index(sorted_A[j]):            sorted_A[i], sorted_A[j] = sorted_A[j], sorted_A[i]
print(sorted_A)  # 输出: [1, 2, 3, 4, 5, 6]

复制代码

使用内置函数 sorted

相对于冒泡排序，内置函数 sorted 简洁而高效。

简洁：如下使用少量的代码，实现等效的排序。

sorted_A = sorted(A, key=lambda x: B.index(x))print(sorted_A)  # 输出: [1, 2, 3, 4, 5, 6]

复制代码

高效：sorted 函数是线性对数时间复杂度 𝑂(𝑛log⁡𝑛)，冒泡算法属于平方时间复杂度 𝑂(𝑛2)。排序的数量级越大，sorted 函数优势越明显。

PS: Python 内置的 sorted 函数以及列表的 sort 方法都使用了一种叫做 Timsort 的排序算法。以下是 sorted 函数的详细介绍及其使用方法：

sorted(iterable, key=None, reverse=False)
iterable: 这是必需参数。可以是任何可迭代对象，如列表、元组、字符串、字典等。 key: 这是一个可选参数。它是一个函数，作用于 iterable 参数中的每一个元素，sorted 函数将使用该函数的返回值进行排序。 reverse: 这是一个可选参数。它是一个布尔值。如果设置为 True，则按照降序排序。默认为 False（升序排序）。

适配元素不存在情况

生产环境中，可能存在序列 A 中元素不在序列 B 中。对于这种情况，使用以上代码会抛出异常。

例如：

A = [4, 1, 6, 3, 5, 7]B = [1, 2, 3, 4, 5, 6]sorted_A = sorted(A, key=lambda x: B.index(x))
Traceback (most recent call last):  File "<input>", line 3, in <module>  File "<input>", line 3, in <lambda>ValueError: 7 is not in list

复制代码

根据墨菲定律（如果有什么事情可能出错，那么它就很有可能会出错），应该进行防御式编程，做相应适配。

使用 if 做预先判断

A = [4, 1, 6, 3, 5, 7]B = [1, 2, 3, 4, 5, 6]# 当序列A中元素不在序列B时，默认排在最后default_index = len(B) + 1
# 定义一个普通函数作为排序的关键字函数def sort_key(x):    return B.index(x) if x in B else default_index
sorted_A = sorted(A, key=sort_key)print(sorted_A)  # 输出: [1, 3, 4, 5, 6, 7]

复制代码

使用 try except 捕获异常

A = [4, 1, 6, 3, 5, 7]B = [1, 2, 3, 4, 5, 6]# 当序列A中元素不在序列B时，默认排在最后default_index = len(B) + 1# 定义一个普通函数作为排序的关键字函数def sort_key(x):    try:        return B.index(x)    except ValueError:        return default_indexsorted_A = sorted(A, key=sort_key)print(sorted_A)  # 输出: [1, 3, 4, 5, 6, 7]

复制代码

转换成字典使用 get 方法

A = [4, 1, 6, 3, 5, 7]B = [1, 2, 3, 4, 5, 6]# 当序列A中元素不在序列B时，默认排在最后default_index = len(B) + 1# 创建一个字典来存储 B 中每个元素的索引index_map = {value: idx for idx, value in enumerate(B)}# 使用这个字典来对 A 进行排序sorted_A = sorted(A, key=lambda x: index_map.get(x, default_index))print(sorted_A) # 输出: [1, 3, 4, 5, 6, 7]

复制代码

总结

对比三种方式：

性能：字典方法 (get) 最优，if 判断其次，try-except 最差。
可读性：if 判断和字典方法较好，try-except 相对较差。
空间复杂度：字典方法需要额外空间，其它两种方法不需要。

异常处理在 Python 中相对较慢 python 字典因为使用哈希表（Hash Table）这种数据结构的原因，时间复杂度是常量级的。是一种以空间换时间的实现方式。优点是速度非常快，缺点是消耗额外内存。

综合考虑性能和可读性，使用字典转换 (get 方法) 是三者中最优的选择。它在性能上占据优势，并且代码简洁直观，易于维护。

作者：程序员非鱼
链接：https://juejin.cn/post/7371422530958049291

发布于: 刚刚阅读数: 5

我再BUG界嘎嘎乱杀

关注

欢迎关注，一起学习，一起交流，一起进步 2020-06-14 加入

公众号：做梦都在改BUG

发布

暂无评论

创作场景

用 python 优雅实现：序列 A 依照序列 B 排序

冒泡排序

使用内置函数 sorted

适配元素不存在情况

总结

我再BUG界嘎嘎乱杀

评论