北京书展,哈多利系博美犬价格,酒色国际
最近在学习排序算法的时候,需要利用程序自动生成测试数据,代码和思路整理在这篇文章里面。
文章图片来源于 github,网速不佳的朋友。
顺便软广一下个人技术小站:。欢迎常来 ♪(^∇^*)
因为会被很多排序算法调用,所以,数据自动生成代码应该放在.h
头文件中。为了防止命名冲突,函数被封装在“命名空间”中(代码中命名空间是: sorttesthelper
)。
而对于排序来说,自动生成数据的类型需要有以下几种:
[a, b]
范围内的n
个随机数据,比如:1、2、100、-1...n
个近乎有序的数据,比如:1、2、3、7、5、6、4...n
个近乎相同的数据,比如:1、1、1、2、2、2、2、2...除此之外,还需要数组浅拷贝、打印的函数,以及验证是否排序成功和测试排序时间的函数。
srand(time(null))
与 rand()
: 设立随机种子,生成随机数clock()
: 用来算法运行前后的计算时钟周期差值,再除以clocks_per_sec
即为运行秒数。其中rand()
函数能生成 0 到max_int
之间的随机整数。如果想生成[0, n)
之间的整数,需要取余操作:int x = rand() % n;
;如果想生成[left, right]
之间的整数,需要进行偏移:int x = rand() % (right - left + 1) + left;
// // created by godbmw.com on 2018/9/11. // #ifndef basesort_sorthelper_h #define basesort_sorthelper_h #include <iostream> #include <string> #include <ctime> #include <cassert> using namespace std; namespace sorttesthelper { // 生成[left, right]范围内n个随机数 template <typename t> t* generaterandomarray(int n, int left, int right) { assert( left <= right ); t *arr = new t[n]; srand(time(null)); // set random seed for(int i = 0; i < n; i++) { arr[i] = rand() % (right - left + 1) + left; } return arr; } // 生成[0, n)范围内n个近乎有序的随机数 template <typename t> t* generatenearlyorderedarray(int n, int swap_times) { t *arr = new t[n]; srand(time(null)); // 先生成长度为n的有序数组 for(int i = 0; i < n; i++) { arr[i] = i + 1; } // 随机选取其中2个数据,交换 swap_times 次 for(int i = 0; i < swap_times; i++) { int pos_x = rand() % n; int pos_y = rand() % n; swap(arr[pos_x], arr[pos_y]); } return arr; } template <typename t> t* copyarray(t arr[], int length) { t* brr = new t[length]; // 注意检查brr数组大小 copy(arr, arr + length, brr); return brr; } template <typename t> void printarray(t arr[], int length) { for(int i = 0; i < length; i++) { cout<< arr[i] << " "; } cout<< endl; return; } template <typename t> bool issorted(t arr[], int length) { for(int i = 0; i < length-1; i++) { if(arr[i] > arr[i + 1]) { return false; } } return true; } // 第三个参数是函数指针,传入后,可以在本函数内运行被传入的函数 template <typename t> void testsort(t arr[], int length, void(*sort)(t[], int), string name) { clock_t starttime = clock(); sort(arr, length); clock_t endtime = clock(); assert(issorted(arr, length)); cout << name << " : " << double(endtime - starttime) / clocks_per_sec << " seconds" << endl; // endtime - starttime: 时钟周期 return; } } #endif //basesort_sorthelper_h
我们没有实现第二部分所说的 生成n
个近乎相同的数据,比如:1、1、1、2、2、2、2、2...。因为可以借助 generaterandomarray
函数,比如:sorttesthelper::generaterandomarray(10000, 0, 10)
。生成[0,10]区间内 10000 个整数,那么不就是近乎相同的吗?
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论