算法 class 005 （对数器C语言实现）

 对数器的概念：

用来测试你的算法是否正确。

怎么做呢？

        1：比如，写个冒泡排序，作为对比的对象

        2：生成一个随机数 数组，用来测试

        3：用冒泡排序和你想要验证的那个排序算法，同时对这个数组排序，所以这个数组我们需要两份一样的。

        4：需要验证一个验证函数验证

        5：多次生成随机数组，然后排序验证，如果都没有出错，大概率你写的那个排序就是正确的

1、生成随机数组

 1、定义时间时间戳，以及两个变量，一个用来生成数组的长度，一个用来生成每一个元素的大小

2、定义一个变量表示本次的数组范围然后用一个函数来生成这个随机数组

生成随机数组函数

2、拷贝数组

arr1 是生成的随机数组，可以直接使用，也可以多拷贝一份，我这里直接使用，所以两个数组就够了，待会用冒泡排序和插入排序比较。

 拷贝函数

3、排序

 用 冒泡排 arr1; 这俩排序在 class 004文章中

 用 插入排 arr2;

4、写验证函数验证

函数的返回值是 bool类型的，如果为真(fruit 非 0值)，表示你的测试方法这一次通过了

 

验证函数

5、多次测试

只需要再定义一个变量套在外面就行

#define	_CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#if 1;
void Swap(int* arr, int x, int y)
//x y 为下标
{
	int tmp = arr[x];
	arr[x] = arr[y];
	arr[y] = tmp;

}
void BubbleSort(int* arr, int size)//冒泡排序
{
	//if (arr == NULL || size < 2) return;
	for (int i = size - 1; i > 0; i--)
	{	// i 用来放入最大值

		int count = 0;//用来计数，如果提前排好序了，就提前结束
		for (int j = 0; j < i; j++)
		{	// j 用来比较两个数
			if (arr[j] > arr[j + 1])
			{//如果 j 大与 j 后一个数
				Swap(arr, j, j + 1);//就交换
				count++;//计数器加1
			}

		}
		if (count == 0)
			break;
	}
}

void InsertSort(int* arr, int size)//插入排序
{
	//if (arr == NULL || size < 2) return;
	for (int i = 1; i < size; i++)
	{
		for (int j = i; j > 0; j--)
		{
			if (arr[j] < arr[j - 1])
			{
				Swap(arr, j, j - 1);
			}
			else
				j = 0;
		}
	}
}

int* randomArray(n, V)//生成随机数组
{
	int* arr = (int*)malloc(n * sizeof(int));//开辟 n 个int类型的空间
	if (arr == NULL)
	{
		perror("randomArray-malloc::failed");
		exit(EOF);
	}
	for (int i = 0; i < n; i++)//循环 n 次
	{
		arr[i] = rand() % V+1;//每次放入一个大小在 [0 ~ V-1]之间的数

	}
	return arr;//返回该地址
}
int* copyArray(int n,int* arr1)//拷贝数组
{
	int* arr2 = (int*)malloc(n * sizeof(int));//开辟一个 n 个 int 类型的地址
	if (arr2 == NULL)
	{
		perror("randomArray-malloc::failed");
		exit(EOF);
	}
	for (int i = 0; i < n; i++)
	{
		arr2[i] = arr1[i];//将 arr1 中的每一给元素赋值给 arr2，就算拷贝完成了
	}
	return arr2;//返回 arr2 的地址

}

bool sameArray(int* arr1, int* arr2, int n)
{
	for (int i = 0; i < n; i++)
	{
		if (arr1[i] != arr2[i])//每一个元素作比较
			return false;//如果有不一样的就返回 false
	}
	return true;//一个都没有返回 ture
}
void PrintArray(int* arr,int*arr2 ,int size)
{
	for (int i = 0; i < size; i++)
	{
		printf("%d %d", arr[i], arr2[i]);
		printf("\n");
	}
	
}

int main()
{
	srand((unsigned int)time(NULL));
	int N = 30;       // 随机数组最大长度
	int V = 1000;      // 随机数组每个值范围
	int times = 20;
	for (int i = 0; i < times; i++)
	{
		printf("测试开始\n");
		int n = rand() % N + 1; //本次的数组大小，范围[1 ~ N-1] 	
		int* arr1 = randomArray(n, V);//生成随机数数组
		int* arr2 = copyArray(n, arr1);//拷贝一份

		BubbleSort(arr1, n);
		InsertSort(arr2, n);
		bool fruit = sameArray(arr1, arr2, n);
		if (fruit)
		{
			printf("测试通过 - %d\n\n", i);
			PrintArray(arr1, arr2, n);
			free(arr1);
			free(arr2);
		}
		else
		{
			printf("测试失败 - %d\n\n", i);
			free(arr1);
			free(arr2);
			return EOF;
		}
	}
	return 0;
}