排序2——C语言-3. 代码和性能测试

void test()
{
	srand(time(0));
	int n = 1000;

	int* a1 =(int*)malloc(sizeof(int) * n);
	int* a2 =(int*)malloc(sizeof(int) * n);
	int* a3 =(int*)malloc(sizeof(int) * n);
	int* a4 =(int*)malloc(sizeof(int) * n);
	int* a5 =(int*)malloc(sizeof(int) * n);
	int* a6 =(int*)malloc(sizeof(int) * n);
	int* a7 =(int*)malloc(sizeof(int) * n);
	int* a8 =(int*)malloc(sizeof(int) * n);
	int* a9 =(int*)malloc(sizeof(int) * n);
	int* a10 =(int*)malloc(sizeof(int) * n);
	int* a11 =(int*)malloc(sizeof(int) * n);

	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];
		a9[i] = a1[i];
		a10[i] = a1[i];
		a11[i] = a1[i];
	}

	printf("排序%d个数所用的时间(ms)\n",n);

	int begin1 = clock();
	ShellSort(a1, n);
	int end1 = clock();

	int begin2 = clock();
	HeapSort(a2, n);
	int end2 = clock();

	int begin3 = clock();
	QuickSort1(a3, 0, n - 1);
	int end3 = clock();

	int begin4 = clock();
	QuickSort2(a4, 0, n - 1);
	int end4 = clock();

	int begin5 = clock();
	MergeSort(a5, n);
	int end5 = clock();

	int begin6 = clock();
	MergeSortNonRe(a6, n);
	int end6 = clock();

	int begin7 = clock();
	QuickSort3(a7, 0, n - 1);
	int end7 = clock();

	int begin8 = clock();
	QuickSortNonRe(a8, 0, n - 1);
	int end8 = clock();

	int begin9 = clock();
	InsertSort(a9, n);
	int end9 = clock();

	int begin10 = clock();
	SelectSort(a10, n);
	int end10 = clock();

	int begin11 = clock();
	BubbleSort(a11, n);
	int end11 = clock();


	printf("希尔排序:%d", end1-begin1);
	printf("\n堆排序:%d", end2 - begin2);
	printf("\n快速排序1(hoare版本):%d", end3 - begin3);
	printf("\n快速排序2(前后指针法):%d", end4 - begin4);
	printf("\n快速排序3(挖坑法):%d", end7 - begin7);
	printf("\n快速排序4(非递归):%d", end8 - begin8);
	/*printf("\n归并排序:%d", end5 - begin5);
	printf("\n归并排序(非递归):%d", end6 - begin6);*/
	printf("\n直接插入排序:%d", end9 - begin9);
	printf("\n直接选择排序:%d", end10 - begin10);
	printf("\n冒泡排序:%d", end11 - begin11);

}

int main()
{
	test();
	
	return 0;
}

用上述方法，完成对多个数组进行相同的初始化，我们看一下这些排序的性能差别。
之前的排序也加入测试，对比一下。测试性能时，我们要在release版本下测试。

先对比1000个数据所用的时间，单位是毫秒（ms）

可以看到，数据量为1000时，都很快。这里的0不是指0毫秒，而是指所用的时间小于1毫秒。

数据量扩大十倍后（一万）

数据量再扩大十倍（十万）

当数据量为十万时，后三个排序已经开始吃力了，和前面的对比速度差了一百多倍 。后续就不测试它们了，这里直接把数据量加到一千万。

可以看到，复杂度为O（N^2）和O（N*logN）的排序算法时间差异还是蛮大的。

关于快排就介绍到这里了，下篇介绍归并排序、计数排序以及这些排序算法的稳定性。