//************************  快速排序程序  *****************************
//**幾點(diǎn)說明: 
//**1.當(dāng)線性表長度大于3時(shí),選用快速排序
//**2.當(dāng)線性表長度不大于3時(shí),選用簡單插入排序
//**********************************************************************
#include<stdio.h>
#include<string.h>
#define N 20                //設(shè)定數(shù)據(jù)表的最大長度
int a[N];
int max,count;

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

//**********************************************************************
//                 輸入數(shù)據(jù)
//**********************************************************************
int  input(void)
{
	int i=0,j=0,t;
    printf("請輸入數(shù)據(jù),并以‘0’結(jié)束\n（最多%d個(gè)整型數(shù)據(jù)，且在(-2^31)--(2^31-1)之間,注意‘0’已經(jīng)作為結(jié)束符）：\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個(gè)數(shù)據(jù)：\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記錄數(shù)據(jù)的個(gè)數(shù)
	if(n3-m3==2)               //把需要排序的數(shù)據(jù)賦給數(shù)組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++)              //對數(shù)據(jù)進(jìn)行簡單插入排序
		{
			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)                   //把排好序的數(shù)據(jù)重新賦給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次操作后的結(jié)果：\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];                     //選線性表的第一個(gè)元素、中間元素、最后一個(gè)元素的中項(xiàng)為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時(shí)j往前移
		{
			j=j-1;
		}
		if(i<j)                      //如果未分割完,且出現(xiàn)小于t的元素,則把a(bǔ)[j]賦給a[i]
		{
			a[i]=a[j];
			i=i+1;
			while(a[i]<=t&&i<j)     //從表頭開始,元素小于t的i往后移
			{
				i=i+1;
			}
			if(i<j)                //如果未分割完,且出現(xiàn)大于t的元素,則把a(bǔ)[i]賦給a[j]
			{
				a[j]=a[i];
				j=j-1;
			}
		}
	}
	a[i]=t;                    //I為t在線性表中所在的位置
	I=i;
	printf("第%d次操作后的結(jié)果：\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)                             //當(dāng)線性表長度大于3時(shí),選用快速排序
		{
			I=split(m1,n1);
			qksort(m1,I-1);
			qksort(I+1,n1);
		}
		else insort(m1,n1);                    //當(dāng)線性表長度不大于3時(shí),選用簡單插入排序
	}
	return;
}


void main()
{
	
	int i,c;
	print();                              //打印界面頭部
AA:	count=0;
	max=input();                          //輸入數(shù)據(jù),返回?cái)?shù)據(jù)個(gè)數(shù)
	qksort(0,max-1);                      //快速排序
	printf("最后結(jié)果為：\n");            //打印結(jié)果
	for(i=0;i<max;i++)
		printf(" %d ",a[i]);
	printf("\n謝謝使用！");
	printf("\n************************************************************************\n");
	printf("**************************************************************************\n");
 	printf("請選擇您要進(jìn)行的操作：1、繼續(xù)       0、退出\n");
 	printf("**************************************************************************\n");
 	scanf("%d",&c);
 	if(c==1)goto AA;
  	else
	return;
}