main.c

插入排序

#include <stdio.h>
#include <sys/time.h>
#include "sort.h"
#include "sort.c"

main()
{
	struct timeval start_t,end_t;
	int choice,flag;
	int i,j,m;
	
	//构建数组
	printf("input the numbers of the array:");
	scanf("%d",&m);
	ptr=BuildArray(m);
	printf("build array by random function:\n");
	print(ptr,1,m);
	printf("\n");
	
	printf("please choose algorithm:\n");
	printf("0 for exit;\n");
	printf("1 for BubbleSort;\n");
	printf("2 for HeapSort;\n");
	printf("3 for InsertSort;\n");
	printf("4 for QuickSort;\n");
	printf("5 for SelectSort;\n");
	printf("6 for ShellSort;\n");
	printf("7 for One input one sorted;\n");
	printf("8 for change numbers;\n");
	for(;;){
		scanf("%d",&choice);
		if(choice==0)
			break;
		else{
			switch(choice){
				case 1:
					//冒泡排序
					flag=0;
					initializtion(m);
					gettimeofday(&start_t,NULL);
					printf("bubblesort algorithm start at %d : %d \n",start_t.tv_sec,start_t.tv_usec);
					BubbleSort(pt,m);
					gettimeofday(&end_t,NULL);
					printf("algorithm end at %d : %d \n",end_t.tv_sec,end_t.tv_usec);
					//printf("the queue sorted by bubblesort is:\n");
					//print(pt,1,m);
					printf("\n");
					check(pt,m);
					printf("BubbleSort compare=%d*LIMIT+%u,move=%d*LIMIT+%u",c_carry,compare,c_carry,move);
					printf("\n\n");
					break;

				case 2:
					//堆排序
					flag=0;
					initializtion(m);
					gettimeofday(&start_t,NULL);
					printf("heapsort algorithm start at %d : %d \n",start_t.tv_sec,start_t.tv_usec);
					HeapSort(pt,m);
					gettimeofday(&end_t,NULL);
					printf("algorithm end at %d : %d \n",end_t.tv_sec,end_t.tv_usec);
					//printf("the queue sorted by heapsort is:\n");
					//print(pt,1,m);
					printf("\n");
					check(pt,m);
					printf("HeapSort compare=%d*LIMIT+%u,move=%d*LIMIT+%u",c_carry,compare,c_carry,move);
					printf("\n\n");
					break;
				case 3:
					//插入排序
					flag=0;
					initializtion(m);
					gettimeofday(&start_t,NULL);
					printf("insertsort algorithm start at %d : %d \n",start_t.tv_sec,start_t.tv_usec);
					InsertSort(pt,m);
					gettimeofday(&end_t,NULL);
					printf("algorithm end at %d : %d \n",end_t.tv_sec,end_t.tv_usec);
					//printf("the queue sorted by insertsort is:\n");
					//print(pt,1,m);
					printf("\n");
					check(pt,m);
					printf("InsertSort compare=%d*LIMIT+%u,move=%d*LIMIT+%u",c_carry,compare,c_carry,move);
					printf("\n\n");
					break;
				case 4:
					//快速排序
					flag=0;
					initializtion(m);
					gettimeofday(&start_t,NULL);
					printf("quicksort algorithm start at %d : %d \n",start_t.tv_sec,start_t.tv_usec);
					QuickSort(pt,m,0,m-1);
					gettimeofday(&end_t,NULL);
					printf("algorithm end at %d : %d \n",end_t.tv_sec,end_t.tv_usec);
					//printf("the queue sorted by quicksort is:\n");
					//print(pt,1,m);
					printf("\n");
					check(pt,m);
					printf("QuickSort compare=%d*LIMIT+%u,move=%d*LIMIT+%u",c_carry,compare,c_carry,move);
					printf("\n\n");
					break;
				case 5:
					//选择排序
					flag=0;
					initializtion(m);
					gettimeofday(&start_t,NULL);
					printf("selectsort algorithm start at %d : %d \n",start_t.tv_sec,start_t.tv_usec);
					SelectSort(pt,m);
					gettimeofday(&end_t,NULL);
					printf("algorithm end at %d : %d \n",end_t.tv_sec,end_t.tv_usec);
					//printf("the queue sorted by selectsort is:\n");
					//print(pt,1,m);
					printf("\n");
					check(pt,m);
					printf("SelectSort compare=%d*LIMIT+%u,move=%d*LIMIT+%u",c_carry,compare,c_carry,move);
					printf("\n\n");
					break;
				case 6:
					//希尔排序
					flag=0;
					initializtion(m);
					gettimeofday(&start_t,NULL);
					printf("shellsort algorithm start at %d : %d \n",start_t.tv_sec,start_t.tv_usec);
					ShellSort(pt,m);
					gettimeofday(&end_t,NULL);
					printf("algorithm end at %d : %d \n",end_t.tv_sec,end_t.tv_usec);
					//printf("the queue sorted by shellsort is:\n");
					//print(pt,1,m);
					printf("\n");
					check(pt,m);
					printf("ShellSort compare=%d*LIMIT+%u,move=%d*LIMIT+%u",c_carry,compare,c_carry,move);
					printf("\n\n");	
					break;
				 case 7:
				 	//输入一个排序一个
				 	flag=0;
				 	memset(a,0,sizeof(a));
				 	pt=a;
				 	gettimeofday(&start_t,NULL);
				 	printf("algorithm start at %d : %d \n",start_t.tv_sec,start_t.tv_usec);
				 	for(i=0;i<m;i++){
				 		if(i==0){
				 			printf("please input the first calllist:%d\n",Queue[0]);
				 			//scanf("%d",pt+0);
				 			a[0]=Queue[0];
				 			printf("sorted queue is:\n");
				 			printf("%d	\n",*(pt+0));
				 			continue;
				 		}
				 		printf("next:%d\n",Queue[i]);
				 		//scanf("%d",pt+i);
				 		a[i]=Queue[i];
				 		for(j=i-1;j>=0;j--)
				 			if(*(pt+j)>*(pt+j+1))
				 				swap(pt+j,pt+j+1);
				 		//printf("sorted queue is:\n");
				 		print(pt,1,i+1);
				 		printf("\n");
				 	}
				 	gettimeofday(&end_t,NULL);
				 	printf("algorithm end at %d : %d \n",end_t.tv_sec,end_t.tv_usec);
				 	check(pt,i);
					break;
				 case 8:
				 	main(); 
				 	break;
				default:
					//出错
					printf("input error!\nplease try again:\n");
					flag=1;
					break;
			}
			if(flag==0){
				printf("sort algorithm running time: %d microseconds\n",((end_t.tv_sec)-(start_t.tv_sec))*1000000+(end_t.tv_usec)-(start_t.tv_usec));
				printf("\n");
			}
		}
	}
}