11.cpp

关于快速

#include <stdio.h>
#include <stdlib.h>
#define LeftChild(i) (2*(i)+1)
#define MAX 1000                         /* 数组最大界限 */
typedef int ElemType;                    /* 关键字的类型 */
typedef  struct 
{ 
	ElemType key;                  
    int shu;                        /*   其它属性域   */
}Data;                          /* 一个纪录的结构体类型 */
Data  ar[MAX],br[MAX];                  
typedef struct  
{ 
	int lo,hi;
}Selem;                          /* 栈的元素结构体类型 */
typedef struct 
{ 
	Selem elem[MAX];                /* 一维数组子域 */
    int top;                          /* 栈顶指针子域    */
}SqStack;                         /* 栈的顺序结构体类型 */
SqStack  s1;

void  bubble(Data *ary,int n);
int partition(Data * a, int start, int stop);
void quicksort(Data * a, int start, int stop);
void PerDown(Data *a,int i,int N);
void Heapsort(Data *a,int N);
void Insertionsort(Data *a,int n); 
int ChangTimes=0,CompTimes=0;


void getrandat(Data *ary,int count)    /*  产生一批随机数，准备排序 */
{ 
	long int a=100001;
	int i;
	for(i=0;i<count;i++)
	{    
		//a=(a*125)%2796203;
		a=rand()%10000;
		ary[i].key=(int)a;
	}
} /* getrandat */

void prdata(Data  ary[],int count)    /*  输出数据的函数 */
{ 
	int i;  char ch;
	printf("\n");
	for(i=0;i<count;i++) printf("%6d ",ary[i].key);
	printf("\n");
	printf("\n\n   打回车键，结束显示。");
} /* prdata */

