第一章 排序算法基础
#
1.1 排序基本概念
#
- 排序的定义与分类
- 稳定性与原地排序
- 时间复杂度与空间复杂度
- 比较排序与非比较排序
1.2 算法分析基础
#
- 渐进符号与复杂度分析
- 最坏情况与平均情况分析
- 递归关系求解
- 比较树模型
第二章 简单排序算法
#
2.1 冒泡排序
#
- 算法原理与实现
- 优化版本（标志位优化）
- 复杂度分析
- 适用场景与局限性
2.2 选择排序
#
- 算法流程与实现
- 稳定性分析
- 比较次数与交换次数
- 实际应用场景
2.3 插入排序
#
- 直接插入排序
- 二分插入排序
- 希尔排序
- 自适应特性分析
第三章 高效比较排序算法
#
3.1 快速排序
#
- 分治策略与分区过程
- 递归实现与迭代实现
- 枢纽元素选择策略
- 三路快速排序
3.2 归并排序
#
- 分治思想与合并过程
- 自顶向下与自底向上实现
- 外部排序应用
- 稳定性证明
3.3 堆排序
#
- 二叉堆数据结构
- 建堆过程与堆调整
- 原地排序特性
- 优先队列应用
第四章 特殊比较排序算法
#
4.1 树形排序
#
4.2 其他比较排序
#
第五章 比较排序理论分析
#
5.1 比较排序下界
#
- 决策树模型
- 信息论下界证明
- 比较次数下界
- 最优排序算法
5.2 实际性能分析
#
- 缓存友好性
- 分支预测影响
- 实际运行时间测量
- 硬件特性考虑
第六章 排序算法比较与应用
#
6.1 算法性能对比
#
- 时间复杂度对比表
- 空间复杂度对比
- 稳定性对比
- 实际测试数据
6.2 应用场景选择
#
- 小规模数据排序
- 大规模数据排序
- 部分有序数据
- 特殊数据类型
第七章 优化与改进
#
7.1 混合排序算法
#
7.2 工程实践优化
#
- 内存访问优化
- 并行化排序
- 预处理技术
- 特定硬件优化
第八章 扩展与相关主题
#
8.1 非比较排序
#
8.2 排序相关问题
#