直接.cpp

是数据结构中的内部排序算法

/*做一个大的综合程序,里面有很多不同的排序方法,分别处理给出的随机数组,得出它们各自进行 比较 和 调换 的次数. */

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define maxsize 1000
typedef struct node node; 
int num[maxsize+1];
int num0[maxsize+1];
struct node
{
	int haoma;
	int nnn;
	node *next;
};

node *num4[maxsize+1];

void randon() //生成随机的1000个数
{
	int i;
	for(i=1;i<=maxsize;i++)
	{
		num[i]=rand()%1000;
		printf("%5d",num[i]);
	}
	printf("\n");  
}


void insertsort()  //   1.直接插入法!!
{
	int i,j,compare=0,change=0;    //compare是比较次数,change是调换次数
	int num1[maxsize+1];
	for(i=1;i<=maxsize;i++) //为了不破坏原来的数组,只能重新定义一个和它一样的进行处理
		num1[i]=num[i];

	for(i=2;i<=maxsize;i++)   //排成从小到大
	{
		if(num1[i]<num1[i-1])
		{
			compare++;//比较次数加1
			num1[0]=num1[i];
		    num1[i]=num1[i-1];
			change++;change++;//change加2
			for(j=i-2;num1[j]>num1[0];j--)
			{
				num1[j+1]=num1[j];
				compare++; 
				change++;
			}
			num1[j+1]=num1[0];
			change++;
		}  
	}
/*	printf("经过直接排序法后的数组为:\n");
	for(i=1;i<=maxsize;i++)
		printf("%5d",num1[i]);  
	printf("\n");  */
	printf("直接排序法:1.关键字比较次数为%5d;  2.交换次数为%5d \n",compare,change);  
}

void binsertsort()   //  2.折半插入法!!
{
	int i,j,mid,low,high,compare=0,change=0;
	int num2[maxsize+1];
	for(i=1;i<=maxsize;i++)
		num2[i]=num[i];

	for(i=2;i<=maxsize;i++)
	{
		change++; 
		num2[0]=num2[i];
		low=1;high=i-1;
		while(low<=high)
		{
			mid=(low+high)/2;
			compare++;
			if(num2[mid]>num2[0])
				high=mid-1;
			else
				low=mid+1;
		}
		for(j=i-1;j>=high+1;j--)
		{
			change++;
			num2[j+1]=num2[j];
		}
		num2[high+1]=num2[0];
		change++;
	}
/*	printf("经过折半插入法后的数组为:\n");
	for(i=1;i<=maxsize;i++)
		printf("%5d",num2[i]);  */
	printf("\n");  
	printf("折半插入法:1.关键字比较次数为%5d;  2.交换次数为%5d \n\n",compare,change);


}


void initial()
{
	int i;
	for(i=1;i<=maxsize;i++)
	{
		num4[i]=(node *)malloc(sizeof(node));
		num4[i]->haoma=i;
		num4[i]->nnn=num[i];
		num4[i]->next=NULL;
	}
    num4[0]=(node *)malloc(sizeof(node));
	num4[0]->haoma=0;
	num4[0]->nnn=0;
	num4[0]->next=num4[1];
	num4[1]->next=num4[0];
}

int arrange()
{
	int i,cunchu=0;
	node *p1;
	node *temp,*temp1;
	temp=(node *)malloc(sizeof(node));
	temp1=(node *)malloc(sizeof(node));
	p1=num4[0]->next;
	for(i=1;i<=maxsize;i++)
	{
		while(p1->haoma<i)
			p1=p1->next;
		if(i!=p1->haoma)
		{
			temp->nnn=num4[i]->nnn;
			temp->next=num4[i]->next;
			num4[i]->nnn=p1->nnn;
			num4[i]->next=p1;
			temp1->next=p1->next;
			p1->nnn=temp->nnn;
			p1->next=temp->next;
			cunchu++;
		}
		p1=temp1->next;
	}
/*	for(i=1;i<=maxsize;i++)
	{
		printf("%5d",num4[i]->nnn);
	}  */
	return (cunchu);

}

