【数据结构基础】之八大排序(C语言实现)-???? 性能测试与排序正确性测试

♈️ 正确性测试

借助这个OJ题来测试一下我们七大排序算法的正确性：

???? 冒泡排序

在这里插入图片描述
这里我们的冒泡排序过了9组测试用例，说明其排序的功能没啥问题，就是太慢了。

???? 选择排序

在这里插入图片描述
选择排序也是同样的效果。

???? 插入排序

在这里插入图片描述

同为一个量级的排序算法，我们的插入排序居然过了11组数据！

???? 希尔排序

在这里插入图片描述

我们的希尔排序直接狠狠拿下了！果然O(N*logN)级别的排序算法就是不一样（崇拜。

???? 堆排序

在这里插入图片描述

堆排序也直接过了！

???? 快速排序

在这里插入图片描述

这里我们快速排序被针对了，导致很慢！还是我们优化了很多地方才过的。

???? 归并排序

在这里插入图片描述
归并排序也过了！

???? 计数排序

在这里插入图片描述

可以看到我们计数排序的实力还是杠杠的，当然这是因为力扣的测试用例没有针对计数排序，如果将数据范围搞的很极端，计数排序的性能就更不上了。

♈️ 性能测试

我们使用下面的代码来测试一下八大排序的性能，测性能的时候我们要调到Release版本下，优化更好。

void TestOP()
{
	int N = 10000;
	printf("N: %d\n", N);
	int* a1 = (int*)malloc(sizeof(int) * N);
	if (a1 == NULL)
	{
		printf("a1 malloc failed\n");
		exit(-1);
	}
	int* a2 = (int*)malloc(sizeof(int) * N);
	if (a2 == NULL)
	{
		printf("a2 malloc failed\n");
		exit(-1);
	}
	int* a3 = (int*)malloc(sizeof(int) * N);
	if (a3 == NULL)
	{
		printf("a3 malloc failed\n");
		exit(-1);
	}
	int* a4 = (int*)malloc(sizeof(int) * N);
	if (a4 == NULL)
	{
		printf("a4 malloc failed\n");
		exit(-1);
	}
	int* a5 = (int*)malloc(sizeof(int) * N);
	if (a5 == NULL)
	{
		printf("a5 malloc failed\n");
		exit(-1);
	}
	int* a6 = (int*)malloc(sizeof(int) * N);
	if (a6 == NULL)
	{
		printf("a6 malloc failed\n");
		exit(-1);
	}
	int* a7 = (int*)malloc(sizeof(int) * N);
	if (a7 == NULL)
	{
		printf("a7 malloc failed\n");
		exit(-1);
	}

	int* a8 = (int*)malloc(sizeof(int) * N);
	if (a8 == NULL)
	{
		printf("a8 malloc failed\n");
		exit(-1);
	}
	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand() % N;
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
		a7[i] = a1[i];
		a8[i] = a1[i];
	}

	int begin1 = clock();
	BubbleSort(a1, N);
	int end1 = clock();

	int begin2 = clock();
	SelectSort(a2, N);
	int end2 = clock();

	int begin3 = clock();
	InsertSort(a3, N);
	int end3 = clock();

	int begin4 = clock();
	HeapSort(a4,N);
	int end4 = clock();

	int begin5 = clock();
	QuickSort1(a5,0,N-1);//三路划分版本
	int end5 = clock();

	int begin6 = clock();
	ShellSort(a6, N);
	int end6 = clock();

	int begin7 = clock();
	MergeSort(a7, N);
	int end7 = clock();

	int begin8 = clock();
	CountSort(a8, N);
	int end8 = clock();

	printf("BubbleSort：%dms\n", end1 - begin1);
	printf("SelectSort：%dms\n", end2 - begin2);
	printf("InsertSort：%dms\n", end3 - begin3);
	printf("HeapSort：%dms\n", end4 - begin4);
	printf("QuickSort1：%dms\n", end5 - begin5);
	printf("ShellSort：%dms\n", end6 - begin6);
	printf("MergeSort：%dms\n", end7 - begin7);
	printf("CountSort：%dms\n", end8 - begin8);
}
int main()
{
	srand(time(NULL));
	TestOP();
	return 0;
}