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

简介: 序列排序是日常开发常见的需求。实现方式有很多,哪种方式最简洁明了?需求:已知序列A、B拥有相同的元素,要求序列A依照序列B排序进行排序。

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


需求:已知序列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 方法) 是三者中最优的选择。它在性能上占据优势,并且代码简洁直观,易于维护。

相关文章
|
1天前
|
机器学习/深度学习 调度 Python
SOFTS: 时间序列预测的最新模型以及Python使用示例
这是2024年4月《SOFTS: Efficient Multivariate Time Series Forecasting with Series-Core Fusion》中提出的新模型,采用集中策略来学习不同序列之间的交互,从而在多变量预测任务中获得最先进的性能。
11 4
|
1天前
|
存储 索引 Python
【Python列表解锁】:掌握序列精髓,驾驭动态数据集合
【Python列表解锁】:掌握序列精髓,驾驭动态数据集合
|
6天前
|
存储 算法 数据挖掘
LeetCode第33题:搜索旋转排序数组【python】
LeetCode第33题:搜索旋转排序数组【python】
|
10天前
|
存储 算法 Java
【经典算法】 leetcode88.合并排序的数组(Java/C/Python3实现含注释说明,Easy)
【经典算法】 leetcode88.合并排序的数组(Java/C/Python3实现含注释说明,Easy)
7 1
|
11天前
|
机器学习/深度学习 自然语言处理 TensorFlow
|
11天前
|
数据库 索引 Python
10.Python【序列】- 字符串(下)
10.Python【序列】- 字符串
17 0
|
11天前
|
存储 数据安全/隐私保护 索引
10.Python【序列】- 字符串(上)
10.Python【序列】- 字符串
29 3
|
11天前
|
运维 索引 Python
9.Python【非序列】- 集合
9.Python【非序列】- 集合
20 2
|
11天前
|
索引 Python
8.Python【非序列】- 字典
8.Python【非序列】- 字典
11 2
|
11天前
|
索引 Python
7.Python【序列】- 元组
7.Python【序列】- 元组