最近在學習排序演算法的時候，需要利用程式自動生成測試數據，代碼和思路整理在這篇文章裡面。 文章圖片來源於 GitHub，網速不佳的朋友 "請點我看原文" 。 順便軟廣一下個人技術小站： "https://godbmw.com" 。歡迎常來 ♪\(^∇^\ \) 1. 設計思路 因為會被很多排序演算法調用 ...
最近在學習排序演算法的時候，需要利用程式自動生成測試數據，代碼和思路整理在這篇文章裡面。
文章圖片來源於 GitHub，網速不佳的朋友請點我看原文。
順便軟廣一下個人技術小站：https://godbmw.com。歡迎常來 ♪(^∇^*)
1. 設計思路
因為會被很多排序演算法調用，所以，數據自動生成代碼應該放在.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...
除此之外，還需要數組淺拷貝、列印的函數，以及驗證是否排序成功和測試排序時間的函數。
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;
3. 代碼實現
//
// 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 個整數，那麼不就是近乎相同的嗎？
