kindsort.c

各种排序:快速排序,堆排序

#include <stdio.h> 
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h>
#include <conio.h>
#define MAXSIZE 100
typedef int RedType;
typedef struct SqList
{
       RedType INT[MAXSIZE+1];
       int length;      
}SqList; 
SqList L;
void TIME()                                      //获得系统时间
{
	static char *week[]={"一","二","三","四","五","六","日"};
	time_t t;
	struct tm *tp;
	t=time(NULL);
	tp=localtime(&t);
	printf("\t　       ─────────────────────\n");
	printf("\t\t    现在是:%d年%d月%d日",tp->tm_year+1900,tp->tm_mon+1,tp->tm_mday);   
	printf(" %d:%d:%d ",tp->tm_hour,tp->tm_min,tp->tm_sec,tp->tm_wday); 
	printf("星期%s\n",week[(tp->tm_wday)-1]);
}
void PRINT(SqList *L)                             //打印排序结果
{
	int i;
	printf("\t\t");
	for(i=1;i<=L->length;i++)
		   printf("%d ",L->INT[i]);
	printf("\n");
}
void STINSORT(SqList *L)                         //直接插入排序
{
	int i,j;
	for(i=2;i<=L->length;i++)                    //依次插入INT[2]，…，INT[n]
	{
		L->INT[0]=L->INT[i];                     //以INT[0]为哨兵
		j=i-1;
		while(L->INT[j]>L->INT[0])
		{
			L->INT[j+1]=L->INT[j];
			j--;
		}
		L->INT[j+1]=L->INT[0];
	}
}
void BIS_INT(SqList *L)                          //折半插入排序
{  
	int i,j,low,high,mid;
	for(i=2;i<=L->length;++i)
       if(L->INT[i]<L->INT[i-1])
	   {
		   L->INT[0] = L->INT[i];
		   high=i-1;                             //认为在r[1]和r[i-1]之间已经有序
		   low=1;
		   while(low<=high)                      //对有序表进行折半查找
		   {
			   mid=(low+high)/2;
			   if(L->INT[0]<L->INT[mid])
				   high=mid-1;
			   else
				   low=mid+1;
		   }
		   for(j=i-1;j>=high+1;--j)
			   L->INT[j+1]=L->INT[j];
		   L->INT[high+1]=L->INT[0];
	   }
}
void SHELL(SqList *L)                            //希尔排序
{
	int i,j,d;
	d=L->length/2;                               //d为增量
	while(d>=1)                                  //最后一次的增量一定为1
	{
		for(i=d+1;i<=L->length;i++)
		{
			L->INT[0]=L->INT[i];
			j=i-d;
			while(L->INT[j]>L->INT[0]&&j>0)
			{
				L->INT[j+d]=L->INT[j];
				j=j-d;
			}
			L->INT[j+d]=L->INT[0];
		}
		d=d/2;
	}
}
void QUICK(SqList *L,int low,int high)           //快速排序
{
	int i,j,temp;
	i=low;
	j=high;
	temp=L->INT[low];                            //以INT[0]为基准
	while(i<j)                                   //从两端往中间进行扫描直到i=j为止
	{
		while(i<j&&temp<=L->INT[j])              //右端进行扫描
			j--;
		if(i<j)
		{
			L->INT[i]=L->INT[j];
			i++;
		}
		while(i<j&&L->INT[i]<=temp)              //左端进行扫描
			i++;	
		if(i<j)
		{
			L->INT[j]=L->INT[i];
			j--;
		}
	}
	L->INT[i]=temp;
	if(low<i)
		QUICK(L,low,i-1);                        //对左区间进行排序
	if(i<high)
		QUICK(L,j+1,high);                       //对右区间进行排序
}
void SELECT(SqList *L)                           //选择排序
{
	int i,j,small;
	for(i=1;i<=L->length-1;i++)                  //做第i趟排序(1≤i≤length-1)
	{
		small=i;                                 //保存小址
		for(j=i+1;j<=L->length;j++)              //在当前无序区INT[i..length]中选最小的记录INT[small]
		{
			if(L->INT[j]<L->INT[small]) 
				small=j;                         //small记下目前找到的最小关键字所在的位置
		}
		if(small!=i)                             //交换值
		{L->INT[0]=L->INT[i];L->INT[i]=L->INT[small];L->INT[small]=L->INT[0];}
	}
}
void BUBBLE(SqList *L)                           //冒泡优化排序
{
	int i,j,flag=1;                              //i为扫描次数,flag标记为是否交换
	for(i=0;i<=L->length-1&&flag==1;i++)
	{
		flag=0;
		for(j=0;j<L->length-i;j++)
		{
			if(L->INT[j]>L->INT[j+1])
			{
				flag=1;
				L->INT[0]=L->INT[j];
				L->INT[j]=L->INT[j+1];
				L->INT[j+1]=L->INT[0];
			}
		}
	}
}
void BUILDHEAP(SqList *L,int k,int m)            //建立堆
{
	int i,x;
	x=L->INT[k];
	for(i=2*k;i<=m;i=i*2)
	{
		if(i<m&&L->INT[i]<L->INT[i+1])
			i++;
		if(x>L->INT[i]) break;                   //x应插入在位置k上
		L->INT[k]=L->INT[i];
		k=i;
	}
	L->INT[k]=x;                                 //插入
}
void HEAPSORT(SqList *L)                         //堆排序
{
	int i,n,temp;
	n=L->length;
	for(i=n/2;i>0;i--)
		BUILDHEAP(L,i,n);
	for(i=n;i>1;i--)
	{
		temp=L->INT[1];
		L->INT[1]=L->INT[i]; 
		L->INT[i]=temp;   
		BUILDHEAP(L,1,i-1);                      //将INT[1..n-1] 重新调整为大顶堆
	}
}
void RAND(SqList *L)                             //随机生成数字
{
	int i;
	L->length=(rand()%(14))+2;                   //长度<=15,数值>=2的随机数
	for(i=0;i<L->length;i++)
	{
		//rand((unsigned)time(NULL));            //长度为65535以内的随机数
		L->INT[i]=(rand()%(100))+1;              //为0-100的随机数   
	}
}
void INIT(SqList *L)                             //初始化排序的数据
{
	int i;
	char c;
loop:;
	TIME();
	printf("\t　       ─────────────────────\n");
	printf("\n\t\t\t请输入待排序数据的数量【>=2】: ");
	while (scanf("%d", &L->length)!=1)           //检测是否为正确输入数
	{
		while ((c=getchar())!='\n');
		printf("\n\t\t【×】Error:错误的输入,请按任意键重新输入→\n\t\t\t\t");
		getch();
		system("cls");
		goto loop;
	}
	if(L->length<2||L->length>MAXSIZE)
	{
		printf("\n\t\t\t\t 【×】Error:\n\t\t待排序数据数目小于2或超出最大输入量,请按任意键重新输入→\n\t\t\t\t");
		getch();
		system("cls");
		goto loop;
	}
	printf("\n");
	for(i=1;i<=L->length;i++)
	{

	  printf("\t\t\t    请输入第%d个数据: ",i);
lable:;		
	  while (scanf("%d",&L->INT[i])!=1)          //检测是否为正确输入数
	  {
		  while ((c=getchar())!='\n');
		  printf("\n【×】Error:数据输入出错,请重新输入→");
		  goto lable;
	  }
	}
	printf("\n\n\n\n\t\t\t数据初始化成功,按任意键继续→\n");
	getch();
	system("cls");
}
void PRIN()                                      //格式化输出─
{
	int i;
	printf("\t\t");
	for(i=0;i<L.length;i++)
		printf("──");
	printf("\n");
}
int MENUE()
{
	int input_data;
	char c;
	TIME();
	printf("\t　     ╭─────────────────────╮\n");
    printf("\t       ｜          各种排序的基本操作实现          ｜\n");
    printf("\t　     ｜─────────────────────｜\n");
    printf("\t       ｜          1、手动(Hand)输入数据           ｜\n");
    printf("\t　     ｜─────────────────────｜\n");
	printf("\t       ｜          2、随机(Rand)生成数据           ｜\n");
    printf("\t　     ｜─────────────────────｜\n");
    printf("\t       ｜          3、退         出  ...           ｜\n");
    printf("\t       ╰─────────────────────╯\n");
	printf("\t                        请正确选择:");
	while(scanf("%d", &input_data)!=1)                  //检测是否为正确输入数
	{
		while ((c=getchar())!='\n');
		return input_data;
	}
	fflush(stdin);
	return input_data;
}
void SUB_MENUE()
{
	char c;
	for(;;){
	TIME();
    printf("\t　     ╭─────────────────────╮\n");
    printf("\t       ｜          各种排序的基本操作实现          ｜\n");
    printf("\t　     ｜─────────────────────｜\n");
    printf("\t       ｜          1、重新(Again)输入数据          ｜\n");
    printf("\t       ｜          2、折半(Binary)排序             ｜\n");
    printf("\t       ｜          3、直接(Straight)排序           ｜\n");
	printf("\t       ｜          4、希尔(Shell)排序              ｜\n");
	printf("\t       ｜          5、快速(Quick)排序              ｜\n");
	printf("\t       ｜          6、选择(Select)排序             ｜\n");
	printf("\t       ｜          7、冒泡(Bubble)排序             ｜\n");
	printf("\t       ｜          8、堆  (Heap)排序               ｜\n");
	printf("\t       ｜          9、随机(Rand)生成               ｜\n");
    printf("\t       ｜          Q、退     出  ...               ｜\n");
    printf("\t       ╰─────────────────────╯\n");
	printf("\t        【共%d个数据】如下:\n",L.length);
	PRIN();
	PRINT(&L);
	PRIN();
    printf("\t                        请选择:");
    scanf("%s",&c);
	switch(c)
	{
		case '1':
			system("cls");
			INIT(&L);
			system("cls");
			break;
		case '2':
			BIS_INT(&L);
			printf("\n\t\t\t         排序成功!!!\n\t\t\t    ");
			system("pause");
			system("cls");
			break;
		case '3':
			STINSORT(&L);
			printf("\n\t\t\t         排序成功!!!\n\t\t\t    ");
			system("pause");
			system("cls");
			break;
		case '4':
			SHELL(&L);
			printf("\n\t\t\t          排序成功!\n\t\t\t     ");
			system("pause");
			system("cls");
			break;
		case '5':
			QUICK(&L,1,L.length);
			printf("\n\t\t\t          排序成功!\n\t\t\t     ");
			system("pause");
			system("cls");
			break;
		case '6':
			SELECT(&L);
			printf("\n\t\t\t          排序成功!\n\t\t\t     ");
			system("pause");
			system("cls");
			break;
		case '7':
			BUBBLE(&L);
			printf("\n\t\t\t          排序成功!\n\t\t\t    ");
			system("pause");
			system("cls");
			break;
		case '8':
			HEAPSORT(&L);
			printf("\n\t\t\t           排序成功!\n\t\t\t    ");
			system("pause");
			system("cls");
			break;
		case '9':
			RAND(&L);
			printf("\n\t\t\t         随机生成成功!\n\t\t\t   ");
			system("pause");
			system("cls");
			break;
		case 'q':
		case 'Q':
			system("cls");
			printf("\n\n\n\n\t\t\t   谢 谢 使 用 , 再 见!!!\n");
			printf("\n\t\t\t     任 意 键 退 出!\n\t\t\t");
			getch();
			exit(0);
			break;
		default :
			printf("\n\t\t\t\t 【×】Error:\n\t\t\t  输入有误,请重新选择!!!\n");
			getch();
			system("cls");
			break;
	}
	}
}
void main(void)
{	
	int input_data;
	do
	{
		input_data=MENUE();
		switch(input_data)
		{
		case 1:
			system("cls");
			INIT(&L);
			SUB_MENUE();  
			break;
		case 2:
			system("cls");
			RAND(&L);
			SUB_MENUE();  
			break;
		case 3:
			system("cls");
			printf("\n\n\n\n\t\t\t   谢 谢 使 用 , 再 见!!!\n");
			printf("\n\t\t\t     任 意 键 退 出!\n\t\t\t");
			getch();
			exit(0);
			break;
		default:
			printf("\n\t\t\t\t 【×】Error:\n\t\t\t  输入有误,请重新选择!!!\n");
			getch();
			system("cls");
			break;
		}
	}while(input_data!=3); 
}