9-2.txt

数据结构源程序

/*排序的基本运算与实现*/
#include <stdio.h>
#define MAX 16
typedef struct
{
	int key;
}datatype;
void menu();
void initialization(datatype R[]);
void D_InsertSort(datatype R[],int n);
void B_InsertSort(datatype R[],int n);
void ShellSort(datatype R[],int d[],int t);
void ShellInsert(datatype R[],int dk);
void Bubble_Sort(datatype R[],int n);
int Partition(datatype R[],int low,int high);
void Quick_Sort(datatype R[],int low,int high);
void Select_Sort(datatype R[],int n);
void Heap_Sort(datatype R[],int n);
void HeapAdjust(datatype R[],int s,int t);
void Merge_Sort(datatype R[],int n);
void MergePass(datatype R[],datatype R1[],int len,int n);
void Merge(datatype R[],datatype R1[],int s,int m,int t);
void main()
{
	int n,m=1;
	datatype R[MAX];
	while(m)
	{
		int i;
		menu();
		initialization(R);
		scanf("%d",&n);
		printf("\n\n");
		switch(n)
		{
			case 1:	{
					int i;
					D_InsertSort(R,MAX-1);
					for(i=1;i<MAX;i++)
					{
						printf("%4d",R[i].key);
					}
					break;
				}
			case 2:	{
					int i;
					B_InsertSort(R,MAX-1);
					for(i=1;i<MAX;i++)
					{
						printf("%4d",R[i].key);
					}
					break;
				}
			case 3:	{
					int d[3]={5,3,1},t=3;
					ShellSort(R,d,t);
					for(i=1;i<MAX;i++)
					{
						printf("%4d",R[i].key);
					}
					break;
				}
			case 4: {
					int i;
					Bubble_Sort(R,MAX-1);
					for(i=1;i<MAX;i++)
					{
						printf("%4d",R[i].key);
					}
					break;
				}
			case 5: {
					int i,low=1;
					Quick_Sort(R,low,MAX-1);
					for(i=1;i<MAX;i++)
					{
						printf("%4d",R[i].key);
					}
					break;
				} 
			case 6: {
					int i;
					Select_Sort(R,MAX-1);
					for(i=1;i<MAX;i++)
					{
						printf("%4d",R[i].key);
					}
					break;
				}
			case 7: {
					int i;
					Heap_Sort(R,MAX-1);
					for(i=1;i<MAX;i++)
					{
						printf("%4d",R[i].key);
					}
					break;
				}
			case 8:{
					int i;
					Merge_Sort(R,MAX-1);
					for(i=1;i<MAX;i++)
					{
						printf("%4d",R[i].key);
					}
					break;
				}

			case 0: m=0;
		}
	}
}
void menu()
{
	/*clrscr();*/
	printf("\n\n\n");
	printf("\t\t1.zhi jie cha ru sort\n\n");
	printf("\t\t2.zhe ban cha ru sort\n\n");
	printf("\t\t3.shell sort\n\n");
	printf("\t\t4.Bubble sort\n\n");
	printf("\t\t5.Quick sort\n\n");
	printf("\t\t6.Select sort\n\n");
	printf("\t\t7.Heap sort\n\n");
	printf("\t\t8.Merge sort\n\n");
	printf("\t\t0.exit\n\n");
	printf("\n\n\n\tplease select:");
}
void initialization(datatype R[])
{
	R[0].key=0;
	R[1].key=39;
	R[2].key=80;
	R[3].key=76;
	R[4].key=41;
	R[5].key=13;
	R[6].key=29;
	R[7].key=50;
	R[8].key=78;
	R[9].key=30;
	R[10].key=11;
	R[11].key=100;
	R[12].key=7;
	R[13].key=41;
	R[14].key=86;
	R[15].key=21;
}
void D_InsertSort(datatype R[],int n)
{
	int i,j;
	for(i=2;i<=n;i++)
	{
		if(R[i].key<R[i-1].key)
		{
			R[0]=R[i];
			for(j=i-1;R[0].key<R[j].key;j--)
			{
				R[j+1]=R[j];
			}
			R[j+1]=R[0];
		}
	}
}
void B_InsertSort(datatype R[],int n)
{
	int i,j,low,high,mid;
	for(i=2;i<=n;i++)
	{
		R[0]=R[i];
		low=1;
		high=i-1;
		while(low<=high)
		{
			mid=(low+high)/2;
			if(R[0].key>R[mid].key)
				low=mid+1;
			else
				high=mid-1;
		}
		for(j=i-1;j>=high+1;j--)
		{
			R[j+1]=R[j];
		}
		R[high+1]=R[0];
	}
}
void ShellSort(datatype R[],int d[],int t)
{
	int k;
	for(k=0;k<t;k++)
	{
		ShellInsert(R,d[k]);
	}
}
void ShellInsert(datatype R[],int dk)
{
	int i,j;
	for(i=dk+1;i<=MAX-1;i++)
	{
		if(R[i].key<R[i-dk].key)
		{
			R[0]=R[i];
			for(j=i-dk;(j>0)&&(R[0].key<R[j].key);j=j-dk)
			{
				R[j+dk]=R[j];
			}
			R[j+dk]=R[0];
		}
	}
}
void Bubble_Sort(datatype R[],int n)
{
	int i,j,swap;
	for(i=1;i<n-1;i++)
	{
		swap=0;
		for(j=1;j<=n-i;j++)
		{
			if(R[j].key>R[j+1].key)
			{
				R[0]=R[j];
				R[j]=R[j+1];
				R[j+1]=R[0];
				swap=1;
			}
		}
		if(swap==0) break;
	}
}
int Partition(datatype R[],int low,int high)
{
	R[0]=R[low];
	while(low<high)
	{
		while(low<high&&R[high].key>=R[0].key)
			high--;
		if(low<high)
		{
			R[low]=R[high];
			low++;
		}
		while(low<high&&R[low].key<R[0].key)
			low++;
		if(low<high)
		{
			R[high]=R[low];
			high--;
		}
	}
	R[low]=R[0];
	return low;
}
void Quick_Sort(datatype R[],int low,int high)
{
	int i;
	if(low<high)
	{
		i=Partition(R,low,high);
		Quick_Sort(R,low,i-1);
		Quick_Sort(R,i+1,high);
	}
}
void Select_Sort(datatype R[],int n)
{
	int i,j,k;
	for(i=1;i<n;i++)
	{
		for(k=i,j=i+1;j<=n;j++)
		{
			if(R[j].key<R[k].key)
				k=j;
		}
		if(i!=k)
		{
			R[0]=R[k];
			R[k]=R[i];
			R[i]=R[0];
		}
	}
}
void Heap_Sort(datatype R[],int n)
{
	int i;
	for(i=n/2;i>0;i--)
	{
		HeapAdjust(R,i,n);
	}
	for(i=n;i>=1;i--)
	{
		R[0]=R[1];
		R[1]=R[i];
		R[i]=R[0];
		HeapAdjust(R,1,i-1);
	}
	return;
}
void HeapAdjust(datatype R[],int s,int t)
{
	datatype rc;
	int i,j;
	rc=R[s];
	i=s;
	for(j=2*i;j<=t;j=2*j)
	{
		if((j<t)&&(R[j].key<R[j+1].key))
		{
			j=j+1;
		}
		if(rc.key>R[j].key)
		{
			break;
		}
		R[i]=R[j];
		i=j;
	} /* end for j */
	R[i]=rc;
	return;
}
void Merge_Sort(datatype R[],int n)
{
	datatype R1[MAX];
	int len = 1;
	while(len < n)
	{
		MergePass(R,R1,len,n);
		len = 2*len;
	}
}
void MergePass(datatype R[],datatype R1[],int len,int n)
{
	int i;
	for(i=1;i+2*len-1<=n;i=i+2*len)
	{
		Merge(R,R1,i,i+len-1,i+2*len-1);
	}
	if(i+len-1 < n)
	{
		Merge(R,R1,i,i+len-1,n);
	}
	else if(i <= n)
	{
		while(i <= n)
		{
			R1[i] = R[i];
			i++;
		}
	}
	for(i=1;i<=n;i++)
	{
		R[i] = R1[i];
	}
}
void Merge(datatype R[],datatype R1[],int s,int m,int t)
{
	int i = s , j = m+1 , k = s;	
	while((i <= m)&&(j <= t))
	{
		if(R[i].key < R[j].key)
		{
			R1[k] = R[i];
			k++;
			i++;
		}
		else
		{
			R1[k] = R[j];
			k++;
			j++;
		}
	}
	while(i <= m)
	{
		R1[k] = R[i];
		k++;
		i++;
	}
	while(j <= t)
	{
		R1[k] = R[j];
		k++;
		j++;
	}
}