compare.cpp

编程实现直接插入、冒泡排序、快速排序、直接选择排序算法

#define MAXSIZE 100 
#include <stdio.h> 
 
typedef struct 
{ 
	int key; 
}RECNODE; 

int prep,tim; //prep为比较次数，tim为比较排序进行次数

int MakeList(RECNODE *r) 
{ 
	int j,k; 
	printf("\n请输入原始顺序数据（不多于100个元素，以0结束）： "); 
	k=0; 
	scanf("%d",&j); 
	while(j!=0) 
		{ 
			k++; 
			r[k].key=j; 
			scanf("%d",&j); 
		} 
	return k; 
} 



void UnsortedList(RECNODE *r,int n) 
{ 
	int i; 
    printf("\n未进行排序前的元素顺序 ： "); 
    for(i=0;i<n;i++) 
		printf(" %d",r[i+1].key); 
		printf("\n\n"); 
} 



void SortedList(RECNODE*r,int n) 
{ 
	int i; 
	printf("进行排序后的元素顺序 ： "); 
	for(i=0;i<n;i++) 
		printf(" %d",r[i+1].key); 
		printf("\n\n\n"); 
		printf("交换或比较次数： %d\n\n",prep); 
		printf("排序操作循环次数： %d\n\n\n\n\n\n",tim); 
} 



void InsertSort(RECNODE*r,int n)//直接插入排序实现过程
{ 
	int i,j; 
	prep=0,tim=0; 

	for(i=2;i<=n;i++) 
	{ 
		r[0]=r[i]; 
		j=i-1; 
	while(r[0].key<r[j].key) 
	{ 
		r[j+1]=r[j]; 
		j--; 
		prep++; 
	} 
		r[j+1]=r[0]; 
		prep++; 
		tim++; 
	} 

} 


void BubbleSort(RECNODE *r,int n) //冒泡排序实现过程
{ 
	int i,j; 
	prep=0,tim=0; 
    RECNODE temp; 
	for(i=1;i<n;i++) 
	{ 
		for(j=n-1;j>=i;j--) 
		if(r[j+1].key<r[j].key) 
		{ 
			temp=r[j+1]; 
			r[j+1]=r[j]; 
			r[j]=temp; 
			prep++; 
		} 
		else prep++; 
	tim++; 
	} 

} 


int Partition(RECNODE*r,int*low,int*high)//快速排序中一次排序的实现
{ 
	int i,j; 
	static int s=0; 
	RECNODE temp; 
	i=*low; 
	j=*high; 
	temp=r[i]; 
	do 
	{ 
		while((r[j].key>=temp.key)&&(i<j)) 
		{ 
			j--; 
			s++; 
		} 
		if(i<j) 
		{ 
			r[i]=r[j]; 
			i++; 
			s++; 
		} 
		while((r[i].key<=temp.key)&&(i<j)) 
		{ 
			i++; 
			s++; 
		} 
		if(i<j) 
		{ 
			r[j]=r[i]; 
			j--; 
			s++; 
		} 
	}
	while(i!=j); 
		r[i]=temp; 
		prep=s; 
	return i; 
} 


void QuickSort(RECNODE*r,int start,int end)//快速排序完整实现过程
{ 
	int i; 
	static int q=0; 
	if(start<end) 
	{ 
		i= Partition(r,&start,&end); 
		q++; 
		QuickSort(r,start,i-1); 
		QuickSort(r,i+1,end); 
	} 
	tim=q; 
} 

void SelectSort(RECNODE*r,int n)//简单选择排序实现过程
{ 
	int i,j,z; 
	prep=0,tim=0; 
	RECNODE temp; 
	for(i=1;i<n;i++) 
	{ 
		z=i; 
		for(j=i+1;j<=n;j++) 
		if(r[j].key<r[z].key) 
		{ 
			z=j; 
			prep++; 
		} 
		else prep++; 
		if(z!=i) 
		{ 
			temp=r[i]; 
			r[i]=r[z]; 
			r[z]=temp; 
		} 
		tim++; 
	} 

} 

 

 



 

void main() 
{ 
	RECNODE a[MAXSIZE]; 
	int len,p; 
	do 
	{ 
         printf("**********************\n"); 
         printf("       * 菜 单 *\n"); 
         printf("**********************\n"); 
         printf("*  1---直接插入排序  *\n"); 
         printf("*  2---  冒泡排序    *\n"); 
         printf("*  3---  快速排序    *\n"); 
         printf("*  4---简单选择排序  *\n"); 
		 printf("*  0---    退出      *\n"); 
         printf("**********************\n"); 
         printf("\n请在上述序号中选择一个并输入： "); 
         scanf("%d",&p); 
        
switch(p) 
	{ 
		case 1:
			len=MakeList(a); 
			UnsortedList(a,len); 
			InsertSort(a,len); 
			SortedList(a,len); 
		break; 
           
		case 2:
			len=MakeList(a); 
			UnsortedList(a,len); 
			BubbleSort(a,len); 
			SortedList(a,len); 
		break; 
            
		case 3:
			len=MakeList(a); 
			UnsortedList(a,len); 
			QuickSort(a,1,len); 
			SortedList(a,len); 
		break; 
           
		case 4:
			len=MakeList(a); 
			UnsortedList(a,len); 
			SelectSort(a,len); 
			SortedList(a,len); 
		break; 
  
		case 0:
		break; 
           
		default:
			printf("元素类型或者元素数量超限，请重新输入\n");
		break; 
	} 
	}
	while(p!=0); 

}