快速排序的递归和非递归算法测试

快速排序的相关操作

【问题描述】

      快速排序的递归和非递归算法测试

基本要求：

     （1）将产生的整数序列放入文件中；

     （2）从文件中读出的数据分别用顺序表和链表存储。

测试数据要求：

     待排序序列随机产生，要求两位数且互不相同。排序个数由用户输入。 

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<stack>
#define N 40
using namespace std;
typedef struct{
	int key;
}Elemtype;
typedef struct{
	Elemtype *elem;
	int length;
}Table;
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;
void Save(int n){
	//存入文件中 
	int i,j,t,f,a[N];
	FILE *fp;
	srand(time(0));
	fp=fopen("zhengshu.txt","w");
	for(i=1;i<=n;i++){
		f=1;
		t=rand()%90+10;
		for(j=1;j<=i;j++){
			if(t==a[j])
				f=0;
		}
		if(f){
			a[i]=t; 
		}
	}
	for(i=1;i<=n;i++){
		fprintf(fp,"%d ",a[i]);
	}
	fclose(fp);
}
void Get(Table &T,int n){
	//顺序表存储 
	FILE *fp;
	int i;
	fp=fopen("zhengshu.txt","r");
	T.elem=(Elemtype *)malloc(n*sizeof(Elemtype));
	for(i=1;i<=n;i++)
		fscanf(fp,"%d ",&T.elem[i].key);
	fclose(fp);
	T.length=n;
}
void Output1(Table T){
	int i;
	for(i=1;i<=T.length;i++){
		printf("%d ",T.elem[i].key);
	}
	printf("\n");
}
void InitList(LinkList &L,int n){
	//链表存储 
	FILE *fp;
	LinkList p,pre;
	int x,i;
	fp=fopen("zhengshu.txt","r");
	L=pre=(LinkList)malloc(sizeof(LNode));
	for(i=1;i<=n;i++){
		fscanf(fp,"%d ",&x);
		p=(LinkList)malloc(sizeof(LNode));
		p->data=x;
		pre->next=p;
		pre=p;
	}
	pre->next=NULL;
}
void Output2(LinkList L){
	LinkList p;
        p=L->next;
        while(p!=NULL)
        {
            printf("%d ",p->data);
            p=p->next;
        }
        printf("\n");
}
/*快速排序递归算法*/
int Partition(Table &T,int low,int high){
	int pivotkey;
	T.elem[0]=T.elem[low];
	pivotkey=T.elem[low].key;
	while(low<high){
		while(low<high&&T.elem[high].key>=pivotkey)  --high;
		T.elem[low]=T.elem[high];
		while(low<high&&T.elem[low].key<=pivotkey)   ++low;
		T.elem[high]=T.elem[low];
	}
	T.elem[low]=T.elem[0];
	return low;
}
void QuickSort1(Table &T,int low,int high){
	int pivotloc;
	if(low<high){
		pivotloc=Partition(T,low,high);
		QuickSort1(T,low,pivotloc-1);
		QuickSort1(T,pivotloc+1,high);
	}
}
/*************************************/
/*快速排序非递归算法*/
void QuickSort2(Table &T,int low,int high){
	stack<int> st;
	if(low<high){
		int mid=Partition(T,low,high);
		if(low<mid-1){
			st.push(low);
			st.push(mid-1);
		}
		if(mid+1<high){
			st.push(mid+1);
			st.push(high);
		}
		while(!st.empty()){
			int q=st.top();
			st.pop();
			int p=st.top();
			st.pop();
			mid=Partition(T,p,q);
			if(p<mid-1){
				st.push(p);
				st.push(mid-1);
			}
			if(mid+1<q){
				st.push(mid+1);
				st.push(q);
			}
		}
	}
	
} 
/*************************************/
int main(){
	int n;
	Table T;
	LinkList L;
	printf("输入个数：");
	scanf("%d",&n);
	Save(n);
	printf("顺序表存储：\n");
	Get(T,n);
	Output1(T);
	printf("递归：\n");
	QuickSort1(T,1,T.length);
	Output1(T);
	printf("非递归：\n");
	Get(T,n);
	QuickSort2(T,1,T.length);
	Output1(T);
	printf("链表存储：\n");
	InitList(L,n);
	Output2(L);
	return 0;
} #include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<stack>
#define N 40
using namespace std;
typedef struct{
	int key;
}Elemtype;
typedef struct{
	Elemtype *elem;
	int length;
}Table;
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;
void Save(int n){
	//存入文件中 
	int i,j,t,f,a[N];
	FILE *fp;
	srand(time(0));
	fp=fopen("zhengshu.txt","w");
	for(i=1;i<=n;i++){
		f=1;
		t=rand()%90+10;
		for(j=1;j<=i;j++){
			if(t==a[j])
				f=0;
		}
		if(f){
			a[i]=t; 
		}
	}
	for(i=1;i<=n;i++){
		fprintf(fp,"%d ",a[i]);
	}
	fclose(fp);
}
void Get(Table &T,int n){
	//顺序表存储 
	FILE *fp;
	int i;
	fp=fopen("zhengshu.txt","r");
	T.elem=(Elemtype *)malloc(n*sizeof(Elemtype));
	for(i=1;i<=n;i++)
		fscanf(fp,"%d ",&T.elem[i].key);
	fclose(fp);
	T.length=n;
}
void Output1(Table T){
	int i;
	for(i=1;i<=T.length;i++){
		printf("%d ",T.elem[i].key);
	}
	printf("\n");
}
void InitList(LinkList &L,int n){
	//链表存储 
	FILE *fp;
	LinkList p,pre;
	int x,i;
	fp=fopen("zhengshu.txt","r");
	L=pre=(LinkList)malloc(sizeof(LNode));
	for(i=1;i<=n;i++){
		fscanf(fp,"%d ",&x);
		p=(LinkList)malloc(sizeof(LNode));
		p->data=x;
		pre->next=p;
		pre=p;
	}
	pre->next=NULL;
}
void Output2(LinkList L){
	LinkList p;
        p=L->next;
        while(p!=NULL)
        {
            printf("%d ",p->data);
            p=p->next;
        }
        printf("\n");
}
/*快速排序递归算法*/
int Partition(Table &T,int low,int high){
	int pivotkey;
	T.elem[0]=T.elem[low];
	pivotkey=T.elem[low].key;
	while(low<high){
		while(low<high&&T.elem[high].key>=pivotkey)  --high;
		T.elem[low]=T.elem[high];
		while(low<high&&T.elem[low].key<=pivotkey)   ++low;
		T.elem[high]=T.elem[low];
	}
	T.elem[low]=T.elem[0];
	return low;
}
void QuickSort1(Table &T,int low,int high){
	int pivotloc;
	if(low<high){
		pivotloc=Partition(T,low,high);
		QuickSort1(T,low,pivotloc-1);
		QuickSort1(T,pivotloc+1,high);
	}
}
/*************************************/
/*快速排序非递归算法*/
void QuickSort2(Table &T,int low,int high){
	stack<int> st;
	if(low<high){
		int mid=Partition(T,low,high);
		if(low<mid-1){
			st.push(low);
			st.push(mid-1);
		}
		if(mid+1<high){
			st.push(mid+1);
			st.push(high);
		}
		while(!st.empty()){
			int q=st.top();
			st.pop();
			int p=st.top();
			st.pop();
			mid=Partition(T,p,q);
			if(p<mid-1){
				st.push(p);
				st.push(mid-1);
			}
			if(mid+1<q){
				st.push(mid+1);
				st.push(q);
			}
		}
	}
	
} 
/*************************************/
int main(){
	int n;
	Table T;
	LinkList L;
	printf("输入个数：");
	scanf("%d",&n);
	Save(n);
	printf("顺序表存储：\n");
	Get(T,n);
	Output1(T);
	printf("递归：\n");
	QuickSort1(T,1,T.length);
	Output1(T);
	printf("非递归：\n");
	Get(T,n);
	QuickSort2(T,1,T.length);
	Output1(T);
	printf("链表存储：\n");
	InitList(L,n);
	Output2(L);
	return 0;
}