042-排序的基本概念

class SortingConcepts: def __init__(self): self.data = [64, 34, 25, 12, 22, 11, 90]

def demonstrate_sorting_concept(self): """演示排序的基本概念""" print("排序前的数据:", self.data)

# 升序排序 ascending = sorted(self.data) print("升序排序后:", ascending)

# 降序排序 descending = sorted(self.data, reverse=True) print("降序排序后:", descending)

# 自定义排序（按绝对值） data_with_negative = [-5, 3, -1, 8, -2, 7] by_absolute = sorted(data_with_negative, key=abs) print("按绝对值排序:", by_absolute)

return ascending, descending, by_absolute

# 演示排序概念 sorting_demo = SortingConcepts() sorting_demo.demonstrate_sorting_concept()

"""演示排序在实际应用中的重要性"""

def __init__(self): self.students = [ {'name': '张三', 'score': 85, 'age': 20}, {'name': '李四', 'score': 92, 'age': 19}, {'name': '王五', 'score': 78, 'age': 21}, {'name': '赵六', 'score': 95, 'age': 20} ]

def search_efficiency_demo(self): """演示排序对搜索效率的影响""" import time import random

# 生成大量随机数据 large_data = [random.randint(1, 10000) for _ in range(10000)] sorted_data = sorted(large_data) target = random.choice(large_data)

# 线性搜索（未排序数据） start_time = time.time() linear_result = self.linear_search(large_data, target) linear_time = time.time() - start_time

# 二分搜索（已排序数据） start_time = time.time() binary_result = self.binary_search(sorted_data, target) binary_time = time.time() - start_time

print(f"线性搜索时间: {linear_time:.6f}秒") print(f"二分搜索时间: {binary_time:.6f}秒") print(f"性能提升: {linear_time/binary_time:.2f}倍")

return linear_time, binary_time

def linear_search(self, arr, target): """线性搜索""" for i, val in enumerate(arr): if val == target: return i return -1

def binary_search(self, arr, target): """二分搜索""" left, right = 0, len(arr) - 1 while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1

def data_organization_demo(self): """演示排序在数据组织中的应用""" print("\n=== 学生信息排序演示 ===")

# 按成绩排序 by_score = sorted(self.students, key=lambda x: x['score'], reverse=True) print("\n按成绩排序（降序）:") for student in by_score: print(f"{student['name']}: {student['score']}分")

# 按年龄排序 by_age = sorted(self.students, key=lambda x: x['age']) print("\n按年龄排序（升序）:") for student in by_age: print(f"{student['name']}: {student['age']}岁")

# 多级排序（先按年龄，再按成绩） multi_sort = sorted(self.students, key=lambda x: (x['age'], -x['score'])) print("\n多级排序（年龄升序，成绩降序）:") for student in multi_sort: print(f"{student['name']}: {student['age']}岁, {student['score']}分")

return by_score, by_age, multi_sort

# 演示排序的重要性 importance_demo = SortingImportance() importance_demo.search_efficiency_demo() importance_demo.data_organization_demo()

"""排序算法分类演示"""

def __init__(self): self.data = [64, 34, 25, 12, 22, 11, 90]

def comparison_based_sorting(self): """基于比较的排序算法示例""" print("=== 基于比较的排序算法 ===")

# 冒泡排序（简化版） def bubble_sort(arr): n = len(arr) comparisons = 0 for i in range(n): for j in range(0, n-i-1): comparisons += 1 if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr, comparisons

data_copy = self.data.copy() sorted_data, comparisons = bubble_sort(data_copy) print(f"冒泡排序结果: {sorted_data}") print(f"比较次数: {comparisons}")

return sorted_data, comparisons

def non_comparison_based_sorting(self): """非基于比较的排序算法示例""" print("\n=== 非基于比较的排序算法 ===")

# 计数排序 def counting_sort(arr): if not arr: return arr

max_val = max(arr) min_val = min(arr) range_val = max_val - min_val + 1

# 计数数组 count = [0] * range_val

