C++ 排序算法測試代碼編寫指南：覆蓋率、邊界、性能三維驗證

題目拆解

要求實現插入排序、歸併排序、快速排序三種算法，並編寫測試代碼驗證：

1. 正確性：輸出遍歷結果，保證所有分支語句被覆蓋
2. 算法複雜度：理論分析 + 實測數據對比
3. 效率：輸出具體耗時

測試用例設計原則：從「覆蓋所有路徑」到「覆蓋所有分支」

路徑覆蓋 vs 分支覆蓋

int foo(int x, int y, int z) {
    if (z == 0) { x = 1; y = -1; }
    if (x > 0) {
        if (y > 0) return 1;
        else return 2;
    } else {
        if (y > 0) return 3;
        else return 4;
    }
}

• 路徑覆蓋：需 8 個用例覆蓋所有分支組合（2×2×2）
• 分支覆蓋：僅需 5 個用例讓每個 if/else 兩側各執行一次
• 實際工程中**分支覆蓋率 100% 是底線**，路徑覆蓋指數級爆炸不可行

排序算法關鍵測試數據集

測試框架代碼骨架

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

using Clock = std::chrono::high_resolution_clock;
using Ms = std::chrono::milliseconds;

// 待測算法接口
void insertSort(std::vector<int>& a);
void mergeSort(std::vector<int>& a);
void quickSort(std::vector<int>& a);

// 驗證有序性
bool isSorted(const std::vector<int>& a) {
    return std::is_sorted(a.begin(), a.end());
}

// 單次測試
template<typename Fn>
long long benchmark(Fn sortFn, std::vector<int> data, const char* name) {
    auto t0 = Clock::now();
    sortFn(data);
    auto t1 = Clock::now();
    bool ok = isSorted(data);
    std::cout << name << ": " << (ok ? "PASS" : "FAIL") 
              << ", time=" << std::chrono::duration_cast<Ms>(t1-t0).count() << "ms\n";
    return ok ? 0 : 1;
}

int main() {
    std::vector<std::pair<std::string, std::vector<int>>> testCases = {
        {"empty", {}},
        {"single", {42}},
        {"sorted", {1,2,3,4,5}},
        {"reversed", {5,4,3,2,1}},
        {"duplicates", {3,1,4,1,5,9,2,6,5}},
        {"near_sorted", {1,2,3,5,4,6,7,8,9,10}},
    };

    // 小規模正確性驗證（含輸出遍歷結果）
    for (auto& tc : testCases) {
        auto v = tc.second;
        insertSort(v);
        std::cout << "InsertSort [" << tc.first << "]: ";
        for (int x : v) std::cout << x << ' ';
        std::cout << '\n';
        // 同理 mergeSort, quickSort...
    }

    // 大規模性能基準
    std::mt19937 rng(42);
    std::uniform_int_distribution<int> dist(0, 1000000);
    std::vector<int> big(100000);
    for (int& x : big) x = dist(rng);

    benchmark(insertSort, big, "InsertSort");
    benchmark(mergeSort,  big, "MergeSort");
    benchmark(quickSort,  big, "QuickSort");

    return 0;
}

複雜度理論 vs 實測對比表

進階驗證：分支覆蓋率工具

編譯加旗標：g++ -fprofile-arcs -ftest-coverage -O0 test.cpp -o test
運行 ./test 生成 .gcda，用 lcov / gcovr 生成 HTML 報告，直觀查看每個 if/else 是否被執行。

核心心法

「測試不是為了證明代碼對，而是為了找出代碼錯。構造極端、邊界、惡意數據，比隨機大數據更能暴露缺陷。」