欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-24 13:23:31
...
快速排序的相关操作
【问题描述】
      快速排序的递归和非递归算法测试
基本要求:
     (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;
}