完美排序.cpp

各种排序功能的实现和时间比较

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <conio.h>
#define MAXSIZE 30000

typedef struct 
{
	int r[MAXSIZE+1];
	int length;
}SqList;

void directdata(SqList &R)       /////系统产生30000个随机数
{
	int i;
	R.length=MAXSIZE;
	printf("The initial data:\n ");
	for (i=1; i<=R.length; i++)
	{	  
		R.r[i]=rand();
		printf("%d  ",R.r[i]);
		if(i%10==0)
			printf("\n");
	}
}

void creat(SqList &R)           /////用户自定义需要排序的数据
{
	int i;
	printf("\n请输入需要排序的数的个数:");
	scanf("%d",&i);
	printf("\n");
	R.length=i;
	if(i<=MAXSIZE)
	for(i=1;i<=R.length;i++)
	{
		printf("请输入第%d个值:",i);
		scanf("%d",&R.r[i]);
		printf("\n");
	}
}

void show(SqList &R)
{
	int i;
	printf("\n");
	for(i=1;i<=R.length;i++)
	{
		printf("%d   ",R.r[i]);
		if(i%10==0)
			printf("\n");
	}
}

void insertsort(SqList &R)  // 直接插入排序
{
	int i,j;
	for(i=2;i<=R.length;++i)
	{
		if(R.r[i]<R.r[i-1])
		{
			R.r[0]=R.r[i];// 设置监视哨
			R.r[i]=R.r[i-1];
			for(j=i-2;R.r[0]<R.r[j];--j)
				R.r[j+1]=R.r[j];
			R.r[j+1]=R.r[0];
		}
	}	
}

void shellinert(SqList &R,int dk)  // 希尔插入排序
{
	int i,j;
	for(i=dk+1;i<=R.length;++i)
	{
		if(R.r[i]<R.r[i-dk])
		{
			R.r[0]=R.r[i];
			for(j=i-dk;j>0&&R.r[0]<R.r[j];j-=dk)
				R.r[j+dk]=R.r[j];
			R.r[j+dk]=R.r[0];
		}
	}
}

void shellsort(SqList &R)  // 希尔排序
{
	int k;
	int dlta[4]={7,5,3,1};
	for(k=0;k<4;++k)
		shellinert(R,dlta[k]);
}

void bubblesort(SqList &R)  // 起泡排序
{
	int i,j,exchange;
	for(i=1;i<=R.length;i++)
	{
		exchange=0;
		for(j=1;j<=R.length-i;j++)
			if(R.r[j]>R.r[j+1])
			{
				R.r[0]=R.r[j];
				R.r[j]=R.r[j+1];
				R.r[j+1]=R.r[0];
				exchange=1;
			}
			if(!exchange)
				break;
	}
}

int partition(SqList &R,int low,int high)  // 快速排序的子函数（取定枢轴元素）
{
	R.r[0]=R.r[low];// 取定枢轴元素
	while(low<high)
	{// 从表的两端交替地向中间扫描
		while(low<high&&R.r[high]>=R.r[0])
			high--;
		R.r[low]=R.r[high];
		while(low<high&&R.r[low]<=R.r[0])
			low++;
		R.r[high]=R.r[low];
	}
	R.r[low]=R.r[0];// 枢轴元素到位
	return low; // 返回枢轴位置
}

void quicksort(SqList &R,int low,int high)  // 快速排序
{
	int temp;
	if(low<high)
	{	
		temp=partition(R,low,high);// 将表R一分为二
		quicksort(R,temp+1,high);// 对高子表递归排序
		quicksort(R,low,temp-1);// 对低子表递归排序

	}
}

void selectsort(SqList &R)    // 简单选择排序
{
	int i,j,k;
	int temp;
	for (i=1; i<R.length; i++) 
	{
		k=i;
		for (j=i+1; j<=R.length; j++)
			if(R.r[j]<R.r[k])
				k=j;   // 用k指出每趟在无序区间段的最小元素
			if(k!=i) 
			{
				temp=R.r[i];
				R.r[i]=R.r[k];
				R.r[k]=temp;
			}
	}	
}