void blanksertsort()  //  表插入排序法!!
{
	int i,cunchu1=0,cunchu2=0,comparex=0;
    node *p1,*p2;
	initial();
    for(i=2;i<=maxsize;i++)
	{
		for(p2=num4[0],p1=p2->next;p1!=num4[0];p2=p1,p1=p1->next)
		{
			if(num4[i]->nnn <= p1->nnn)
			{
				comparex++;
				p2->next=num4[i];
				num4[i]->next=p1;
				cunchu1++;
				break;
			}
		}
		if(p1==num4[0])
		{
			comparex++;
			p2->next=num4[i];
			num4[i]->next=num4[0];
			cunchu1++;
		}
	}
/*	printf("经过表插入法后的数组为:\n"); 
	for(p1=num4[0]->next;p1!=num4[0];p1=p1->next)
		printf("%5d",p1->nnn);
	printf("\n");  */
	cunchu2=arrange();
	printf("表插入排序法:1.关键字比较次数为%5d;  2.交换次数为 %5d \n",cunchu1+cunchu2,comparex);
}

void shellsort()
{
	int compare=0,change=0;
	int i,j,m,k;
	int num1[maxsize+1];
	for(i=1;i<=maxsize;i++)
		num1[i]=num[i];
    for(k=maxsize/2;k>=1;k--)//这里k得递减规律不明??
	{
		for(i=0;i<k;i++)
		{
			for(j=i+k;j<=maxsize;j+=k)
			{
				if(num1[j]<num1[j-k])
				{
					compare++;
					change++;
					num1[0]=num1[j];
					for(m=j;m>k&&num1[m-k]>num1[0];m-=k)
					{
						compare++;
						change++;
						num1[m]=num1[m-k];
					}
					num1[m]=num1[0];
					change++;
				}
			}

		}
	}
/*	printf("经过希尔排序法后的数组为:\n");
	for(i=1;i<=maxsize;i++)
		printf("%5d",num1[i]);  */
	printf("\n");   
	printf("希尔排序法:1.关键字比较次数为%5d;  2.交换次数为%5d \n\n",compare,change);

}
void bubblesort()
{
	int compare=0,change=0; 
	int i,j;
	int num1[maxsize+1];
	for(i=1;i<=maxsize;i++)
		num1[i]=num[i];

	for(i=1;i<=maxsize-1;i++)
	{
		for(j=1;j<=maxsize-i;j++)
		{
			compare++;
			if(num1[j]>num1[j+1])
			{
				change++;
				num1[0]=num1[j];
				num1[j]=num1[j+1];
				num1[j+1]=num1[0];
			}
		}
	}
 /* printf("经过起泡排序法后的数组为:\n");
	for(i=1;i<=maxsize;i++)
		printf("%5d",num1[i]);  */
	printf("\n");  
	printf("起泡排序法:1.关键字比较次数为%5d;  2.交换次数为%5d \n\n",compare,change);
}
 

int compare0=0,change0=0;

int partition(int low,int high)
{
	num0[0]=num0[low];
    int	pivotkey=num0[low];
	while(low<high)
	{
		while(low<high && num0[high]>=pivotkey)
		{
			high--;
			compare0++;
		}
		num0[low]=num0[high];
		change0++;
		while(low<high && num0[low]<=pivotkey)
		{
			low++;
			compare0++;
		}
		num0[high]=num0[low];
		change0++;
	}
	num0[low]=num0[0];
	return low;
}

void qsort(int low,int high)
{
	int pivotloc;
	if(low<high)
	{
		pivotloc=partition(low,high);
		qsort(low,pivotloc-1);
		qsort(pivotloc+1,high);
	}

}


