4.测试算法的性能

本例中测试选择排序的性能. 用选择排序对一数组进行排序，该数组为长度为10000，每个数组元素的大小是[0,10000]中随机的一个.

main.cpp:
#include<iostream>
#include<algorithm>
#include"temp.h"
using namespace std;

template<typename T>
void selectionSort(T arr[], int n){
    for(int i = 0; i < n-1; 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 = 10000;
    int *arr = SortTestHelper::generateRandomArray(N,0,N);
    SortTestHelper::testSort("Selection Sort", selectionSort, arr, N); 
    delete[]arr;
    return 0;
}

test.h:
#ifndef _TEMP_H
#define _TEMP_H
#include <iostream>
#include <ctime>
#include <cassert>
#include <algorithm>
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;
    }
    template<typename T>
    void PrintArray(T arr[], int n){
        for( int i = 0; i < n; i++)
            cout << arr[i] << " ";
        cout << endl;
        return;
    }
    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;
    }
    /*
    * endTime - startTime返回的是运行了几个时钟周期
    * CLOCK_PER_SEC是标准库中定义的宏，表示每秒钟运行的时钟周期的个数
    */
    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