void heap_adjust(SqList &R,int s,int m)  // 堆排序的子函数（筛选算法，使R[s..m]成为一个大根堆）
{
	int rc,j;
	rc=R.r[s];
	for(j=2*s;j<=m;j=j*2)
	{
		if(j<m&&R.r[j]<R.r[j+1])
			j++;// 若右孩子较大，则把j修改为右孩子的下标
		if(rc>R.r[j])
			break;
		R.r[s]=R.r[j]; // 将R[j]调到父亲的位置上
		s=j;
	}
	R.r[s]=rc; // 被筛结点的值放入最终位置
}

void heapsort(SqList &R)  // 堆排序
{
	int i,temp;
	for(i=R.length/2;i>0;i--)
           heap_adjust(R,i,R.length);// 建立初始堆
	for(i=R.length;i>1;i--)
	{ // 进行MAXSIZE-1次循环，完成堆排序
		temp=R.r[i];// 将第一个元素同当前区间内最后一个元素对换
		R.r[i]=R.r[1];
		R.r[1]=temp;
		heap_adjust(R,1,i-1);// 筛选R[1]结点，得到(MAXSIZE-1)个结点的堆
	}
}

void time_compare(SqList &R,SqList &temp)
{
	clock_t start,finish;     // 用于函数运行的记时
    double duration;          // 用于存放持续时间
	int i;

    printf("┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");
    printf("┃  ★★★★★★  各种排序算法的实现和时间  ☆☆☆☆☆☆  ┃\n");
    printf("┃  ☆☆☆☆☆☆  ************************  ★★★★★★  ┃\n");
    printf("┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫\n");
    printf("┃   排  序  方  法  ┃          时       间 （单位:S)    ┃\n");
    printf("┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫\n");

    //////////////////////直接插入排序///////////////////////////////////
    for(i=1;i<=R.length;i++)
	{
		R.r[i]=temp.r[i];
	}
	start = clock();  // 记时开始
	insertsort(R);    //直接插入排序
	finish = clock();   // 记时结束
	duration = (double)(finish-start) / CLOCKS_PER_SEC;
	printf("┃   直接插入排序    ┃            %lf               ┃\n",duration);
    printf("┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫\n");

    //////////////////////希尔排序///////////////////////////////////
	for(i=1;i<=R.length;i++)
	{
		R.r[i]=temp.r[i];
	}
	start = clock();  // 记时开始
	shellsort(R);     //希 尔  排 序
    finish = clock();   // 记时结束
	duration = (double)(finish-start) / CLOCKS_PER_SEC;
	printf("┃   希 尔  排 序    ┃            %lf               ┃\n",duration);
    printf("┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫\n");

    //////////////////////起泡排序///////////////////////////////////
	for(i=1;i<=R.length;i++)
	{
		R.r[i]=temp.r[i];
	}
	start = clock();  // 记时开始
	bubblesort(R);     //起 泡  排 序
	finish = clock();   // 记时结束
	duration = (double)(finish-start) / CLOCKS_PER_SEC;
	printf("┃   起 泡  排 序    ┃            %lf               ┃\n",duration);
    printf("┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫\n");

	//////////////////////快速排序///////////////////////////////////
    for(i=1;i<=R.length;i++)
	{
		R.r[i]=temp.r[i];
	}
    start = clock();  // 记时开始
	quicksort(R,1,R.length);  //快 速  排 序
	finish = clock();   // 记时结束
	duration = (double)(finish-start) / CLOCKS_PER_SEC;
	printf("┃   快 速  排 序    ┃            %lf               ┃\n",duration);
    printf("┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫\n");

	//////////////////////简单选择插入排序///////////////////////////////////
	for(i=1;i<=R.length;i++)
	{
		R.r[i]=temp.r[i];
	}
    start = clock();  // 记时开始
	selectsort(R);    //简单选择排序
    finish = clock();   // 记时结束
	duration = (double)(finish-start) / CLOCKS_PER_SEC;
	printf("┃   简单选择排序    ┃            %lf               ┃\n",duration);
    printf("┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫\n");

	//////////////////////堆排序///////////////////////////////////
	for(i=1;i<=R.length;i++)
	{
	    R.r[i]=temp.r[i];
	}
	
	start = clock();  // 记时开始
	heapsort(R);      //堆   排 序
    finish = clock();   // 记时结束
	duration = (double)(finish-start) / CLOCKS_PER_SEC;
	printf("┃   堆     排 序    ┃            %lf               ┃\n",duration);
	printf("┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");
	printf("(注：若部分时间为0，是由于数据太少，各种排序算法效率不同，时间长度太短而引起的，而并非实际为0，0实际为近似值。)");
}


