demo.cpp

实现各种内部排序。包括冒泡排序

/*实现冒泡、直接插入、Shell排序和快速排序、堆排序
并比较各种排序算法的移动次数和比较次数。*/

/*实验说明：1)采用顺序表存放待排序的记录， 设关键字类型为整型。
            2)设计了两个菜单，一个主菜单选择输入的方式，一个是排序菜单选择上述排序方法。
			3)程序执行时能按趟输出排序的结果及移动和比较的次数。
            4)可以人工输入和随机输入两种输入方式*/
#include<stdio.h>
#include<stdlib.h>
#include<time.h> 
#define n 10
#define FALSE 0
#define TRUE 1

typedef int KeyType;//记录关键字为整型数据
typedef char InfoType;//记录其他数据设为字符型，本程序未用该数据项*/
typedef struct 
{
	KeyType key;//关键字项
	InfoType otherinfo;//其他数据项
}RecType;//定义的记录类型
typedef RecType Seqlist[n+1];//定义的顺序表类型
int m,num;//全局变量m存储输出的是第几趟结果；num存储递归调用的次数
Seqlist R,S;//记录待排序的10个数
int contrast,move;//比较和移动的次数


void Insertsort()//直接插入排序
{                //对顺序表中记录按递增序列进行插入排序                             
	int i,j,k;
	for(i=2;i<=n;i++)
	{
		contrast++;
		if(R[i].key<R[i-1].key)
		{
			R[0]=R[i];
			move=move++;
			j=i-1;
			contrast++;
			while(R[0].key<R[j].key)
			{                       //从右向左在有序区R[1...i-1]中查找R[i]的插入位置 
				R[j+1]=R[j];
				move=move++;
				j--;				
			}
			R[j+1]=R[0];
			move=move++;
		}		
		if(m==i-1)
		{   
			printf("第%d趟的结果是：\n",m);
			for(k=1;k<=n;k++)
				printf("%5d",R[k].key);
			printf("\n");
			printf("请输入还要输出第几趟结果，不想输出时请输入0：\n");
			scanf("%d",&m);
		}
	}
    if(m==n||m==0)
	{
		 printf("最终排序结果是：\n");
		 for(k=1;k<=n;k++)
	     printf("%5d",R[k].key);
		 printf("\n");
		 printf("比较次数为%d\n",contrast);
		 printf("移动次数为%d\n",move);
		 
	}
}
void Bubblesort()//冒泡排序
{                //R[1...n]是待排序的文件，采用自下向上扫描对R做冒泡排序
	int i,j,k;
	int exchange;
	for(i=1;i<n;i++)
	{               //最多做n-1趟排序
		exchange=FALSE;
		for(j=1;j<=n-1;j++)
		{
			contrast++;
			if(R[j+1].key<R[j].key)
			{
				R[0]=R[j];
				R[j]=R[j+1];
				R[j+1]=R[0];
				exchange=TRUE;
                move=move+3; 
			}           
		}
        if(i==m)
		{
			printf("第%d趟的结果是：\n",m);
			for(k=1;k<=n;k++)
				printf("%5d",R[k].key);
			printf("\n");
			printf("请输入还要输出第几趟结果，不想输出时请输入0：\n");
			scanf("%d",&m);
		}
	}
	printf("最终排序结果是：\n");
	for(k=1;k<=n;k++)
	    printf("%5d",R[k].key);
	printf("\n");
    printf("比较次数为%d\n",contrast);
	printf("移动次数为%d\n",move);

}

int Partition(int i,int j)
{                 //调用Partition（low,high）时，返回在R[low...high]中基准记录的位置
	
    RecType pivot=R[i];
	move++;
	while(i<j)
	{
		while(i<j && R[j].key>=pivot.key)
			j--;
		contrast++;
		if(i<j)
		{
			R[i++]=R[j];
			move++;
		}
		while(i<j && R[i].key<=pivot.key)
			i++;
		contrast++;
		if(i<j)
		{
			R[j--]=R[i];
			move++;
		}
	}
	R[i]=pivot;
	move++;
	return i;
}

void Quicksort(int low,int high)//快速排序
{                               //对R[low...high]的快速排序
	int pivotpos,k;
	if(low<high)
	{           //当区间长度大于1时才需排序
		pivotpos=Partition(low,high);
		num++;
		if(m==num)
		{
			printf("第%d趟的结果是：\n",m);
			for(k=1;k<=n;k++)
				printf("%5d",R[k].key);
			printf("\n");
			printf("请输入还要输出第几趟结果，不想输出时输入0：\n");
			scanf("%d",&m);
		}
		Quicksort(low,pivotpos-1);
		Quicksort(pivotpos+1,high);
	}
	if(m!=0||m==0)
	{
		if(low==1 && high==n)
		{
		   printf("最终排序结果是：\n");
		   for(k=1;k<=n;k++)
			   printf("%5d",R[k].key);
		   printf("\n");
		   printf("比较次数为%d\n",contrast);
		   printf("移动次数为%d\n",move);
		   
		}
	}
}

