前言

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

需求：已知序列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)

1. iterable: 这是必需参数。可以是任何可迭代对象，如列表、元组、字符串、字典等。
2. key: 这是一个可选参数。它是一个函数，作用于 iterable 参数中的每一个元素，sorted 函数将使用该函数的返回值进行排序。
3. 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_index
sorted_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 相对较差。
• 空间复杂度：字典方法需要额外空间，其它两种方法不需要。

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

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