void main()
{
	SqList R,temp;
	clock_t start,finish;     // 用于函数运行的记时
    double duration;          // 用于存放持续时间
	int choice;              // 用于存放用户的选择项
	int i;
	R.length=MAXSIZE;
	
	while(1)
	{    
		system("cls");
		printf("┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓");
		printf("┃******************  ☆    各种排序算法的实现和时间    ☆  ******************┃");
		printf("┃************ ★★★★★        ★★★★★★★        ★★★★★ ************┃");
        printf("┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫");
		printf("┃****************★  ☆         0.随机产生数据(30000)  ☆  ★****************┃");
        printf("┃****************★  ☆         1.用户定义数据         ☆  ★****************┃");
        printf("┃****************★  ☆         2.直接插入排序         ☆  ★****************┃");
        printf("┃****************★  ☆         3.希 尔  排 序         ☆  ★****************┃");
        printf("┃****************★  ☆         4.起 泡  排 序         ☆  ★****************┃");
        printf("┃****************★  ☆         5.快 速  排 序         ☆  ★****************┃");
        printf("┃****************★  ☆         6.简单选择排序         ☆  ★****************┃");
        printf("┃****************★  ☆         7.堆     排 序         ☆  ★****************┃");
        printf("┃****************★  ☆         8.运行时间比较         ☆  ★****************┃"); 
		printf("┃****************★  ☆         9.安全退出系统         ☆  ★****************┃");  
        printf("┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛");
        printf(" 请输入您的选择(0--9): ");

        scanf("%d",&choice);
		fflush(stdin);
		switch(choice)
		{
   //////////////////////随 机 产 生 30000 个 数///////////////////////////////////
		case 0:
			directdata(R);
            for(i=1;i<=R.length;i++)
			{
				temp.r[i]=R.r[i];
			}
			getch();
			break;//------------------------------------------------

   //////////////////////用 户 定 义 数 据 输 入///////////////////////////////////
		case 1: 
			creat(R);
			for(i=1;i<=R.length;i++)
			{
				temp.r[i]=R.r[i];
			}
			break;//------------------------------------------------

   //////////////////////直接插入排序///////////////////////////////////	
        case 2:
			for(i=1;i<=R.length;i++)
			{
				R.r[i]=temp.r[i];
			}
			start = clock();  // 记时开始
	        insertsort(R);	
			finish = clock();   // 记时结束
	        duration =(double)(finish-start) / CLOCKS_PER_SEC;
	        printf("\n直接排序结果为:\n");
	        show(R);
		    printf("\n\n运行时间为:%lf S",duration);
			printf("\n\n(注：若时间为0，是由于数据太少，时间长度太短而引起的，而并非实际为0，0实际为近似值。)");
            printf("\n");
            getch();
            break; //------------------------------------------------

   ///////////////////////希 尔  排 序////////////////////////////////////
       case  3:
		    for(i=1;i<=R.length;i++)
			{
				R.r[i]=temp.r[i];
			}
			start = clock();  // 记时开始
	        shellsort(R);
			finish = clock();   // 记时结束
	        duration =(double)(finish-start) / CLOCKS_PER_SEC;
	        printf("\n希尔排序结果为:\n");
	        show(R);
			printf("\n\n运行时间为:%lf S",duration);
			printf("\n\n(注：若时间为0，是由于数据太少，时间长度太短而引起的，而并非实际为0，0实际为近似值。)");
            printf("\n");
            getch();
            break;//------------------------------------------------

   ///////////////////////起 泡 排 序////////////////////////////////////
       case 4:
            for(i=1;i<=R.length;i++)
			{
				R.r[i]=temp.r[i];
			}
		    start = clock();  // 记时开始
	        bubblesort(R);
			finish = clock();   // 记时结束
	        duration =(double)(finish-start) / CLOCKS_PER_SEC;
			printf("\n起泡排序结果为:\n");
	        show(R);
			printf("\n\n运行时间为:%lf S",duration);
			printf("\n\n(注：若时间为0，是由于数据太少，时间长度太短而引起的，而并非实际为0，0实际为近似值。)");
            printf("\n");
            getch();
            break;//------------------------------------------------

	////////////////////// 快 速 排 序//////////////////////////////////////
       case 5:
		   for(i=1;i<=R.length;i++)
			{
				R.r[i]=temp.r[i];
			}
		    start = clock();  // 记时开始
	        quicksort(R,1,R.length);
			finish = clock();   // 记时结束
	        duration = (double)(finish-start) / CLOCKS_PER_SEC;
			printf("\n快速排序结果为:\n");
	        show(R);
			printf("\n\n运行时间为:%lf S",duration);
			printf("\n\n(注：若时间为0，是由于数据太少，时间长度太短而引起的，而并非实际为0，0实际为近似值。)");
            printf("\n");
            getch();
            break;//------------------------------------------------

     ///////////////////// 简单选择排序////////////////////////////////////
       case 6:
		   for(i=1;i<=R.length;i++)
			{
				R.r[i]=temp.r[i];
			}
		    start = clock();  // 记时开始
	        selectsort(R);
			finish = clock();   // 记时结束
	        duration = (double)(finish-start) / CLOCKS_PER_SEC;
	        printf("\n简单选择排序结果为:\n");
	        show(R);
			printf("\n\n运行时间为:%lf S",duration);
			printf("\n\n(注：若时间为0，是由于数据太少，时间长度太短而引起的，而并非实际为0，0实际为近似值。)");
            printf("\n");
			getch();	        
            break;//-----------------------------------------------

     ////////////////////  堆     排 序/////////////////////////////////
       case 7:
		   for(i=1;i<=R.length;i++)
			{
				R.r[i]=temp.r[i];
			}
		    start = clock();  // 记时开始
	        heapsort(R);
			finish = clock();   // 记时结束
	        duration = (double)(finish-start) / CLOCKS_PER_SEC;
	        printf("\n堆排序结果为:\n");
	        show(R);
			printf("\n\n运行时间为:%lf S",duration);
			printf("\n\n(注：若时间为0，是由于数据太少，时间长度太短而引起的，而并非实际为0，0实际为近似值。)");
            printf("\n");
            getch();
            break;//-----------------------------------------------

	   case 8:
		    time_compare(R,temp);
		    getch();
		    break;//-----------------------------------------------

	////////////////////  安全退出系统/////////////////////////////////
       case 9:
		    printf("\n                      ");
		    printf("★★★★★★★★★★★★★★★★★\n");
			printf("\n                      ");
            printf("★★☆  谢谢您的使用,再见!  ☆★★\n");
			printf("\n                      ");
			printf("★★★★★★★★★★★★★★★★★\n\n");
            exit(0);
			break;//-----------------------------------------------
		}
	}
}