%20(2).svg)
项目简介
本项目实现基于双调排序（Bitonic Sort）的算法，用于对分段数据排序。双调排序是数据无关的排序算法，适合并行计算，如GPU和FPGA。项目实现基本递归双调排序，还完成多个加分挑战，具备非递归实现、内存高效、可并行等特性。
项目的主要特性和功能
- 双调排序算法：实现核心算法，支持对任意长度数组排序，通过填充将非2的幂次长度数组转换为2的幂次长度数组。
- 分段排序：支持分段数据排序，保持段间顺序不变，仅对段内数据排序。
- 非递归实现：以非递归方式实现双调排序，避免递归调用的性能开销。
- 内存高效：不使用动态内存分配，用固定长度大数组存储数据，避免内存碎片和动态分配开销。
- 可并行：所有时间复杂度为O(n)以上的代码写在for循环中，循环顺序可任意改变，适合并行计算。
- 鲁棒性：输入数据含NaN时，保证除NaN以外的数据正确排序，NaN个数保持不变。
安装使用步骤
假设用户已下载本项目的源码文件。
1. 编译代码：使用C++编译器（如g++）编译源码文件。
bash
g++ segmentedBitonicSort.cpp -o segmentedBitonicSort
2. 运行程序：运行编译后的可执行文件，并提供输入数据。
bash
./segmentedBitonicSort
3. 输入数据格式：输入数据应包含浮点数数组data、段ID数组seg_id、段起始位置数组seg_start、数据长度n和段数m。
c++
float data[5] = {0.8, 0.2, 0.4, 0.6, 0.5};
int seg_id[5] = {0, 0, 1, 1, 1};
int seg_start[3] = {0, 2, 5};
int n = 5;
int m = 2;
4. 输出结果：程序将输出排序后的数据，保持段间顺序不变，段内数据有序。
下载地址
点击下载 【提取码: 4003】【解压密码: www.makuang.net】