排序.cpp

这是二叉树排序的一个算法实验

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
//#define	MAX	255
int	R[100000];
void Insert_Sort(int n)
{
//对数组R中的记录R[1..n]按递增序进行插入排序
	int i,j;
	for(i=2;i<=n;i++)
		if(R[i]<R[i-1])
		{
		R[0]=R[i];j=i-1;
		do{
		R[j+1]=R[j];
		j--;
		}while(R[0]<R[j]);
		R[j+1]=R[0];
		}
}				                   //插入排序
int Partition(int i,int j)
{
//调用Partition(R,low,high)时，对R[low..high]做划分，并返回基准记录的位置
	int pivot=R[i];
	while(i<j){
		while(i<j && R[j]>=pivot)
			j--;
		if(i<j)
			R[i++]=R[j];
		while(i<j && R[i]>=pivot)
			i++;
		if(i<j)
			R[j--]=R[i];
	}//endwhile
	R[i]=pivot;
	return i;
}//end of pattition
void Quick_Sort(int low,int high)
{         //  用递归方法对R[low..high]快速排序
int pivotpos;
if(low<high)                               //长度大于1
{
pivotpos=Partition(low,high);
	Quick_Sort(low,pivotpos-1);            //对底子表递归排序，pivotloc是枢轴位置
	Quick_Sort(pivotpos+1,high);           //对高子表递归排序
}
}// end of Quick_Sort			           //快速排序
void Select_Sort(int n)
{
int i,j,k;
for(i=1;i<n;i++)
{
	k=i;
	for(j=i+1;j<=n;j++)
		if(R[j]<R[k])
			k=j;
		if(k!=i)
		{
		R[0]=R[i];R[i]=R[k];R[k]=R[0];
		}//endif
}//endfor
}//end of Select Sort			//选择排序
void main()
{
int n,i,j,p,k; 
R[100000] = 0;
printf("请输入总的元素数：");
scanf("%d",&n);
srand( (unsigned)time( NULL ) ); 
for( p = 0; p < n;p++ ) 
{ 
k=rand()%n; 
R[p]=k;
//puts("得到的队列是：\n");
printf( " k=%d ", k ); 
}
if(n<=20)
{
	printf("n必须大于20000");
}
//printf("请一个一个的输入元素：\n");
//for(i=1;i<=n;i++) scanf("%d",&R[i]);
//for(i=1;i<=n;i++)
//	printf("%4d",R[i]);
printf("\n请输入要进行的排序方法：");
scanf("%d",&j);
switch(j)
{
case 0:printf("错误输入,请重新输入：");scanf("%d",&j);
case 1: Insert_Sort(n);break;
case 2: Quick_Sort(1,n);break;
case 3: Select_Sort(n);break;
}
printf("排序后的结果为：");
for(i=1;i<=n;i++)
	printf("%4d",R[i]);
}