void Shellsort()//Shell排序
{
	int i,j,k,increment,a=0;
    for(increment=n/2;increment>0;increment/=2)
	{
		for(i=increment+1;i<=n;i++)
		{ 
		   contrast++;
		   if(R[i].key<R[i-1].key)
		   {
			   R[0]=R[i];
			   move++;
			   j=i-increment;
			   contrast++;
			   while(j>=0 && R[0].key<R[j].key)
			   {                       //从右向左在有序区R[1...i-1]中查找R[i]的插入位置 
				  R[j+increment]=R[j];
				  j-=increment;
				  move++;
			   }
			   R[j+increment]=R[0];
			   move++;
		   }
		}a++;
		if(m==a)
		{
			printf("第%d趟的结果是：\n",m);
			for(k=1;k<=n;k++)
				printf("%5d",R[k].key);
			printf("\n");
			printf("请输入还要输出第几趟结果，不想输出时输入0：\n");
			scanf("%d",&m);
		}			
	}
	printf("最终排序结果是：\n");
	for(k=1;k<=n;k++)
	   printf("%5d",R[k].key);
	printf("\n");
	printf("比较次数为%d\n",contrast);
	printf("移动次数为%d\n",move);
	
}

void Sift(Seqlist R,int i,int m)//创建堆(m=n)
{
	int child;
	R[0]=R[i];//将待筛数据暂存于工作变量R[0]
	child=2*i;//child为i的左儿子结点下标
	while(child<=m)
	{
		contrast++;
		if(child<m && R[child].key<R[child+1].key)
		{
			child++;//child指向R[i]的左、右子女中排序码较大的结点
		}
		contrast++;
		if(R[0].key<=R[child].key)//如果右儿子数据较左儿子大，将child改为右儿子下标
		{
			R[i]=R[child];
			move++;
			i=child;
			child=2*i;
		}//如果待筛数据小于其儿子数据，将其儿子数据上移，待筛结点则降至其儿子处
        else 
			child=m+1;//筛选完成，终止循环
	}
	R[i].key=R[0].key;
	move++;//被筛结点数据放入最终位置
}

