排序.cpp

运用直接插入法或快速排序法对程序产生的正序、逆序或随机的序列进行排序

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

int com=0;
int mov=0;

struct SeqList
{
	int Max;
	int n;
	int element[100];
};

typedef struct SeqList *PSeqList;

PSeqList creat_newseq(int m,int type)   //产生序列
{
	int i1,i2;
	PSeqList palist=(PSeqList)malloc(sizeof(struct SeqList));
	
	if (palist==NULL)
	{
		printf("FAIL");
		return 0;
	}
	else
	{
		palist->n=m;
		if (type==1) //正序
		{
			i1=rand();
			for(int j1=0;j1<m; j1++)
				palist->element[j1]=i1+j1;
		}
		if(type==2) //逆序
		{
			i2=rand();
			for(int j2=m;j2>0;j2--)
			palist->element[j2]=i2-j2;		
		}
		if(type==3) //随机
		{			
			for (int j3=0;j3<m;j3++)
			palist->element[j3]=rand();
		}
		return palist;
	}
}

void insertSort_seq(PSeqList palist)   //直接插入法
{
	int i,j;        //com和mov分别记录比较和移动次数
	int temp;

	for (i=1;i<palist->n;i++)
	{
		temp=palist->element[i];    //移动
		j=i-1;
		mov++;

		while (1) 
		{
			if ((temp<palist->element[j])&&(j>=0))
			{
			    palist->element[j+1]=palist->element[j];     //比较和移动
			    j--;
			    com++;
			    mov++;
			}
			else {
			    com++;
				break;
			}
		}
		/*
		while((temp<palist->element[j])&&(j>=0))    
		{
			palist->element[j+1]=palist->element[j];     //比较和移动
			j--;
			com++;
			mov++;
		}
		*/
		if(j!=(i-1))
		{
			palist->element[j+1]=temp;        
			mov++;
		}
	}

	return ;
}

void quickSort_seq(PSeqList palist, int l, int r)  //快速排序法
{
	int i,j,temp;
	

	if (l>=r)
		return ;
	i=l;
	j=r;
	temp=palist->element[i];
	mov++;
	while(i!=j)
	{
		while((palist->element[j]>=temp)&&(j>i))
		{
			j--;
			com++;
		}
		
		if(i<j)
		{
			palist->element[i++]=palist->element[j];
			mov++;
		}
		while((palist->element[i]<=temp)&&(j>i))
		{
			i++;
			com++;
		}
		if (i<j)
		{
			palist->element[j--]=palist->element[i];
			mov++;
		}
	}
	palist->element[i]=temp;
	mov++;
	quickSort_seq(palist,l,i-1);
	quickSort_seq(palist,i+1,r);

	return ;
}
	


int main()
{
	int m,stype,ttype;
	PSeqList palist;

	printf("please put in a number:20 or 50 or 100\n");
	scanf("%d",&m);
	printf("plesse choose which type of sequentlist:1(up to down) or 2(down to up) or 3(random)\n");
	scanf("%d",&stype);
	printf("please choose which way to sort the sequence: 1(insert) or 2(quick)\n");
	scanf("%d",&ttype);

	palist=creat_newseq(m,stype);

	if(ttype==1)
	{
		insertSort_seq(palist);
		printf("比较次数是%d\n移动次数是%d\n",com,mov);
	}
	else if(ttype==2)
	{
		quickSort_seq(palist,0,m);
		printf("比较次数是%d\n移动次数是%d\n",com,mov);
	}
	else
		printf("Fail");

	return 0;
}