這一節(jié) 我們將實(shí)現(xiàn)一個(gè)很有意思 非常重要的 可以幫助我們測(cè)試算法性能的函數(shù)
要評(píng)測(cè)算法性能 最簡(jiǎn)單的思路就是看不同算法在特定數(shù)據(jù)集上執(zhí)行時(shí)間的長(zhǎng)短（注意 需要在不同算法跑的數(shù)據(jù)集完全一致，因?yàn)閿?shù)據(jù)本身結(jié)構(gòu)也會(huì)影響算法執(zhí)行用時(shí)）
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個(gè)元素的隨機(jī)數(shù)組,每個(gè)元素的隨機(jī)范圍為[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數(shù)組的所有內(nèi)容
template<typename T>
void printArray(T arr[], int n) {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return;
}
// 判斷arr數(shù)組是否有序
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;
}
// 測(cè)試sort排序算法排序arr數(shù)組所得到結(jié)果的正確性和算法運(yùn)行時(shí)間
// * 使用VS編碼的同學(xué), 對(duì)于函數(shù)指針的寫法和調(diào)用方法可能和課程中介紹的有所不同;
// * 并且不同版本的VS, 其具體語(yǔ)法可能也有差異, 這是因?yàn)閂S的編譯器不完全是按照C++的標(biāo)準(zhǔn)實(shí)現(xiàn)的;
// * 本課程按照C++11的標(biāo)準(zhǔn)進(jìn)行書(shū)寫。對(duì)于VS編譯器帶來(lái)的語(yǔ)法差異, 希望同學(xué)們可以自己在網(wǎng)上查找相關(guān)資料解決;
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++結(jié)果：
（輸出對(duì)含有100000個(gè)元素的數(shù)組排序用時(shí)12秒排序完成）
排序用時(shí).png
