这一节 我们将实现一个很有意思 非常重要的 可以帮助我们测试算法性能的函数
要评测算法性能 最简单的思路就是看不同算法在特定数据集上执行时间的长短（注意 需要在不同算法跑的数据集完全一致，因为数据本身结构也会影响算法执行用时）
C++代码：
SortTestHelper.h:
#ifndef INC_03_SELECTION_SORT_DETECT_PERFORMANCE_SORTTESTHELPER_H
#define INC_03_SELECTION_SORT_DETECT_PERFORMANCE_SORTTESTHELPER_H
#include <iostream>
#include <ctime>
#include <cassert>
#include <string>
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(NULL));
for (int i = 0; i < n; i++)
arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
return arr;
}
// 打印arr数组的所有内容
template<typename T>
void printArray(T arr[], int n) {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return;
}
// 判断arr数组是否有序
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;
}
// 测试sort排序算法排序arr数组所得到结果的正确性和算法运行时间
// * 使用VS编码的同学, 对于函数指针的写法和调用方法可能和课程中介绍的有所不同;
// * 并且不同版本的VS, 其具体语法可能也有差异, 这是因为VS的编译器不完全是按照C++的标准实现的;
// * 本课程按照C++11的标准进行书写。对于VS编译器带来的语法差异, 希望同学们可以自己在网上查找相关资料解决;
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;
return;
}
};
#endif //INC_03_SELECTION_SORT_DETECT_PERFORMANCE_SORTTESTHELPER_H
main.cpp:
#include <iostream>
#include "SortTestHelper.h"
using namespace std;
template<typename T>
void selectionSort(T arr[], int n) {
for (int i = 0; i < n; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++)
if (arr[j] < arr[minIndex])
minIndex = j;
swap(arr[i], arr[minIndex]);
}
}
int main() {
int n = 100000;
int *arr = SortTestHelper::generateRandomArray(n, 0, n);
SortTestHelper::testSort("Selection Sort", selectionSort, arr, n);
delete[] arr;
return 0;
}
C++结果：
（输出对含有100000个元素的数组排序用时12秒排序完成）
排序用时.png