int main()
{ 
	int k,n,j; j;  char ch;
   	do{ 
	       printf("\n\n     1. 产生一批随机数准备排序 ");
	       printf("\n\n     2. 一般情况的冒泡排序");
	       printf("\n\n     3. 有序情况的冒泡排序");
		   printf("\n\n     4. 一般情况的快速排序");
	       printf("\n\n     5. 有序情况的快速排序");
	       printf("\n\n     6. 一般情况的堆排序");
	       printf("\n\n     7. 有序情况的堆排序");
	       printf("\n\n     8. 一般情况的插入排序");
	       printf("\n\n     9. 有序情况的插入排序");
	       printf("\n\n     0. 结束程序运行");
	       printf("\n======================================");
	       printf("\n     请输入您的选择 (0,1,2,3,4,5,6,7,8,9)");
	       scanf("%d",&k);
	       switch(k)
		   { 
	   			case 1:
		   		{ 
				   printf("the number of datas:"); /* 输入数据个数 */
	               scanf("%d",&n);
	               getrandat(ar,n);  /*产生n个随机数 */
	               for(j=0;j<n;j++)
   				       br[j]=ar[j];  /* 保留复原始数据 */
		   		   prdata(ar,n);
	    		} break;
		        case 2:
				{ 
					for(j=0;j<n;j++) 
						ar[j]=br[j];       /* 恢复原始数据 */
	                    bubble(ar,n);                /* 对n个数据冒泡排序 */
	                prdata(ar,n);                       /* 排序后输出 */
	                printf("交换次数：%d,比较次数：%d。",ar[0].shu,ar[1].shu);
	            } break; 
		        case 3: 
				{   
					bubble( ar,n);            /* 有序情况的冒泡排序 */
	                prdata(ar,n);
	                printf("交换次数：%d,比较次数：%d。",ar[0].shu,ar[1].shu);
	            } break;
		        case 4:
				{ 
					ChangTimes=CompTimes=0;
					for(j=0;j<n;j++) 
						ar[j]=br[j]; /* 恢复原始数据 */
     				//qksort(ar,n);            /* 对n个数据快速排序 */
     				quicksort(ar,0,n-1);
	                prdata(ar,n);                   /* 排序后输出 */
	                printf("交换次数：%d,比较次数：%d。",ChangTimes,CompTimes);
	            } break;
		        case 5:
				{ 
					ChangTimes=CompTimes=0;
					//qksort(ar,n);           /* 有序情况的快速排序 */
					quicksort(ar,0,n-1);
	                prdata(ar,n);
	                printf("交换次数：%d,比较次数：%d。",ChangTimes,CompTimes);
	            } break;
	            case 6:
				{ 
					ChangTimes=CompTimes=0;
					for(j=0;j<n;j++) 
						ar[j]=br[j]; /* 恢复原始数据 */
     				Heapsort(ar,n);
	                prdata(ar,n);                   /* 排序后输出 */
	                printf("交换次数：%d,比较次数：%d。",ChangTimes,CompTimes);
	            } break;
		        case 7:
				{ 
					ChangTimes=CompTimes=0;
					Heapsort(ar,n);
	                prdata(ar,n);
	                printf("交换次数：%d,比较次数：%d。",ChangTimes,CompTimes);
	            } break;
	            case 8:
				{ 
					ChangTimes=CompTimes=0;
					for(j=0;j<n;j++) 
						ar[j]=br[j]; /* 恢复原始数据 */
     				Insertionsort(ar,n);
	                prdata(ar,n);                   /* 排序后输出 */
	                printf("交换次数：%d,比较次数：%d。",ChangTimes,CompTimes);
	            } break;
		        case 9:
				{ 
					ChangTimes=CompTimes=0;
					Insertionsort(ar,n);
	                prdata(ar,n);
	                printf("交换次数：%d,比较次数：%d。",ChangTimes,CompTimes);
	            } break;
		   		case 0: exit(0);
		  } /*  switch  */
		  printf("\n ----------------");
	}while(k>=0 && k=<9);
     printf("\n               再见！");
     printf("\n        打回车键，返回。");
	 system("pause");
} 
void  bubble(Data *ary,int n)
{
	int i,j,flag=1;						//flag交换完毕标签 
	Data temp;
	ary[0].shu=0;						//记录交换次数 
	ary[1].shu=0;						//记录比较次数 
	for(i=0;flag&&(i<n-1);i++)
	{
		flag=0;		
		for(j=0;j<n-1;j++)
		{
			ary[1].shu++;
			if(ary[j].key>ary[j+1].key)
			{
				temp=ary[j];
				ary[j]=ary[j+1];
				ary[j+1]=temp;
				ary[0].shu++;
				flag=1;
			}
		}
	}
}
void Exchange(Data *a,Data *b)
{
	Data temp;
	ChangTimes++;
	temp.key=a->key;
	a->key=b->key;
	b->key=temp.key;
}
int isLess(Data a,Data b)
{
	CompTimes++;
	if(a.key<b.key)
		return 1;
	else return 0;
}
int partition(Data * a, int start, int stop)
{
	int up,down;
	up = start, down = stop -1;
	Data part = a[stop];
	if (stop <= start) return start;
	while (true)
	{
		while (isLess(a[up], part))
			up++;
		while (isLess(part, a[down]) && (up < down))
			down--;
		if (up >= down) break;
		Exchange(&a[up], &a[down]);
		up++; down--;
	}
	Exchange(&a[up], &a[stop]);
	return up;
}
void quicksort(Data * a, int start, int stop)
{
	int i;
	if (stop <= start) return;
	i = partition(a, start, stop);
	quicksort(a, start, i - 1);
	quicksort(a, i + 1, stop);
}
void PerDown(Data *a,int i,int N)
{
	int Child;
	Data tmp;
	for(tmp.key=a[i].key;LeftChild(i)<N;i=Child)
	{
		Child=LeftChild(i);
		if(Child!=N-1&&a[Child+1].key>a[Child].key)
			Child++,CompTimes++;
		if(tmp.key<a[Child].key)
			a[i].key=a[Child].key,CompTimes++;
		else
			break;
	}
	a[i].key=tmp.key;
}
void Heapsort(Data *a,int N)
{
	int i;
	for(i=N/2;i>=0;i--)
		PerDown(a,i,N);
	for(i=N-1;i>0;i--)
	{
		Exchange(&a[0],&a[i]);
		PerDown(a,0,i);
	}
}
void Insertionsort(Data *a,int n)
{
	int j,p;
	Data tmp;
	for(p=1;p<n;p++)
	{
		tmp.key=a[p].key;
		for(j=p;j>0&&(a[j-1].key>tmp.key);j--)
			a[j].key=a[j-1].key,CompTimes++,ChangTimes++;
		a[j].key=tmp.key;
		CompTimes++;
	}
}