蓝桥杯python语言基础（7）——自定义排序和二分查找

目录

一、自定义排序

（一）sorted

（二）list.sort

二、二分查找

bisect

---

一、自定义排序

（一）sorted

sorted() 函数会返回一个新的已排序列表，而列表的 sort() 方法会直接在原列表上进行排序。这两个方法都接受一个 key 参数，key 是一个函数，用于指定排序的依据。

my_list = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]# 按照元素的平方进行排序   
sorted_by_square = sorted(my_list, key=lambda x: x ** 2)   
print(sorted_by_square)# 定义一个包含字典的列表   
students = [{'name': 'Alice', 'age': 20},{'name': 'Bob', 'age': 18},{'name': 'Charlie', 'age': 22}   
]# 按照学生的年龄进行排序   
students.sort(key=lambda student: student['age'])   
print(students)

 基于比较函数的排序

functools.cmp_to_key 是Python标准库 functools 模块中的一个函数，它的作用是将一个传统的比较函数（comparison function）转换为一个 key 函数，以便在 sorted()、min()、max() 等支持 key 参数的函数中使用。

import functoolsdef custom_compare(tuple1, tuple2):# 这里以二元组第一个元素的绝对值大小进行排序# 如果第一个元素绝对值相等，则按照第二个元素的大小排序abs_value1 = abs(tuple1[0])abs_value2 = abs(tuple2[0])if abs_value1 < abs_value2:return -1elif abs_value1 > abs_value2:return 1else:if tuple1[1] < tuple2[1]:return -1elif tuple1[1] > tuple2[1]:return 1else:return 0tuple_list = [(3, 5), (-2, 7), (2, 1), (-4, 3)]   
sorted_list = sorted(tuple_list, key=functools.cmp_to_key(custom_compare))   
print(sorted_list)

 对字符串排序

string_list = ["apple", "banana", "cherry", "date", "fig", "melon"]def custom_key(s):return len(s), ssorted_by_length = sorted(string_list, key=custom_key)   
print(sorted_by_length)

sorted() 函数会根据 custom_key 函数返回的元组进行排序。首先会按照元组的第一个元素（字符串长度）进行排序，如果长度相同，再按照元组的第二个元素（字符串本身，即字典序）进行排序。在长度相同的情况下按照其他规则排序，只需要相应地修改 custom_key 函数的返回值即可。

为什么 key=custom_key ？

在 sorted() 函数中使用 key=custom_key 而不是 key=custom_key(s) ，这是因为 key 参数需要的是一个函数对象，而不是调用该函数的结果。

key=custom_key ，sorted() 函数会在排序过程中，对可迭代对象中的每个元素自动调用 custom_key 函数。也就是说，sorted() 函数会遍历 string_list 中的每个字符串，依次将每个字符串作为参数传递给 custom_key 函数，然后根据 custom_key 函数返回的值来确定元素的排序顺序。

（二）list.sort

直接修改原始列表，而不是像 sorted() 函数那样返回一个新的已排序列表

string_list = ["apple", "banana", "cherry", "date", "fig", "melon"]def custom_key(s):return len(s), sstring_list.sort(key=custom_key)   
print(string_list)

二、二分查找

bisect

用于在有序序列中进行二分查找和插入操作

bisect.bisect_left(a, x, lo=0, hi=len(a))

在有序列表 a 中查找元素 x 应该插入的位置，使得插入后列表仍然保持有序。如果 x 已经存在于列表中，返回它左边的插入点。

import bisecta = [1, 3, 5, 7, 9]   
x = 4index = bisect.bisect_left(a, x)   
print(f"元素 {x} 应该插入到索引 {index} 处")

bisect.bisect_right(a, x, lo=0, hi=len(a)) （别名 bisect.bisect(a, x, lo=0, hi=len(a))）

import bisectnums = [1, 2, 2, 3]# bisect_left
target = 2
left_index = bisect.bisect_left(nums, target)
print(f"bisect_left 查找 {target} 在列表 {nums} 中的插入点: {left_index}")# bisect_right
right_index = bisect.bisect_right(nums, target)
print(f"bisect_right 查找 {target} 在列表 {nums} 中的插入点: {right_index}")new_target = 2
bisect.insort_left(nums, new_target)
print(f"insort_left 将 {new_target} 插入到列表 {[2, 2, 2, 2]} 后: {nums}")new_target2 = 2
bisect.insort_right(nums, new_target2)
print(f"insort_right 将 {new_target2} 插入到列表 {[2, 2, 2, 2]} 后: {nums}")