摘要：def quick_sort(arr):"""标准快速排序实现"""if len(arr)
算法原理： 采用分治策略，选取基准值(pivot)将数组分为两部分，递归排序子数组
def quick_sort(arr):"""标准快速排序实现"""if len(arr) pivot]return quick_sort(left) + middle + quick_sort(right)优化版本（原地排序）def quick_sort_inplace(arr, low=0, high=None):if high is None:high = len(arr) - 1 if low性能特点：
平均时间复杂度：O(n log n)最坏情况（已排序数组）：O(n²)空间复杂度：O(log n)（递归调用栈）归并排序（Merge Sort）算法原理： 递归地将数组分成两半分别排序，然后合并两个有序数组
def merge_sort(arr):"""归并排序实现"""if len(arr)性能特点：
时间复杂度：O(n log n)（所有情况）空间复杂度：O(n)（需要临时数组）稳定排序算法堆排序（Heap Sort）算法原理： 利用二叉堆的性质进行排序，分为建堆和不断提取最大/最小元素两个阶段
def heap_sort(arr):"""堆排序实现"""n = len(arr)# 构建最大堆 for i in range(n // 2 - 1, -1, -1):heapify(arr, n, i)# 逐个提取元素 for i in range(n - 1, 0, -1):arr[i], arr[0] = arr[0], arr[i] # 交换 heapify(arr, i, 0)def heapify(arr, n, i):"""堆调整函数"""largest = i # 初始化最大元素为根 left = 2 * i + 1 right = 2 * i + 2 # 左子节点大于根 if left arr[largest]:largest = left # 右子节点大于当前最大值 if right arr[largest]:largest = right # 如果最大值不是根，交换并继续堆化 if largest != i:arr[i], arr[largest] = arr[largest], arr[i]heapify(arr, n, largest)测试用例 nums = [12, 11, 13, 5, 6, 7]heap_sort(nums)print("堆排序结果:", nums) # 输出: [5, 6, 7, 11, 12, 13]性能特点：
时间复杂度：O(n log n)（所有情况）空间复杂度：O(1)（原地排序）不稳定排序算法计数排序（Counting Sort）适用场景： 整数排序，数据范围不大且密集的情况
def counting_sort(arr, max_val=None):"""计数排序实现"""if max_val is None:max_val = max(arr)# 初始化计数数组 count = [0] * (max_val + 1)# 计算每个元素出现次数 for num in arr:count[num] += 1 # 重构排序后的数组 sorted_arr = for num, cnt in enumerate(count):sorted_arr.extend([num] * cnt)return sorted_arr 优化版本（处理任意范围）def counting_sort_advanced(arr):min_val = min(arr)max_val = max(arr)# 计算偏移量并初始化计数数组 count = [0] * (max_val - min_val + 1)# 计数 for num in arr:count[num - min_val] += 1 # 重构数组 sorted_arr = for i, cnt in enumerate(count):sorted_arr.extend([i + min_val] * cnt)return sorted_arr 测试用例 nums = [4, 2, 2, 8, 3, 3, 1]print("计数排序结果:", counting_sort_advanced(nums)) # 输出: [1, 2, 2, 3, 3, 4, 8]性能特点：
时间复杂度：O(n + k)（k是数据范围）空间复杂度：O(n + k)稳定排序（在优化实现中）算法原理： 结合归并排序和插入排序的优点，是Python内置的sorted和list.sort使用的算法
Python实际上使用C实现的Timsort，这里展示类似逻辑 def insertion_sort(arr, left=0, right=None):"""插入排序，用于小规模数据"""if right is None:right = len(arr) - 1 for i in range(left + 1, right + 1):key = arr[i]j = i - 1 while j >= left and arr[j] > key:arr[j + 1] = arr[j]j -= 1 arr[j + 1] = key def timsort(arr):"""简化版Timsort实现"""min_run = 32 n = len(arr)# 对小片段进行插入排序 for i in range(0, n, min_run):insertion_sort(arr, i, min((i + min_run - 1), n - 1))# 逐步合并排序好的片段 size = min_run while size性能特点：
时间复杂度： 最佳情况：O(n)（已排序数组） 平均情况：O(n log n) 最坏情况：O(n log n)空间复杂度：O(n)稳定排序桶排序（Bucket Sort）适用场景： 数据均匀分布在某个范围内时效率最高
def bucket_sort(arr, bucket_size=5):"""桶排序实现"""if len(arr) == 0:return arr # 确定数据范围 min_val = min(arr)max_val = max(arr)# 初始化桶 bucket_count = (max_val - min_val) // bucket_size + 1 buckets = [ for _ in range(bucket_count)]# 将元素分配到桶中 for num in arr:buckets[(num - min_val) // bucket_size].append(num)# 对每个桶排序并合并 sorted_arr = for bucket in buckets:sorted_arr.extend(sorted(bucket)) # 这里可以使用任意排序算法 return sorted_arr 测试用例 nums = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]print("桶排序结果:", bucket_sort(nums)) # 输出: [0.1234, 0.3434, 0.565, 0.656, 0.665, 0.897]性能特点：
时间复杂度： 最佳情况：O(n + k)（k是桶的数量） 平均情况：O(n + n²/k + k)（当使用O(n²)排序算法时） 最坏情况：O(n²)（所有元素在一个桶中）空间复杂度：O(n + k)特定场景排序算法适用场景： 非负整数或固定长度字符串排序
def radix_sort(arr):"""基数排序实现（LSD）"""# 获取最大位数 max_num = max(arr)max_digit = len(str(max_num))for digit in range(max_digit):# 每位数使用计数排序 buckets = [ for _ in range(10)]for num in arr:# 获取当前位的数字 d = (num // (10 digit)) % 10 buckets[d].append(num)# 重新组合数组 arr = [num for bucket in buckets for num in bucket]return arr 测试用例 nums = [170, 45, 75, 90, 802, 24, 2, 66]print("基数排序结果:", radix_sort(nums)) # 输出: [2, 24, 45, 66, 75, 90, 170, 802]性能特点：
时间复杂度：O(d(n + k))（d是最大位数，k是基数如10）空间复杂度：O(n + k)稳定排序拓扑排序（Topological Sort）适用场景： 有向无环图(DAG)的任务排序
from collections import defaultdict, deque def topological_sort(graph):"""拓扑排序实现"""# 计算入度 in_degree = defaultdict(int)for u in graph:for v in graph[u]:in_degree[v] += 1 # 初始化队列（入度为0的节点）queue = deque([u for u in graph if in_degree[u] == 0])sorted_order = while queue:u = queue.popleftsorted_order.append(u)# 减少邻居的入度 for v in graph[u]:in_degree[v] -= 1 if in_degree[v] == 0:queue.append(v)# 检查是否存在环 if len(sorted_order) != len(graph):raise ValueError("图中存在环，无法进行拓扑排序")return sorted_order 测试用例 course_graph = {'C1': ['C3'],'C2': ['C3', 'C4'],'C3': ['C5'],'C4': ['C5', 'C6'],'C5': ,'C6': }print("拓扑排序结果:", topological_sort(course_graph)) 可能的输出: ['C1', 'C2', 'C3', 'C4', 'C5', 'C6']性能特点：
时间复杂度：O(V + E)（顶点数加边数）空间复杂度：O(V)多条件排序复杂对象排序
class Student:def __init__(self, name, grade, age):self.name = name self.grade = grade self.age = age def __repr__(self):return f"{self.name}({self.grade}, {self.age})"创建测试数据 students = [Student('张三', 'B', 20),Student('李四', 'A', 22),Student('王五', 'B', 21),Student('赵六', 'A', 20)]按成绩升序，年龄降序排序 students_sorted = sorted(students, key=lambda s: (s.grade, -s.age))print("多条件排序结果:", students_sorted)输出: [李四(A, 22), 赵六(A, 20), 王五(B, 21), 张三(B, 20)]处理大规模数据外部排序技术
import tempFile import heapq def external_sort(input_file, output_file, chunk_size=1000):"""外部排序实现"""# 第一步：分块排序 temp_files = with open(input_file, 'r') as f:while True:chunk = for _ in range(chunk_size):line = f.readlineif not line:break chunk.append(int(line))if not chunk:break chunk.sort# 写入临时文件 temp_file = tempfile.NamedTemporaryFile(delete=False)with open(temp_file.name, 'w') as tf:for num in chunk:tf.write(f"{num}\n")temp_files.append(temp_file.name)# 第二步：多路归并 with open(output_file, 'w') as out_f:# 打开所有临时文件 files = [open(fname, 'r') for fname in temp_files]# 使用堆进行归并 heap = for i, f in enumerate(files):line = f.readlineif line:heapq.heappush(heap, (int(line), i))while heap:num, file_idx = heapq.heappop(heap)out_f.write(f"{num}\n")# 从对应文件中读取下一行 line = files[file_idx].readlineif line:heapq.heappush(heap, (int(line), file_idx))# 关闭文件 for f in files:f.close# 清理临时文件 for fname in temp_files:os.unlink(fname)生成测试数据 import random with open('large_input.txt', 'w') as f:for _ in range(10000):f.write(f"{random.randint(1, 1000000)}\n")执行外部排序 external_sort('large_input.txt', 'sorted_output.txt')算法名称平均时间复杂度最坏时间复杂度空间复杂度稳定性适用场景来源：ICodeWR