# 统计每个元素的出现次数 for num in arr: count[num - min_val] += 1

# 重构排序后的数组 result = [] for i, cnt in enumerate(count): result.extend([i + min_val] * cnt)

return result

sorted_data = counting_sort(self.data) print(f"计数排序结果: {sorted_data}") print("特点: 不需要比较元素，时间复杂度O(n+k)")

return sorted_data

def demonstrate_classification(self): """演示排序算法分类""" print("原始数据:", self.data)

# 基于比较的排序 comp_result, comparisons = self.comparison_based_sorting()

# 非基于比较的排序 non_comp_result = self.non_comparison_based_sorting()

# 分类总结 print("\n=== 排序算法分类总结 ===") print("1. 基于比较的排序:") print(" - 冒泡排序、选择排序、插入排序") print(" - 快速排序、归并排序、堆排序") print(" - 理论下界: O(n log n)")

print("\n2. 非基于比较的排序:") print(" - 计数排序、基数排序、桶排序") print(" - 可以突破O(n log n)的下界") print(" - 通常有特定的使用条件")

return comp_result, non_comp_result

# 演示排序算法分类 classification_demo = SortingClassification() classification_demo.demonstrate_classification()

"""排序算法稳定性演示"""

def __init__(self): # 使用包含重复值的数据来演示稳定性 self.students = [ {'name': '张三', 'score': 85, 'id': 1}, {'name': '李四', 'score': 92, 'id': 2}, {'name': '王五', 'score': 85, 'id': 3}, # 与张三同分 {'name': '赵六', 'score': 78, 'id': 4}, {'name': '钱七', 'score': 92, 'id': 5} # 与李四同分 ]

def stable_sort_demo(self): """稳定排序演示""" print("=== 稳定排序演示 ===") print("原始顺序（按ID排序）:") for student in self.students: print(f"ID:{student['id']} {student['name']} - {student['score']}分")

# 使用Python内置的稳定排序 stable_sorted = sorted(self.students, key=lambda x: x['score'], reverse=True)

print("\n稳定排序后（按分数降序）:") for student in stable_sorted: print(f"ID:{student['id']} {student['name']} - {student['score']}分")

print("\n观察: 相同分数的学生保持原有的相对顺序") print("- 85分: 张三(ID:1) 仍在 王五(ID:3) 前面") print("- 92分: 李四(ID:2) 仍在 钱七(ID:5) 前面")

return stable_sorted

def unstable_sort_demo(self): """不稳定排序演示""" print("\n=== 不稳定排序演示 ===")

# 模拟不稳定的快速排序 def unstable_quick_sort(arr, key_func): """简化的不稳定快速排序""" if len(arr) <= 1: return arr

