sortmain.c

算法导论上面各种排序算法的实现及排序性能比较的c语言实现代码

//file sortmain.c


#include <stdio.h>
#include "sort.h"


void main ()
{
	double time;
	printf("\n\n                      ****  常见排序算法的实现与性能比较  ****\n\n");
	printf("\n     <<  合并排序，插入排序，希尔排序，快速排序，冒泡排序，桶排序  >>\n");
	printf("\n 按任意键继续........");
	getchar();

    printf("\n  1. 样本空间 N=10 时各排序算法的排序效果 ：\n\n");
	printf("\n 按任意键继续........");
	getchar();

	printf("                         (1). 合并排序  \n\n");
	printf(" 随机产生样本array1：\n\n");
    randarray(tenarray, MAXTEN);
	printarray(tenarray, MAXTEN);
	printf("\n 排序后的样本array1：\n\n");
	mergesort(tenarray, MAXTEN);
	printarray(tenarray, MAXTEN);
	printf("\n 按任意键继续........");
	getchar();


	printf("                         (2). 插入排序  \n\n");
	printf(" 随机产生样本array2：\n\n");
	randarray(tenarray, MAXTEN);
	printarray(tenarray,MAXTEN);
	printf("\n 排序后的样本array2：\n");
	insertsort(tenarray,MAXTEN);
	printarray(tenarray,MAXTEN);
	printf("\n 按任意键继续........");
	getchar();

    
	printf("                         (3). 希尔排序  \n\n");
	printf(" 随机产生样本array3：\n\n");
	randarray(tenarray, MAXTEN);
	printarray(tenarray,MAXTEN);
	printf("\n 排序后的样本array3：\n");
	shellsort(tenarray,MAXTEN);
	printarray(tenarray,MAXTEN);
	printf("\n 按任意键继续........");
	getchar();


	printf("                         (4). 快速排序  \n\n");
	printf(" 随机产生样本array4：\n\n");
	randarray(tenarray, MAXTEN);
	printarray(tenarray,MAXTEN);
	printf("\n 排序后的样本array4：\n");
	quicksort(tenarray,MAXTEN);
	printarray(tenarray,MAXTEN);
	printf("\n 按任意键继续........");
	getchar();


	printf("                         (5). 冒泡排序  \n\n");
	printf(" 随机产生样本array5：\n\n");
	randarray(tenarray, MAXTEN);
	printarray(tenarray,MAXTEN);
	printf("\n 排序后的样本array5：\n");
	bubblesort(tenarray,MAXTEN);
	printarray(tenarray,MAXTEN);
	printf("\n 按任意键继续........");
	getchar();


	printf("                         (6). 桶排序  \n\n");
	printf(" 随机产生样本array6：\n\n");
	randarray(tenarray, MAXTEN);
	printarray(tenarray,MAXTEN);
	printf("\n 排序后的样本array6：\n");
	bucketSort(tenarray,MAXTEN);
	printarray(tenarray,MAXTEN);
	printf("\n 按任意键继续........");
	getchar();



	printf("\n\n  2. N=1000，10000，100000时，对同一个样本实例，不同排序完成所需的时间：\n\n");
	printf("\n 按任意键继续........");
	getchar();
	printf("                         (1). 样本空间N=1000:  \n\n");
	printf("\n 按任意键继续........");
	getchar();
	//printf(" 随机产生样本array1：\n\n");
	randarray(thouarray1, MAXTHOUSAND);
	//printarray(thouarray1,MAXTHOUSAND);
	printf("\n                 排序各种算法的执行时间：\n\n");
	copyarray(thouarray1,thouarray2,MAXTHOUSAND);
	time = mergesort(thouarray2,MAXTHOUSAND);
	printf("  合并排序：%lf 秒  ",time); 
	copyarray(thouarray1,thouarray2,MAXTHOUSAND);
	time = insertsort(thouarray2,MAXTHOUSAND);
	printf("  插入排序：%lf 秒\n",time); 
	copyarray(thouarray1,thouarray2,MAXTHOUSAND);
	time = shellsort(thouarray2,MAXTHOUSAND);
	printf("  希尔排序：%lf 秒  ",time);
	copyarray(thouarray1,thouarray2,MAXTHOUSAND);
	time = quicksort(thouarray2,MAXTHOUSAND);
	printf("  快速排序：%lf 秒\n",time); 
	copyarray(thouarray1,thouarray2,MAXTHOUSAND);
	time = bubblesort(thouarray2,MAXTHOUSAND);
	printf("  冒泡排序：%lf 秒  ",time); 
	time = bucketSort(thouarray1,MAXTHOUSAND);
	printf("  桶排序：  %lf 秒\n\n",time);
	printf("\n 按任意键继续........");
	getchar();


	printf("                         (2). 样本空间N=10000:  \n\n");
	randarray(tetharray1, MAXTENTHOUSAND);
	printf("\n                 排序各种算法的执行时间：\n\n");
	copyarray(tetharray1,tetharray2,MAXTENTHOUSAND);
	time = mergesort(tetharray2,MAXTENTHOUSAND);
	printf("  合并排序：%lf 秒  ",time); 
	copyarray(tetharray1,tetharray2,MAXTENTHOUSAND);
	time = insertsort(tetharray2,MAXTENTHOUSAND);
	printf("  插入排序：%lf 秒\n",time); 
    copyarray(tetharray1,tetharray2,MAXTENTHOUSAND);
	time = shellsort(tetharray2,MAXTENTHOUSAND);
	printf("  希尔排序：%lf 秒  ",time);
	copyarray(tetharray1,tetharray2,MAXTENTHOUSAND);
	time = quicksort(tetharray2,MAXTENTHOUSAND);
	printf("  快速排序：%lf 秒\n",time); 
	copyarray(tetharray1,tetharray2,MAXTENTHOUSAND);
	time = bubblesort(tetharray2,MAXTENTHOUSAND);
	printf("  冒泡排序：%lf 秒  ",time); 
	time = bucketSort(tetharray1,MAXTENTHOUSAND);
	printf("  桶排序：  %lf 秒\n\n",time);
	printf("\n 按任意键继续........");
	getchar();


	printf("                         (3). 样本空间N=100000:  \n\n");
	//printf(" 随机产生样本array1：\n\n");
	randarray(hutharray1, MAXHUNDREDTHOUSAND);
	printf("\n                 排序各种算法的执行时间：\n\n");
	copyarray(hutharray1,hutharray2,MAXHUNDREDTHOUSAND);
	time = mergesort(hutharray2,MAXHUNDREDTHOUSAND);
	printf("  合并排序：%lf 秒  ",time); 
	copyarray(hutharray1,hutharray2,MAXHUNDREDTHOUSAND);
	time = insertsort(hutharray2,MAXHUNDREDTHOUSAND);
	printf("  插入排序：%lf 秒\n",time); 
    copyarray(hutharray1,hutharray2,MAXHUNDREDTHOUSAND);
	time = shellsort(hutharray2,MAXHUNDREDTHOUSAND);
	printf("  希尔排序：%lf 秒  ",time);
	copyarray(hutharray1,hutharray2,MAXHUNDREDTHOUSAND);
	time = quicksort(hutharray2,MAXHUNDREDTHOUSAND);
	printf("  快速排序：%lf 秒\n",time); 
	copyarray(hutharray1,hutharray2,MAXHUNDREDTHOUSAND);
	time = bubblesort(hutharray2,MAXHUNDREDTHOUSAND);
	printf("  冒泡排序：%lf 秒  ",time); 
	time = bucketSort(hutharray1,MAXHUNDREDTHOUSAND);
	printf("  桶排序：  %lf 秒\n\n",time);
	printf("\n 按任意键继续........");
	getchar();


    printf("\n\n  3. N=1000，10000，100000时，计算比较不同排序算法所用的平均时间：\n\n");
	printf("                         (1). 样本空间N=1000:  \n\n");
	time = aveRunTime(1,6,MAXTHOUSAND);
	printf("  合并排序：%lf 秒  ",time); 
	time = aveRunTime(2,6,MAXTHOUSAND);
	printf("  插入排序：%lf 秒\n",time); 
	time = aveRunTime(3,6,MAXTHOUSAND);
	printf("  希尔排序：%lf 秒  ",time);
	time = aveRunTime(4,6,MAXTHOUSAND);
	printf("  快速排序：%lf 秒\n",time);
	time = aveRunTime(5,6,MAXTHOUSAND);
	printf("  冒泡排序：%lf 秒  ",time); 
	time = aveRunTime(6,6,MAXTHOUSAND);
	printf("  桶排序：  %lf 秒\n\n",time);
	printf("\n 按任意键继续........");
	getchar();


	printf("                         (2). 样本空间N=10000:  \n\n");
	time = aveRunTime(1,6,MAXTENTHOUSAND);
	printf("  合并排序：%lf 秒  ",time); 
	time = aveRunTime(2,6,MAXTENTHOUSAND);
	printf("  插入排序：%lf 秒\n",time); 
	time = aveRunTime(3,6,MAXTENTHOUSAND);
	printf("  希尔排序：%lf 秒  ",time);
	time = aveRunTime(4,6,MAXTENTHOUSAND);
	printf("  快速排序：%lf 秒\n",time);
	time = aveRunTime(5,6,MAXTENTHOUSAND);
	printf("  冒泡排序：%lf 秒  ",time); 
	time = aveRunTime(6,6,MAXTENTHOUSAND);
	printf("  桶排序：  %lf 秒\n\n",time);
	printf("\n 按任意键继续........");
	getchar();



	printf("                         (3). 样本空间N=100000:  \n\n");
	time = aveRunTime(1,6,MAXHUNDREDTHOUSAND);
	printf("  合并排序：%lf 秒  ",time); 
	time = aveRunTime(2,6,MAXHUNDREDTHOUSAND);
	printf("  插入排序：%lf 秒\n",time); 
	time = aveRunTime(3,6,MAXHUNDREDTHOUSAND);
	printf("  希尔排序：%lf 秒  ",time);
	time = aveRunTime(4,6,MAXHUNDREDTHOUSAND);
	printf("  快速排序：%lf 秒\n",time);
	time = aveRunTime(5,6,MAXHUNDREDTHOUSAND);
	printf("  冒泡排序：%lf 秒  ",time); 
	time = aveRunTime(6,6,MAXHUNDREDTHOUSAND);
	printf("  桶排序：  %lf 秒\n\n",time);
	printf("\n 按任意键继续........");
	getchar();
}