测试算法时,经常使用随机数,针对排序算法测试,建立一个名字空间SortTestHelper
1 namespace SortTestHelper 2 { 3 int* generateRandomArray(int n,int rangeL,int rangeR);//生成随机数组 4 void printArray(int *arr,int n);//打印数组 5 template<typename T> bool isSorted(T *arr,int n);//判断是否成功排序 6 template<typename T> void testSort(string sortName,void(*sort)(T [],int),T arr[],int n);//测试排序时间并打印 7 }
生成随机数组时,三个参数分别为元素个数,元素下限和元素上限。
在这个函数中,默认rangR>rangeL,所以在函数中使用了assert(rangeR>rangeL),如果括号内成立,则继续运行,不成立则打断。
生成随机数的方式是使用srand和rand()配合产生伪随机数序列,rand函数在产生随机数前,需要系统提供的生成伪随机数序列的种子,rand根据这个种子的值产生一系列随机数。如果系统提供的种子没有变化,每次调用rand函数生成的伪随机数序列都是一样的。srand(unsigned seed)通过参数seed改变系统提供的种子值,从而可以使得每次调用rand函数生成的伪随机数序列不同,从而实现真正意义上的“随机”。通常可以利用系统时间来改变系统的种子值,即srand(time(NULL)),可以为rand函数提供不同的种子值,进而产生不同的随机数序列。
1 //生成有n个元素的随机数组,每个数组元素范围为[rangeL,rangeR] 2 int* generateRandomArray(int n,int rangeL,int rangeR) 3 { 4 assert(rangeR>rangeL); 5 int *arr=new int[n]; 6 srand(time(NULL)); 7 for(int i=0;i<n;i++) 8 arr[i]=rand()%(rangeR-rangeL+1)+rangeL; 9 return arr; 10 } 11 12 void printArray(int *arr,int n) 13 { 14 for(int i=0;i<n;i++) 15 cout<<arr[i]<<" "; 16 cout<<endl; 17 }
在使用随机数组生成函数后,为数组分配了地址空间,在测试结束后要加delete[] arr,否则会造成内存泄漏。
判断数组是否排序成功时,构造成了函数模板,进行n-1次循环,如果存在某个元素比其后一个元素大,则返回错误
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; }
测试排序时间时,使用了clock()函数,clock()是C/C++中的计时函数,而与其相关的数据类型是clock_t。
clock tick:时钟计时单元(而不把它叫做时钟滴答次数),一个时钟计时单元的时间长短是由CPU控制的,一个clock tick不是CPU的一个时钟周期,而是C/C++的一个基本计时单位。而与之对应的宏CLOCKS_PER_SEC适用于将计算系统时间类型转换为用户可读的秒时间,包含于头文件ctime中。
1 template<typename T> 2 void testSort(string sortName,void(*sort)(T[],int),T arr[],int n) 3 { 4 clock_t startTime=clock(); 5 sort(arr,n); 6 clock_t endTime=clock(); 7 8 assert(isSorted(arr, n)); 9 cout<<sortName<<":"<<double(endTime-startTime)/CLOCKS_PER_SEC<<"s"<<endl; 10 return; 11 }
在函数中,使用了assert()来确定数组是否排序成功,如果成功则继续运行,不成功则打断。