pivot = arr[len(arr) // 2] pivot_val = key_func(pivot)

left = [x for x in arr if key_func(x) > pivot_val] middle = [x for x in arr if key_func(x) == pivot_val] right = [x for x in arr if key_func(x) < pivot_val]

return (unstable_quick_sort(left, key_func) + middle + unstable_quick_sort(right, key_func))

unstable_sorted = unstable_quick_sort(self.students, lambda x: x['score'])

print("不稳定排序后（模拟）:") for student in unstable_sorted: print(f"ID:{student['id']} {student['name']} - {student['score']}分")

print("\n观察: 相同分数的学生可能改变相对顺序")

return unstable_sorted

def stability_importance(self): """稳定性的重要性""" print("\n=== 稳定性的重要性 ===")

# 多级排序场景 employees = [ {'name': '张三', 'dept': 'IT', 'salary': 8000, 'join_date': '2020-01'}, {'name': '李四', 'dept': 'IT', 'salary': 8000, 'join_date': '2019-06'}, {'name': '王五', 'dept': 'HR', 'salary': 7000, 'join_date': '2021-03'}, {'name': '赵六', 'dept': 'IT', 'salary': 9000, 'join_date': '2018-12'} ]

print("员工信息（原始顺序）:") for emp in employees: print(f"{emp['name']} - {emp['dept']} - {emp['salary']} - {emp['join_date']}")

# 先按入职时间排序 by_join_date = sorted(employees, key=lambda x: x['join_date']) print("\n按入职时间排序:") for emp in by_join_date: print(f"{emp['name']} - {emp['dept']} - {emp['salary']} - {emp['join_date']}")

# 再按薪资排序（稳定排序保持入职时间的顺序） by_salary_stable = sorted(by_join_date, key=lambda x: x['salary'], reverse=True) print("\n按薪资排序（稳定，保持入职时间顺序）:") for emp in by_salary_stable: print(f"{emp['name']} - {emp['dept']} - {emp['salary']} - {emp['join_date']}")

print("\n稳定性的价值:") print("- 相同薪资的员工按入职时间排序（资历优先）") print("- 多级排序的结果更符合业务逻辑")

return by_salary_stable

def demonstrate_stability(self): """演示排序稳定性""" stable_result = self.stable_sort_demo() unstable_result = self.unstable_sort_demo() importance_result = self.stability_importance()

return stable_result, unstable_result, importance_result

# 演示排序稳定性 stability_demo = SortingStability() stability_demo.demonstrate_stability()

"""按存储方式分类的排序算法"""

def __init__(self): self.data = [64, 34, 25, 12, 22, 11, 90]

def internal_sorting_demo(self): """内部排序演示""" print("=== 内部排序演示 ===") print("特点: 所有数据都在内存中进行排序")

import sys

# 显示数据大小 data_size = sys.getsizeof(self.data) print(f"数据大小: {data_size} 字节") print(f"原始数据: {self.data}")

# 内部排序 - 插入排序 def insertion_sort(arr): """插入排序（内部排序）""" for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and arr[j] > key: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key return arr

sorted_data = insertion_sort(self.data.copy()) print(f"排序结果: {sorted_data}") print("适用场景: 数据量较小，能完全装入内存")

return sorted_data

def external_sorting_demo(self): """外部排序演示（模拟）""" print("\n=== 外部排序演示（模拟） ===") print("特点: 数据量太大，无法完全装入内存")

# 模拟大文件数据 import tempfile import os

# 创建临时文件模拟大数据 large_data = list(range(1000, 0, -1)) # 1000个逆序数据 chunk_size = 100 # 每次只能处理100个数据

print(f"总数据量: {len(large_data)} 个元素") print(f"内存限制: 每次只能处理 {chunk_size} 个元素")

# 分块排序并写入临时文件 temp_files = [] for i in range(0, len(large_data), chunk_size): chunk = large_data[i:i + chunk_size] chunk.sort() # 内部排序

# 写入临时文件 temp_file = tempfile.NamedTemporaryFile(mode='w', delete=False) for num in chunk: temp_file.write(f"{num}\n") temp_file.close() temp_files.append(temp_file.name)

print(f"块 {i//chunk_size + 1}: 已排序并写入 {temp_file.name}")

# 多路归并 def merge_files(file_list): """多路归并临时文件""" file_handles = [open(f, 'r') for f in file_list] result = []

# 简化的归并过程（实际应该使用堆优化） current_values = [] for fh in file_handles: line = fh.readline().strip() if line: current_values.append((int(line), fh))

while current_values: # 找到最小值 min_val, min_fh = min(current_values, key=lambda x: x[0]) result.append(min_val)

# 从对应文件读取下一个值 current_values.remove((min_val, min_fh)) line = min_fh.readline().strip() if line: current_values.append((int(line), min_fh))

# 关闭文件 for fh in file_handles: fh.close()

return result

# 执行归并 final_result = merge_files(temp_files)

print(f"\n归并完成，前10个元素: {final_result[:10]}") print(f"后10个元素: {final_result[-10:]}") print(f"是否正确排序: {final_result == sorted(large_data)}")

# 清理临时文件 for temp_file in temp_files: os.unlink(temp_file)

print("\n外部排序的特点:") print("- 分治策略: 分块处理，归并合并") print("- 磁盘I/O: 大量的文件读写操作") print("- 内存管理: 严格控制内存使用") print("- 适用场景: 大数据排序，如数据库排序")

return final_result[:20] # 返回前20个元素作为示例

def demonstrate_storage_classification(self): """演示按存储方式的分类""" internal_result = self.internal_sorting_demo() external_result = self.external_sorting_demo()

print("\n=== 存储方式分类总结 ===") print("1. 内部排序:") print(" - 数据完全在内存中") print(" - 访问速度快，随机访问") print(" - 适合中小规模数据")

print("\n2. 外部排序:") print(" - 数据主要在外存中") print(" - 需要磁盘I/O操作") print(" - 适合大规模数据") print(" - 常用多路归并算法")

return internal_result, external_result

# 演示按存储方式分类 storage_demo = SortingByStorage() storage_demo.demonstrate_storage_classification()

"""排序算法性能分析"""

def __init__(self): self.algorithms = { '冒泡排序': {'best': 'O(n)', 'average': 'O(n²)', 'worst': 'O(n²)'}, '选择排序': {'best': 'O(n²)', 'average': 'O(n²)', 'worst': 'O(n²)'}, '插入排序': {'best': 'O(n)', 'average': 'O(n²)', 'worst': 'O(n²)'}, '快速排序': {'best': 'O(n log n)', 'average': 'O(n log n)', 'worst': 'O(n²)'}, '归并排序': {'best': 'O(n log n)', 'average': 'O(n log n)', 'worst': 'O(n log n)'}, '堆排序': {'best': 'O(n log n)', 'average': 'O(n log n)', 'worst': 'O(n log n)'}, '计数排序': {'best': 'O(n+k)', 'average': 'O(n+k)', 'worst': 'O(n+k)'}, '基数排序': {'best': 'O(d(n+k))', 'average': 'O(d(n+k))', 'worst': 'O(d(n+k))'} }

def time_complexity_comparison(self): """时间复杂度比较""" print("=== 排序算法时间复杂度比较 ===") print(f"{'算法名称':<12} {'最好情况':<15} {'平均情况':<15} {'最坏情况':<15}") print("-" * 60)

for name, complexity in self.algorithms.items(): print(f"{name:<12} {complexity['best']:<15} {complexity['average']:<15} {complexity['worst']:<15}")

return self.algorithms

def space_complexity_analysis(self): """空间复杂度分析""" print("\n=== 排序算法空间复杂度分析 ===")

space_complexity = { '冒泡排序': 'O(1)', '选择排序': 'O(1)', '插入排序': 'O(1)', '快速排序': 'O(log n)', # 递归栈空间 '归并排序': 'O(n)', # 需要额外数组 '堆排序': 'O(1)', '计数排序': 'O(k)', # k为数据范围 '基数排序': 'O(n+k)' # 需要额外空间 }

print(f"{'算法名称':<12} {'空间复杂度':<15} {'说明':<30}") print("-" * 60)

explanations = { '冒泡排序': '原地排序，只需常数额外空间', '选择排序': '原地排序，只需常数额外空间', '插入排序': '原地排序，只需常数额外空间', '快速排序': '递归调用需要栈空间', '归并排序': '需要与原数组等大的辅助数组', '堆排序': '原地排序，只需常数额外空间', '计数排序': '需要计数数组，大小取决于数据范围', '基数排序': '需要桶和临时数组' }

for name, space in space_complexity.items(): print(f"{name:<12} {space:<15} {explanations[name]:<30}")

return space_complexity

def performance_measurement_demo(self): """性能测量演示""" print("\n=== 性能测量演示 ===")

import time import random

# 生成测试数据 sizes = [100, 500, 1000]

def bubble_sort(arr): """冒泡排序""" n = len(arr) for i in range(n): for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr

def insertion_sort(arr): """插入排序""" for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and arr[j] > key: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key return arr

algorithms = { '冒泡排序': bubble_sort, '插入排序': insertion_sort, 'Python内置': sorted }

print(f"{'数据规模':<10} {'冒泡排序':<12} {'插入排序':<12} {'Python内置':<12}") print("-" * 50)

for size in sizes: times = {}

for name, func in algorithms.items(): # 生成随机数据 data = [random.randint(1, 1000) for _ in range(size)]

# 测量时间 start_time = time.time() if name == 'Python内置': result = func(data) else: result = func(data.copy()) end_time = time.time()

times[name] = end_time - start_time

print(f"{size:<10} {times['冒泡排序']:<12.6f} {times['插入排序']:<12.6f} {times['Python内置']:<12.6f}")

return times

def demonstrate_performance_analysis(self): """演示性能分析""" time_comp = self.time_complexity_comparison() space_comp = self.space_complexity_analysis() perf_measure = self.performance_measurement_demo()

print("\n=== 性能分析总结 ===") print("1. 时间复杂度是算法效率的主要指标") print("2. 空间复杂度影响内存使用") print("3. 实际性能还受到常数因子、缓存等因素影响") print("4. 选择算法需要综合考虑时间、空间和稳定性")

return time_comp, space_comp, perf_measure

# 演示性能分析 performance_demo = SortingPerformanceAnalysis() performance_demo.demonstrate_performance_analysis()

"""排序算法的应用场景"""

def __init__(self): self.scenarios = { '小规模数据': ['插入排序', '选择排序'], '大规模数据': ['快速排序', '归并排序', '堆排序'], '近似有序': ['插入排序', '冒泡排序'], '稳定性要求': ['归并排序', '插入排序'], '内存限制': ['堆排序', '快速排序'], '特殊数据': ['计数排序', '基数排序', '桶排序'] }

def scenario_analysis(self): """应用场景分析""" print("=== 排序算法应用场景分析 ===")

for scenario, algorithms in self.scenarios.items(): print(f"\n{scenario}:") for algo in algorithms: print(f" - {algo}")

# 详细场景说明 print("\n=== 详细场景说明 ===")

scenarios_detail = { '数据库排序': { '推荐算法': '外部归并排序', '原因': '数据量大，需要稳定性，磁盘I/O优化', '特点': '多路归并，缓冲区管理' }, '实时系统': { '推荐算法': '堆排序', '原因': '时间复杂度稳定，空间复杂度低', '特点': '最坏情况性能可预测' }, '嵌入式系统': { '推荐算法': '插入排序', '原因': '内存占用小，代码简单', '特点': '适合小数据量，资源受限' }, '网络数据': { '推荐算法': '快速排序', '原因': '平均性能优秀，缓存友好', '特点': '分治策略，并行化潜力' } }

for scenario, details in scenarios_detail.items(): print(f"\n{scenario}:") print(f" 推荐算法: {details['推荐算法']}") print(f" 选择原因: {details['原因']}") print(f" 应用特点: {details['特点']}")

return scenarios_detail

def real_world_examples(self): """真实世界的应用示例""" print("\n=== 真实世界应用示例 ===")

# 电商网站商品排序 products = [ {'name': '手机A', 'price': 3999, 'sales': 1500, 'rating': 4.5}, {'name': '手机B', 'price': 2999, 'sales': 2000, 'rating': 4.3}, {'name': '手机C', 'price': 4999, 'sales': 800, 'rating': 4.8}, {'name': '手机D', 'price': 1999, 'sales': 3000, 'rating': 4.0} ]

print("1. 电商网站商品排序:")

# 按价格排序 by_price = sorted(products, key=lambda x: x['price']) print("\n按价格排序（低到高）:") for product in by_price: print(f" {product['name']}: ¥{product['price']}")

# 按销量排序 by_sales = sorted(products, key=lambda x: x['sales'], reverse=True) print("\n按销量排序（高到低）:") for product in by_sales: print(f" {product['name']}: {product['sales']}件")

# 综合排序（评分权重0.4，销量权重0.6） by_score = sorted(products, key=lambda x: x['rating'] * 0.4 + (x['sales']/1000) * 0.6, reverse=True) print("\n综合排序（评分+销量）:") for product in by_score: score = product['rating'] * 0.4 + (product['sales']/1000) * 0.6 print(f" {product['name']}: 综合分 {score:.2f}")

# 学生成绩管理系统 print("\n2. 学生成绩管理系统:")

students = [ {'name': '张三', 'math': 85, 'english': 78, 'total': 163}, {'name': '李四', 'math': 92, 'english': 88, 'total': 180}, {'name': '王五', 'math': 78, 'english': 85, 'total': 163}, {'name': '赵六', 'math': 95, 'english': 82, 'total': 177} ]

# 多级排序：先按总分，再按数学成绩 by_grades = sorted(students, key=lambda x: (-x['total'], -x['math'])) print("\n成绩排名（总分优先，数学次之）:") for i, student in enumerate(by_grades, 1): print(f" {i}. {student['name']}: 总分{student['total']} (数学{student['math']}, 英语{student['english']})")

return by_price, by_sales, by_score, by_grades

def demonstrate_applications(self): """演示排序算法应用""" scenario_analysis = self.scenario_analysis() real_examples = self.real_world_examples()

print("\n=== 应用总结 ===") print("1. 选择排序算法需要考虑:") print(" - 数据规模和特征") print(" - 性能要求（时间/空间）") print(" - 稳定性需求") print(" - 系统环境限制")

print("\n2. 实际应用中的考虑因素:") print(" - 业务逻辑的复杂性") print(" - 用户体验要求") print(" - 系统资源约束") print(" - 可维护性和扩展性")

return scenario_analysis, real_examples

# 演示排序算法应用 applications_demo = SortingApplications() applications_demo.demonstrate_applications()

"""软考排序相关考点"""

def __init__(self): self.key_concepts = { '排序定义': '将一组数据按某种顺序重新排列的过程', '稳定性': '相等元素的相对位置在排序后保持不变', '内部排序': '数据完全在内存中进行的排序', '外部排序': '数据量太大，需要借助外存的排序', '比较排序': '基于元素间比较的排序算法', '非比较排序': '不基于元素比较的排序算法' }

def theoretical_points(self): """理论考点总结""" print("=== 软考理论考点 ===")

for concept, definition in self.key_concepts.items(): print(f"{concept}: {definition}")

print("\n重要理论点:") print("1. 比较排序的理论下界是 O(n log n)") print("2. 稳定排序算法: 插入、冒泡、归并") print("3. 不稳定排序算法: 选择、快速、堆") print("4. 原地排序算法: 插入、选择、冒泡、快速、堆") print("5. 非原地排序算法: 归并、计数、基数")

return self.key_concepts

def exam_questions_examples(self): """考试题型示例""" print("\n=== 典型考试题型 ===")

print("1. 选择题示例:") print(" 下列排序算法中，哪个是稳定的？

") print(" A. 快速排序 B. 堆排序 C. 归并排序 D. 选择排序") print(" 答案: C")

print("\n2. 填空题示例:") print(" 快速排序的平均时间复杂度是 ______，最坏时间复杂度是 ______") print(" 答案: O(n log n), O(n²)")

print("\n3. 应用题示例:") print(" 有一组数据 [5, 2, 8, 1, 9]，使用插入排序，写出每一步的结果")

# 演示插入排序过程 data = [5, 2, 8, 1, 9] print(f" 初始: {data}")

for i in range(1, len(data)): key = data[i] j = i - 1 while j >= 0 and data[j] > key: data[j + 1] = data[j] j -= 1 data[j + 1] = key print(f" 第{i}步: {data}")

print("\n4. 算法设计题示例:") print(" 设计一个算法，在O(n)时间内对0-100范围的整数进行排序") print(" 答案: 使用计数排序")

return data

def demonstrate_exam_points(self): """演示软考考点""" theoretical = self.theoretical_points() examples = self.exam_questions_examples()

return theoretical, examples

# 演示软考考点 exam_demo = SoftwareExamPoints() exam_demo.demonstrate_exam_points()