辅助测试函数

文中使用的图片来自慕课网课程算法与数据结构

本部分构建一些辅助测试函数, 用于辅助我们测试算法性能.

生成随机数组

#include <iostream>
#include <ctime>
#include <cassert>

using namespace std;

namespace SortTestHelper {
    // 生成有 n 个元素的随机数组, 每个元素的随机范围为 [rangeL, rangeR]
    int *generateRandomArray(int n, int rangeL, int rangeR) {
        assert(rangeL <= rangeR);
        int *arr = new int[n];
        srand(time(nullptr));
        for (int i = 0; i < n; i++) {
            // rand() 返回 0 到 RAND_MAX 之间的伪随机值
            // RAND_MAX 至少为 32767
            arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
        }
        return arr;
    }

    template<typename T>
    void printArray(T arr[], int n) {
        for (int i = 0; i < n; ++i) {
            cout << arr[i] << " ";
        }
        cout << endl;
        return;
    }
}

上面是两个辅助测试函数, 一个是随机生成测试数组, 一个是打印输出, 都非常简单.

生成近乎有序的数组

int *generateNearlyOrderedArray(int n, int swapTimes) {
    int *arr = new int[n];
    for (int i = 0; i < n; ++i) {
        arr[i] = i;
    }
    srand(time(nullptr));
    for (int j = 0; j < swapTimes; ++j) {
        int posx = rand() % n;
        int posy = rand() % n;
        swap(arr[posx], arr[posy]);
    }
    return arr;
}

上面代码生成一个近乎有序的数组, 通过对一个有序数组进行交换的方式生成, 其中 swapTimes 决定了交换的次数.

验证排序有效性

验证排序有效性只需要比较

template<typename T>
bool isSorted(T arr[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        if (arr[i] > arr[i + 1]) {
            return false;
        }
    }
    return true;
}

测试算法性能 (运行时长)

template<typename T>
void testSort(const string &sortName, void(*sort)(T[], int), T arr[], int n) {
    // 记录开始时间
    clock_t startTime = clock();
    sort(arr, n);
    // 记录结束时间
    clock_t endTime = clock();
    assert(isSorted(arr, n));
    // 输出测试信息
    cout << sortName << " : " << double(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
}

复制数组

int *copyArray(int a[], int n) {
    int *arr = new int[n];
    copy(a, a + n, arr);
    return arr;
}