排序算测试框架

下面是一个简单的 C++ 排序算法测试框架，旨在帮助你测试不同的排序算法。该框架能够比较排序算法的执行时间和准确性。你可以根据需求扩展不同的排序算法，方便进行对比和性能测试。

1. 设计思路

• 排序算法接口：定义一个虚拟接口，所有排序算法都实现该接口。
• 排序算法实现：实现常见的排序算法（如冒泡排序、快速排序等）。
• 测试框架：编写一个测试框架，能够接收不同的排序算法、生成测试数据并验证结果。
• 性能测试：记录排序时间，方便对比不同算法的效率。

2. 完整代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <cassert>
#include <random>

// 排序算法接口
class Sorter {
public:
    virtual void sort(std::vector<int>& arr) = 0;
    virtual std::string name() const = 0;
    virtual ~Sorter() = default;
};

// 冒泡排序实现
class BubbleSort : public Sorter {
public:
    void sort(std::vector<int>& arr) override {
        for (size_t i = 0; i < arr.size(); ++i) {
            for (size_t j = 0; j < arr.size() - i - 1; ++j) {
                if (arr[j] > arr[j + 1]) {
                    std::swap(arr[j], arr[j + 1]);
                }
            }
        }
    }

    std::string name() const override {
        return "BubbleSort";
    }
};

// 快速排序实现
class QuickSort : public Sorter {
public:
    void quickSort(std::vector<int>& arr, int low, int high) {
        if (low < high) {
            int pivot = partition(arr, low, high);
            quickSort(arr, low, pivot - 1);
            quickSort(arr, pivot + 1, high);
        }
    }

    void sort(std::vector<int>& arr) override {
        quickSort(arr, 0, arr.size() - 1);
    }

    std::string name() const override {
        return "QuickSort";
    }

private:
    int partition(std::vector<int>& arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; ++j) {
            if (arr[j] < pivot) {
                ++i;
                std::swap(arr[i], arr[j]);
            }
        }
        std::swap(arr[i + 1], arr[high]);
        return i + 1;
    }
};

// 测试框架
class SortTester {
public:
    SortTester(Sorter* sorter) : sorter_(sorter) {}

    // 生成随机数组
    std::vector<int> generateRandomArray(size_t size) {
        std::vector<int> arr(size);
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<> dist(0, 1000);
        for (size_t i = 0; i < size; ++i) {
            arr[i] = dist(gen);
        }
        return arr;
    }

    // 打印数组
    void printArray(const std::vector<int>& arr) {
        for (int num : arr) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    }

    // 测试排序算法的正确性
    void testSorting() {
        // 生成一个随机数组
        std::vector<int> arr = generateRandomArray(10);

        std::cout << "Original array: ";
        printArray(arr);

        // 复制数组用于验证结果
        std::vector<int> arrCopy = arr;

        // 排序
        sorter_->sort(arr);

        // 验证排序结果是否正确
        std::sort(arrCopy.begin(), arrCopy.end());
        assert(arr == arrCopy && "Sorting failed!");

        std::cout << sorter_->name() << " passed the test!" << std::endl;
    }

    // 性能测试
    void testPerformance() {
        // 生成一个随机数组
        std::vector<int> arr = generateRandomArray(100000);

        auto start = std::chrono::high_resolution_clock::now();
        sorter_->sort(arr);
        auto end = std::chrono::high_resolution_clock::now();

        std::chrono::duration<double> duration = end - start;
        std::cout << sorter_->name() << " sorting time: " << duration.count() << " seconds" << std::endl;
    }

private:
    Sorter* sorter_;
};

// 主函数
int main() {
    // 创建排序算法对象
    BubbleSort bubbleSort;
    QuickSort quickSort;

    // 创建测试框架对象
    SortTester bubbleTester(&bubbleSort);
    SortTester quickTester(&quickSort);

    // 测试排序算法的正确性
    std::cout << "Testing Bubble Sort:" << std::endl;
    bubbleTester.testSorting();

    std::cout << "Testing Quick Sort:" << std::endl;
    quickTester.testSorting();

    // 性能测试
    std::cout << "\nTesting Performance:" << std::endl;
    bubbleTester.testPerformance();
    quickTester.testPerformance();

    return 0;
}

3. 代码解释

3.1 Sorter 接口

• Sorter 类是一个抽象基类，定义了所有排序算法的通用接口。
• sort() 方法接收一个 std::vector<int> 类型的数组并对其进行排序。
• name() 方法返回排序算法的名称，用于输出日志。

3.2 排序算法实现

