一步一步学习数据结构和算法(零) 排序算法辅助测试函数
2019-06-13 本文已影响3人
mlya
辅助测试函数
文中使用的图片来自慕课网课程算法与数据结构
本部分构建一些辅助测试函数, 用于辅助我们测试算法性能.
生成随机数组
#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;
}