void quicksort()
{
	int i;
	for(i=1;i<=maxsize;i++)
		num0[i]=num[i];
	printf("\n"); 
	qsort(1,maxsize);
/*	printf("经过快速排序法后的数组为:\n");
	for(i=1;i<=maxsize;i++)
		printf("%5d",num0[i]);  */
	printf("\n"); 
	printf("快速排序法:1.关键字比较次数为%5d;  2.交换次数为%5d \n\n",compare0,change0); 
}

int compare1=0,change1=0;
void heapadjust(int numx[],int s,int m)
{
	int j;
	int rc=numx[s];
	for(j=2*s;j<=m;j*=2)  //沿数值较大的孩子结点向下筛选
	{
		if(j<m && numx[j]<numx[j+1])  //j为数值较大的记录的下标
		{
			j++;
			compare1++;
		}
		if(!(rc<numx[j]))  //rc应插入在位置s上
			break;
		numx[s]=numx[j];
		s=j;
		compare1++;
		change1++;
	}
	numx[s]=rc;       //插入
	change1++;
}


void heapsort()
{
	int num1[maxsize+1];
	int i;
	for(i=1;i<=maxsize;i++)
		num1[i]=num[i];
	printf("\n");  
	for(i=maxsize/2;i>0;i--)
	{
		heapadjust(num1,i,maxsize);  //把num1建成大顶堆
	}
	for(i=maxsize;i>1;i--)
	{
		num1[0]=num1[1];  //将堆顶记录和当前未经排序子序列num1[1]--num1[i]中最后一个记录相互交换
		num1[1]=num1[i];
		num1[i]=num1[0];
		change1++;
		heapadjust(num1,1,i-1);  //将num1[1]--num1[i-1]重新调整为大顶堆
	}
/*  printf("经过堆排序法后的数组为:\n");
	for(i=1;i<=maxsize;i++)
		printf("%5d",num1[i]);  
	printf("\n"); */
	printf("堆排序法:1.关键字比较次数为%5d;  2.交换次数为%5d \n\n",compare1,change1);   

}



int compare3=0,change3=0;
void merge(int numx[],int s,int t)
{
	int i,j,k;
	int numx1[maxsize+1];
	int m=(s+t)/2;
	for(i=s,j=m+1,k=s; i<=m && j<=t; k++)
	{
		compare3++;
		if(numx[i]<=numx[j])
		{
			change3++;
			numx1[k]=numx[i];
			i++;
		}
		else
		{
			change3++;
			numx1[k]=numx[j];
			j++;
		}
	}
	if(i<=m)
	{
		for(;i<=m;i++,k++)
			numx1[k]=numx[i];
	}
	if(j<=t)
	{
		for(;j<=t;j++,k++)
			numx1[k]=numx[j];
	}
	for(k=s;k<=t;k++)
		numx[k]=numx1[k];

}

void msort(int numx[],int s,int t)
{
	int m;
	if(s==t)
		return;
	else
	{
		m=(s+t)/2;
		msort(numx,s,m);
		msort(numx,m+1,t);
	    merge(numx,s,t);
	}

}

void mergesort()
{
	int num2[maxsize+1];
	int i;
    for(i=1;i<=maxsize;i++)
		num2[i]=num[i];
	printf("\n");  
	msort(num2,1,maxsize);
/*	printf("经过2-路归并排序后的数组为:\n");
	for(i=1;i<=maxsize;i++)
		printf("%5d",num2[i]);  
	printf("\n"); */
	printf("2-路归并排序法:1.关键字比较次数为%5d;  2.交换次数为%5d \n\n",compare3,change3);   
}


void main()
{
	printf("以下是1000个所要进行排序的数:\n");
	randon();
	insertsort();   //  1.直接插入法!!
	binsertsort();  //  2.折半插入法!!
	blanksertsort();   //  3.表插入排序法!!
	shellsort();       //  4.希尔排序法!!  
	bubblesort();      //  5.起泡排序法!!
	quicksort();       //  6.快速排序法!!
	heapsort();        //  7.堆排序法!!
	mergesort();       //  8.2-路归并排序!!
}