• BubbleSort 类实现了冒泡排序算法。
• QuickSort 类实现了快速排序算法。

3.3 SortTester 测试框架

• SortTester 是用于测试排序算法的类。它接收一个排序算法对象，生成随机数据，并执行排序。
• generateRandomArray() 方法生成随机数组。
• testSorting() 方法验证排序的正确性，通过与 std::sort 结果比较来确保排序的准确性。
• testPerformance() 方法测试排序算法的性能，计算排序所花费的时间。

3.4 主函数

• 主函数中创建了两个排序算法对象（冒泡排序和快速排序）和两个测试框架对象。
• 首先测试排序算法的正确性，再进行性能测试。

4. 运行效果

测试输出示例：

Testing Bubble Sort:
Original array: 324 876 54 12 23 97 645 100 80 11 
BubbleSort passed the test!

Testing Quick Sort:
Original array: 324 876 54 12 23 97 645 100 80 11 
QuickSort passed the test!

Testing Performance:
BubbleSort sorting time: 5.2 seconds
QuickSort sorting time: 0.16 seconds

5. 如何扩展

• 你可以轻松地扩展 Sorter 类来实现更多的排序算法，例如归并排序、插入排序等。
• 通过修改 generateRandomArray 方法，可以调整数组的大小或随机范围，以便进行不同规模的数据测试。
• 可以修改 testPerformance() 方法，采用更高级的性能测试方式，如多次运行并取平均值等。

为了构建你编写的排序算法测试框架，下面是一个简单的 CMakeLists.txt 配置文件。它适用于你提供的 C++ 代码，并允许你使用 CMake 构建项目。

CMakeLists.txt

# 设置最低 CMake 版本
cmake_minimum_required(VERSION 3.10)

# 项目名称
project(SortAlgorithmsTester)

# 设置 C++ 标准为 C++11（或者可以设置为 C++17、C++20）
set(CMAKE_CXX_STANDARD 11)
set(CMAKE_CXX_STANDARD_REQUIRED True)

# 添加可执行文件
add_executable(SortAlgorithmsTester main.cpp)

# 可以选择添加编译选项，例如开启编译优化
# target_compile_options(SortAlgorithmsTester PRIVATE -O2)

# 如果需要链接其他库，可以在这里进行链接，例如：pthread
# target_link_libraries(SortAlgorithmsTester PRIVATE pthread)

# 可选：启用测试功能
enable_testing()

解释：

• cmake_minimum_required(VERSION 3.10)：指定CMake的最低版本要求。
• project(SortAlgorithmsTester)：定义项目名称。
• set(CMAKE_CXX_STANDARD 11)：设置C++标准为 C++11。如果你使用的是更高版本的标准（例如 C++17），可以将其修改为 C++17 或者 C++20。
• add_executable(SortAlgorithmsTester main.cpp)：将 main.cpp 编译为一个可执行文件 SortAlgorithmsTester。这里假设你将上述代码保存在 main.cpp 文件中。
• enable_testing()：启用 CMake 测试功能，如果你打算添加单元测试或集成测试，可以使用该选项。

目录结构

假设你的项目目录结构如下：

SortAlgorithmsTester/
├── CMakeLists.txt
└── main.cpp

• CMakeLists.txt：上述配置文件。
• main.cpp：你的主程序文件（包括排序算法和测试框架）。

构建项目

1. 创建构建目录：

   在项目根目录下，创建一个单独的构建目录（建议这样做，以免将构建文件混合到源代码中）：

   mkdir build
   cd build

2. 生成构建系统：

   使用 CMake 生成构建系统：

   cmake ..

   这将使用 CMakeLists.txt 文件来生成适合你平台的构建文件（如 Makefile 或 Visual Studio 工程）。

3. 构建项目：

   使用 make 构建项目：

   make

   这将编译 main.cpp 文件并生成可执行文件 SortAlgorithmsTester。

4. 运行程序：

   在构建目录下运行生成的可执行文件：

   ./SortAlgorithmsTester

   你应该能够看到程序输出的排序结果和性能测试结果。

其他建议

• 如果你的项目包含多个源文件，可以使用 add_executable() 连接多个源文件。例如，假设你有一个 sorts.cpp 文件来实现排序算法，可以将它加入 add_executable()：

  add_executable(SortAlgorithmsTester main.cpp sorts.cpp)

• 如果你想将排序算法代码分开到不同的目录（例如 src 和 include），你可以指定源代码和头文件目录：

  include_directories(include)
  add_executable(SortAlgorithmsTester src/main.cpp src/sorts.cpp)