Python高级排序算法应用（python简单排序）
基础排序算法实
- 快速排序（Quick Sort）
算法原理： 采用分治策略，选取基准值(pivot)将数组分为两部分，递归排序子数组
def quick_sort(arr):
"""标准快速排序实现"""
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)
优化版本（原地排序）
def quick_sort_inplace(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
if low < high:
# 分区操作
pivot_index = partition(arr, low, high)
# 递归排序子数组
quick_sort_inplace(arr, low, pivot_index - 1)
quick_sort_inplace(arr, pivot_index + 1, high)
def partition(arr, low, high):
"""分区函数，返回基准位置"""
pivot = arr[high] # 选择最后一个元素作为基准
i = low
for j in range(low, high):
if arr[j] < pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[high] = arr[high], arr[i]
return i
测试用例
nums = [3, 6, 8, 10, 1, 2, 1]
quick_sort_inplace(nums)
print("快速排序结果:", nums) # 输出: [1, 1, 2, 3, 6, 8, 10]
性能特点：
- 平均时间复杂度：O(n log n)
- 最坏情况（已排序数组）：O(n^2)
- 空间复杂度：O(log n)（递归调用栈）
- 归并排序（Merge Sort）
算法原理： 递归地将数组分成两半分别排序，然后合并两个有序数组
def merge_sort(arr):
"""归并排序实现"""
if len(arr) <= 1:
return arr
# 分割数组
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# 合并已排序数组
return merge(left, right)
def merge(left, right):
"""合并两个有序数组"""
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# 添加剩余元素
result.extend(left[i:])
result.extend(right[j:])
return result
测试用例
nums = [12, 11, 13, 5, 6, 7]
print("归并排序结果:", merge_sort(nums)) # 输出: [5, 6, 7, 11, 12, 13]
性能特点：
- 时间复杂度：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 < n and arr[left] > arr[largest]:
largest = left
# 右子节点大于当前最大值
if right < n and arr[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)
- 稳定排序（在优化实现中）
混合排序算法
- Timsort算法（Python内置排序）
算法原理： 结合归并排序和插入排序的优点，是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 < n:
for start in range(0, n, size * 2):
mid = start + size - 1
end = min((start + size * 2 - 1), (n - 1))
# 合并两个相邻片段
merged = merge(arr[start:mid + 1], arr[mid + 1:end + 1])
arr[start:start + len(merged)] = merged
size *= 2
return arr
测试用例
import random
nums = [random.randint(1, 1000) for _ in range(100)]
sorted_nums = timsort(nums.copy())
print("Timsort前5个:", sorted_nums[:5])
性能特点：
- 时间复杂度： 最佳情况：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^2/k + k)（当使用O(n^2)排序算法时） 最坏情况：O(n^2)（所有元素在一个桶中）
- 空间复杂度：O(n + k)
特定场景排序算法
- 基数排序（Radix Sort）
适用场景： 非负整数或固定长度字符串排序
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.popleft()
sorted_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.readline()
if 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.readline()
if 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].readline()
if 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')
附录：排序算法性能对比表
表：常见排序算法性能对比
算法名称 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 适用场景 |
快速排序 | O(n log n) | O(n^2) | O(log n) | 不稳定 | 通用排序，大数据量 |
归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 大数据量，需要稳定性 |
堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 | 原地排序，大数据量 |
Timsort | O(n log n) | O(n log n) | O(n) | 稳定 | Python内置，实际数据排序 |
计数排序 | O(n + k) | O(n + k) | O(n + k) | 稳定 | 小范围整数排序 |
基数排序 | O(d(n + k)) | O(d(n + k)) | O(n + k) | 稳定 | 固定长度数字/字符串 |
桶排序 | O(n + k) | O(n^2) | O(n + k) | 稳定 | 均匀分布的数据 |
#编程# #python# #在头条记录我的2025# #春日生活打卡季#
持续更新Python编程相关学习日志，敬请关注！