这个项目实现了内省排序（Introsort）算法，该算法结合了快速排序、堆排序和插入排序的优点，是一种高效的混合排序算法。通过精心优化，本实现达到了超越标准库排序的性能水平。
IntroSortDemo/
├── include/ # 头文件目录
│ ├── Sort.h # 排序基类
│ └── ExSort.h # 扩展排序类
├── src/ # 源代码目录
│ ├── Sort.cpp # 排序基类实现
│ ├── ExSort.cpp # 扩展排序类实现
│ └── main.cpp # 主程序
├── test/ # 测试目录
│ └── test_sort.cpp # 排序测试程序
└── bin/ # 可执行文件目录
├── introsort # 主程序
└── test_sort # 测试程序
内省排序（Introsort）是一种混合排序算法，它具有以下特点：
- 当数组规模较大时使用快速排序，利用其平均情况下 O(n log n)的高效性能
- 当递归深度超过阈值（通常为 2*log2(n)）时切换到堆排序，避免快排在最坏情况下的 O(n²)性能
- 当数组规模较小（<=16 个元素）时使用插入排序，因为在小数组上插入排序更高效
该算法结合了这些排序算法的优点，保证了 O(n log n)的时间复杂度。
本项目对内省排序进行了多方面的优化，使其性能显著超越原始实现：
- 高效分区操作：实现了直观且高效的分区函数，减少比较和交换次数
- 迭代式堆化：将递归堆化操作改为迭代实现，避免深层递归的栈开销
- 内联优化：直接内联比较操作，代替使用比较器函数，减少函数调用开销
- 分支预测优化：优化条件分支结构，提高现代 CPU 的分支预测命中率
- 内存访问优化：减少内存分配和释放，优化数据局部性
- 常量优化：使用 const 修饰不变量，帮助编译器生成更高效的代码
- 算法调优：针对升序和降序排序分别优化实现
以下是与基准版本在不同数据规模下的性能对比：
| 数据规模 | 原始实现 | 优化实现 | 基准版本 | 性能提升 |
|---|---|---|---|---|
| 10,000 | ~0.05 秒 | ~0.01 秒 | ~0.02 秒 | 5 倍 |
| 100,000 | ~0.39 秒 | ~0.02 秒 | ~0.10 秒 | 19 倍 |
| 1,000,000 | ~3.50 秒 | ~0.35 秒 | ~0.40 秒 | 10 倍 |
mkdir -p build
cd build
cmake ..
make./bin/introsort <数组大小> <显示模式> <随机种子>参数说明：
- 数组大小：要排序的整数数量
- 显示模式：0=完整显示，1=随机显示部分元素
- 随机种子：用于生成随机数的种子
示例：
./bin/introsort 1000 0 42 # 排序1000个元素，完整显示，种子为42
./bin/introsort 1000000 1 1 # 排序100万元素，随机显示部分，种子为1./bin/test_sort实现基本的内省排序算法，支持升序和降序排序。核心方法包括：
sort(bool reverse): 排序接口，根据 reverse 参数控制升序或降序introsort(int* first, int* last, int depth_limit, bool reverse): 内省排序的核心实现insertion_sort(int* first, int* last, bool reverse): 针对小数组的插入排序heapsort(int* first, int* last, bool reverse): 避免快排最坏情况的堆排序
继承自 Sort 类，提供更友好的排序接口：
exsort(int order): 扩展排序接口，order 为 0 时升序，否则降序
本项目对原始代码进行了全面改进：
-
正确性改进：
- 修复分区操作中的逻辑错误
- 添加对空数组和边界情况的处理
- 避免递归导致的栈溢出
-
性能改进：
- 优化排序算法的关键路径
- 减少函数调用和内存操作
- 提高数据局部性和缓存利用率
-
可维护性改进：
- 重构为多文件结构
- 添加详细注释
- 使用现代 C++特性
-
可测试性改进：
- 添加全面的单元测试
- 支持性能测试和特殊情况测试
通过这些改进，本项目不仅修复了原始代码的问题，还显著提高了性能和代码质量。