题目
给定版本号：version = ["1.5.1", "1.45.0", "1.99.99", "3.3.3.3", "1.5", "6"]
写一个函数对版本号从小到大排序。
解答
为了对版本号进行排序，我们需要将每个版本号字符串转换为整数元组，然后根据这些元组进行排序。这样可以确保每个部分按数值大小正确比较，并处理不同长度的版本号：
分割和转换：将每个版本号字符串按点号分割成多个部分，并将每个部分转换为整数。
元组比较：利用Python元组的自然排序机制，逐个比较每个部分的值。较短版本号在比较时，缺失的部分视为0。
排序：使用Python的内置排序函数，根据转换后的元组进行排序。
def sort_versions(versions):
return sorted(versions, key=lambda v: tuple(map(int, v.split('.'))))
# 示例测试
version = ["1.5.1", "1.45.0", "1.99.99", "3.3.3.3", "1.5", "6"]
sorted_versions = sort_versions(version)
print(sorted_versions)
# ['1.5', '1.5.1', '1.45.0', '1.99.99', '3.3.3.3', '6']附1：key=lambda v: tuple(map(int, v.split('.')))的解释
1.v.split('.')
- 作用：将版本号字符串按点号
.分割成多个部分 - 结果：生成字符串列表（每个部分仍是字符串）
"1.5.1".split('.') # 返回: ['1', '5', '1']
"3.3.3.3".split('.') # 返回: ['3', '3', '3', '3']
"6".split('.') # 返回: ['6']2.map(int, ...)
作用：将每个字符串部分转换为整数
为什么需要：避免字符串比较（如 "10" < "2" 的错误情况）
map(int, ['1', '5', '1']) # 转换为: [1, 5, 1]
map(int, ['3', '3', '3', '3']) # 转换为: [3, 3, 3, 3]
map(int, ['6']) # 转换为: [6]3.tuple(...)
作用：将整数列表转换为元组
为什么需要：元组支持按元素顺序比较（这是版本号排序的关键）
tuple([1, 5, 1]) # 转换为: (1, 5, 1)
tuple([3, 3, 3, 3]) # 转换为: (3, 3, 3, 3)
tuple([6]) # 转换为: (6,)4.lambda v: ...
作用：创建一个临时函数，接受版本号字符串
v，返回转换后的元组
# 定义一个匿名函数
lambda v: tuple(map(int, v.split('.')))相当于：
def key_function(v):
parts = v.split('.')
int_parts = [int(part) for part in parts]
return tuple(int_parts)附2：快速排序的代码实现（递归算法）
快速排序是一种高效的排序算法，采用分治策略。其基本思想是选择一个基准元素，将数组分为两部分：小于基准的部分和大于基准的部分，然后递归地对这两部分进行排序。
基准选择：
选择数组中间元素作为基准（
pivot = arr[len(arr) // 2]）也可以选择第一个、最后一个或随机元素作为基准
分区操作：
left：存储所有小于基准的元素middle：存储所有等于基准的元素（处理重复值）right：存储所有大于基准的元素
递归排序：
对左右分区递归调用快速排序
将排序后的左分区、中间元素、右分区合并
时间复杂度：
平均情况：O(n log n)
最坏情况（已排序数组）：O(n²) - 可通过随机选择基准避免
空间复杂度：O(log n)（递归调用栈）
def quick_sort(arr):
"""
快速排序函数
:param arr: 待排序列表
:return: 排序后的列表
"""
# 递归终止条件：当数组长度为0或1时，直接返回
if len(arr) <= 1:
return arr
# 选择基准元素（这里选择中间元素）
pivot = arr[len(arr) // 2]
# 创建三个分区
left = [x for x in arr if x < pivot] # 小于基准的元素
middle = [x for x in arr if x == pivot] # 等于基准的元素
right = [x for x in arr if x > pivot] # 大于基准的元素
# 递归排序左右分区，并合并结果
return quick_sort(left) + middle + quick_sort(right)
# 测试示例
if __name__ == "__main__":
test_arr = [3, 6, 8, 10, 1, 2, 1]
print("原始数组:", test_arr)
sorted_arr = quick_sort(test_arr)
print("排序结果:", sorted_arr)附3：快速排序的代码实现（非递归算法）
快速排序的非递归实现使用栈来模拟递归过程，避免了递归调用的系统栈开销。下面是完整的实现：
def quick_sort_non_recursive(arr):
"""
快速排序的非递归实现
:param arr: 待排序列表
:return: 排序后的列表（原地排序）
"""
if len(arr) <= 1:
return arr
# 使用栈存储待处理的子数组范围
stack = []
# 初始范围：整个数组
stack.append((0, len(arr) - 1))
while stack:
# 获取当前处理的子数组范围
low, high = stack.pop()
# 如果子数组长度小于等于1，跳过
if low >= high:
continue
# 分区操作
pivot_index = partition(arr, low, high)
# 将左右子数组范围压入栈中
# 先压入较大的子数组，后压入较小的子数组（优化栈深度）
if (pivot_index - low) > (high - pivot_index):
stack.append((low, pivot_index - 1))
stack.append((pivot_index + 1, high))
else:
stack.append((pivot_index + 1, high))
stack.append((low, pivot_index - 1))
return arr
def partition(arr, low, high):
"""
分区函数：选择基准元素并将数组分为两部分
:param arr: 待分区数组
:param low: 子数组起始索引
:param high: 子数组结束索引
:return: 基准元素的最终位置
"""
# 选择基准元素（这里使用三数取中法优化）
mid = low + (high - low) // 2
# 对左、中、右三个元素进行排序
if arr[low] > arr[mid]:
arr[low], arr[mid] = arr[mid], arr[low]
if arr[low] > arr[high]:
arr[low], arr[high] = arr[high], arr[low]
if arr[mid] > arr[high]:
arr[mid], arr[high] = arr[high], arr[mid]
# 选择中位数作为基准（放在high-1位置）
pivot = arr[mid]
arr[mid], arr[high] = arr[high], arr[mid]
# 分区指针
i = low - 1
# 遍历子数组
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
# 将基准元素放到正确位置
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
# 测试代码
if __name__ == "__main__":
# 测试用例
test_cases = [
[3, 6, 8, 10, 1, 2, 1],
[10, 7, 8, 9, 1, 5],
[],
[1],
[5, 4, 3, 2, 1],
[1, 2, 3, 4, 5],
[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
]
for arr in test_cases:
print(f"原始数组: {arr}")
sorted_arr = quick_sort_non_recursive(arr.copy())
print(f"排序结果: {sorted_arr}")
print()
'''
原始数组: [3, 6, 8, 10, 1, 2, 1]
排序结果: [1, 1, 2, 3, 6, 8, 10]
原始数组: [10, 7, 8, 9, 1, 5]
排序结果: [1, 5, 7, 8, 9, 10]
原始数组: []
排序结果: []
原始数组: [1]
排序结果: [1]
原始数组: [5, 4, 3, 2, 1]
排序结果: [1, 2, 3, 4, 5]
原始数组: [1, 2, 3, 4, 5]
排序结果: [1, 2, 3, 4, 5]
原始数组: [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
排序结果: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
'''