void Heapsort()//堆排序
{
	int i,k;
	RecType w;
	for(i=n/2;i>=1;i--)
		Sift(R,i,n);
	for(i=n;i>1;i--)
	{   move++;
		w=R[i];
		R[i]=R[1];
        R[1]=w;
		Sift(R,1,i-1);
        move=move+2;
        num++;
		if(m==num)
		{
	        printf("第%d趟的结果是：\n",m);
		    for(k=1;k<=n;k++)
			   printf("%5d",R[k].key);
		    printf("\n");
		    printf("请输入还要输出第几趟结果，不想输出时输入0：\n");
		    scanf("%d",&m);
		}
	}
    if(m==0||m==10)
	{
		num=0;
	    printf("最终排序结果是：\n");
	    for(k=1;k<=n;k++)
	      printf("%5d",R[k].key);
	    printf("\n");
	    printf("比较次数为%d\n",contrast);
	    printf("移动次数为%d\n",move);
		
	}
}
void main()
{
	Seqlist S;
	int i,select1;
	char ch1,ch2,select2='y';
	printf("\n\n");
	printf("欢迎进入排序界面   欢迎进入排序界面   欢迎进入排序界面   欢迎进入排序界面!\n");
	printf("\n\n\n");
	printf("      ***************算法与数据结构课程设计——排序DEMO*******\n");
	printf("      *                                                      *\n");
	printf("      *                                                      *\n");
	printf("      *                                                      *\n");
	printf("      *                                                      *\n");
	printf("      *                   指导老师:   XXX                    *\n");
	printf("      *                                                      *\n");
	printf("      ********************************************************\n\n");
	printf("      *课程设计：\n");
	printf("           实现功能说明：\n");
    printf("               (1)能进行各种排序算法运算，排序包括直接插入排序、希尔排序、\n");
	printf("                  冒泡排序、快速排序、堆排序，并可以输出每一趟结果。\n");
    printf("               (3)排序的结果包括排序后的序列、算法关键字比较和移动的次数。\n");
    printf("               (4)数据的输入有两种方式: 手工输入和随机生成。\n");
	printf("                  数据个数=10，随机数<10000。\n\n");

    while(select2=='y'||select2=='Y')
	{
	    printf("      *************************主菜单************************\n");
		printf("      *                                                     *\n");
	    printf("      *                   0----人工输入数据                 *\n");
		printf("      *                                                     *\n");
	    printf("      *                   1---随机产生数据                  *\n");
		printf("      *                                                     *\n");
	    printf("      *                   2---退出程序                      *\n");
		printf("      *                                                     *\n");
		printf("      *******************************************************\n");
	    printf("请选择操作类型:\n");
	    scanf("%d",&select1);
	    if(select1==0)
		{printf("请输入10个待排序的数据:(每两个数据间用空格隔开)\n");
		   for(i=1;i<=n;i++)
		   scanf("%d",&S[i].key);
		}
	    if(select1==1)
		{
	       int i;
           srand( (unsigned)time( NULL ) );
		  	for( i = 1; i <=n;i++ )   
           S[i].key=rand()%1000;
		  
	       printf("随机产生的10个数为: \n");
		    for( i = 1; i <=10;i++ )
	          printf("%5d",S[i].key);
		}
		if(select1==2)
		{
            printf("\n\n");
			printf("--------------------------------------------\n");
			select2='n';
		}
		if(select1!=0 && select1!=1 && select1!=2)
			printf("输入错误! 请重新输入:\n\n");
	    while(select1==0||select1==1)
		{
	        ch1='y';
	        while(ch1=='y'||ch1=='Y')
			{
		    printf("                                                          \n");
		    printf(" ***********************排序菜单**************************\n");
		    printf(" *                                                       *\n");
		    printf(" *                  0—直接插入排序                      *\n");
		    printf(" *                                                       *\n");
		    printf(" *                  1—冒泡排序                          *\n");
		    printf(" *                                                       *\n");
		    printf(" *                  2—快速排序                          *\n");
            printf(" *                                                       *\n");
		    printf(" *                  3—Shell 排序                        *\n");
            printf(" *                                                       *\n");
		    printf(" *                  4—堆排序                            *\n");
		    printf(" *                                                       *\n");
		    printf(" *                  5—各排序的移动和比较次数的比较      *\n");
		    printf(" *                                                       *\n");
		    printf(" *                  6—返回主菜单                        *\n");
		    printf(" *                                                       *\n");
		    printf(" * *******************************************************\n");
		    printf("请选择排序类型：\n");
		        scanf("\n%c",&ch2);
		        switch(ch2)
				{
		            case '0':
					     printf("请输入要输出第几趟结果：(不想输出时输入0)\n");
					     scanf("%d",&m);
					     for(i=1;i<=n;i++)
					        R[i].key=S[i].key;
						
					     Insertsort();
					     break;
		            case '1':
					     printf("请输入要输出第几趟结果：(不想输出时输入0)\n");
					     scanf("%d",&m);
					     for(i=1;i<=n;i++)
					        R[i].key=S[i].key;
					     Bubblesort();
					     break;
		            case '2':
					     printf("请输入要输出第几趟结果：(不想输出时输入0)\n");
					     scanf("%d",&m);
					     for(i=1;i<=n;i++)
					        R[i].key=S[i].key;
					     num=0;
					     Quicksort(1,n);
					     break;
		            case '3':
					     printf("请输入要输出第几趟结果：(不想输出时输入0)\n");
					     scanf("%d",&m);
					     for(i=1;i<=n;i++)
					        R[i].key=S[i].key;
					     Shellsort();
					     break;
		            case '4':
					     printf("请输入要输出第几趟结果：(不想输出时输入0)\n");
					     scanf("%d",&m);
					     for(i=1;i<=n;i++)
					        R[i].key=S[i].key;
					     Heapsort();
					     break;
		            case '5':
		                 printf("      -------------------------------------------------\n");
		                 printf("                     对各排序进行比较分析             \n");
						 printf("      -------------------------------------------------\n");
						 printf("                          | 比较次数 |   移动次数      \n");
		                 printf("      -----------------------------------------------\n");
		                 printf("        直接插入排序      | %d       |   %d            \n",contrast,move);
		                 printf("      ------------------------------------------------\n");
		                 printf("        冒泡排序          | %d       |   %d            \n",contrast,move);
		                 printf("      -------------------------------------------------\n");
		                 printf("        快速排序          | %d       |   %d            \n",contrast,move);
		                 printf("      -------------------------------------------------\n");
		                 printf("        Shell排序         | %d       |   %d            \n",contrast,move);
		                 printf("      -------------------------------------------------\n");
		                 printf("        堆排序            | %d       |   %d            \n",contrast,move);
		                 printf("      -------------------------------------------------\n\n\n");		                 ;
					     break;
					case '6':
					     ch1='n';
					     select1=3;
					     break;
					default:
						printf("输入错误! 请重新输入!");
					     ch1='n';
				}
			}
       
		}
    }
}