计算机软件技术基础实验之快速排序程序

//************************  快速排序程序  *****************************
//**几点说明: 
//**1.当线性表长度大于3时,选用快速排序
//**2.当线性表长度不大于3时,选用简单插入排序
//**********************************************************************
#include<stdio.h>
#include<string.h>
#define N 20                //设定数据表的最大长度
int a[N];
int max,count;

//**********************************************************************
//                 打印表头
//**********************************************************************
void print(void)
{
	printf("************************************************************************\n");
    printf("************************************************************************\n");
    printf("*********************      快速排序程序      ***************************\n");
    printf("***********************    制作：曾令李    *****************************\n");
    printf("************************************************************************\n");
}

//**********************************************************************
//                 输入数据
//**********************************************************************
int  input(void)
{
	int i=0,j=0,t;
    printf("请输入数据,并以‘0’结束\n（最多%d个整型数据，且在(-2^31)--(2^31-1)之间,注意‘0’已经作为结束符）：\n",N);
    while(t!=0&&i<=N)
	{
		scanf("%d",&a[i]);
        t=a[i];
		i=i+1;
		j=j+1;
	}
	j=j-1;
	printf("\n************************************************************************\n");
	printf("\n您总共输入了%d个数据：\n",j);
	for(i=0;i<j;i++)
		printf("%d  ",a[i]);
	printf("\n************************************************************************\n");
	return(j);
}

//**********************************************************************
//                 简单插入排序
//**********************************************************************

void  insort(int m3,int n3)   
{
	int t,p[3];
	int i,j,k,w;                  //w记录数据的个数
	if(n3-m3==2)               //把需要排序的数据赋给数组p[]
	{
		p[0]=a[m3];            
        p[1]=a[m3+1];
        p[2]=a[n3];
		w=3;
   	}
	else
		if(n3-m3==1)
		{
			p[0]=a[m3];
            p[1]=a[n3];
			w=2;
	   	}
		else
		{
			p[0]=a[m3];
			w=1;
	    }
		for(j=1;j<w;j++)              //对数据进行简单插入排序
		{
			t=p[j];
			k=j-1;
			while(k>=0&&p[k]>t)
			{
				p[k+1]=p[k];
				k=k-1;
			}
			p[k+1]=t;
		}
			if(n3-m3==2)                   //把排好序的数据重新赋给a[]
			{
				a[m3]=p[0];
				a[m3+1]=p[1];
				a[n3]=p[2];
			}
			else
				if(n3-m3==1)
				{
					a[m3]=p[0];
					a[n3]=p[1];
				}
				else  
					a[m3]=p[0];
				printf("第%d次操作后的结果：\n",count+1);
				for(i=0;i<max;i++)
					printf(" %d ",a[i]);
				printf("\n");
				count=count+1;
				return ;
}

//**********************************************************************
//                 线性表分割
//********************************************************************** 

int split(int m2,int n2)
{
	int i,j,t,I;
    t=a[m2];                     //选线性表的第一个元素、中间元素、最后一个元素的中项为t
 	if((a[n2]>t&&a[(n2-m2)/2]>a[n2])||(a[n2]<t&&a[(n2-m2)/2]<a[n2]))
	{
		t=a[n2];
		a[n2]=a[m2];
	}
	else
		if((a[(n2-m2)/2]>t&&a[n2]>a[(n2-m2)/2])||(a[(n2-m2)/2]<t&&a[n2]<a[(n2-m2)/2]))
		{
			t=a[(n2-m2)/2];
			a[(n2-m2)/2]=a[m2];
		}
	i=m2;
	j=n2;
	while(i!=j)                      //i==j则分割完毕         
	{
		while(a[j]>=t&&i<j)          //从表尾开始,元素大于t时j往前移
		{
			j=j-1;
		}
		if(i<j)                      //如果未分割完,且出现小于t的元素,则把a[j]赋给a[i]
		{
			a[i]=a[j];
			i=i+1;
			while(a[i]<=t&&i<j)     //从表头开始,元素小于t的i往后移
			{
				i=i+1;
			}
			if(i<j)                //如果未分割完,且出现大于t的元素,则把a[i]赋给a[j]
			{
				a[j]=a[i];
				j=j-1;
			}
		}
	}
	a[i]=t;                    //I为t在线性表中所在的位置
	I=i;
	printf("第%d次操作后的结果：\n",count+1);
	for(i=0;i<max;i++)
		printf(" %d ",a[i]);
	printf("\n");
	count=count+1;
	return I;
}

//**********************************************************************
//                 快速排序
//********************************************************************** 

void qksort(int m1,int n1)
{
	int I;
	if(n1>m1)
	{			
		if(n1-m1>2)                             //当线性表长度大于3时,选用快速排序
		{
			I=split(m1,n1);
			qksort(m1,I-1);
			qksort(I+1,n1);
		}
		else insort(m1,n1);                    //当线性表长度不大于3时,选用简单插入排序
	}
	return;
}


void main()
{
	
	int i,c;
	print();                              //打印界面头部
AA:	count=0;
	max=input();                          //输入数据,返回数据个数
	qksort(0,max-1);                      //快速排序
	printf("最后结果为：\n");            //打印结果
	for(i=0;i<max;i++)
		printf(" %d ",a[i]);
	printf("\n谢谢使用！");
	printf("\n************************************************************************\n");
	printf("**************************************************************************\n");
 	printf("请选择您要进行的操作：1、继续       0、退出\n");
 	printf("**************************************************************************\n");
 	scanf("%d",&c);
 	if(c==1)goto AA;
  	else
	return;
}