数据结构实验之排序算法及其应用【附代码&实验成果】

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了数据结构实验之排序算法及其应用【附代码&实验成果】，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6784字，纯文字阅读大概需要10分钟。

内容图文

一、实验目的

1）理解并掌握各种常用内部排序算法的基本概念、思想和方法。掌握常用内部排序算法流程。
2）掌握常用的排序方法，深刻理解排序的定义和各种排序方法的特点。
3）通过实验观察不同方法的不同之处，记录并分析各种排序方法的结果。

二、实验环境

1）自备计算机，windows操作系统以及相关的编译器（如Devc++）。

三、实验要求

1）理解及熟练运用直接插入排序、快速排序、堆排序和归并排序、哈希排序等内部排序算法。
2）通过计数统计各算法的关键字比较次数和关键字移动次数。
3）分析算法的时间复杂度、空间复杂度及稳定性等各项指标。

四、实验内容

代码如下：
实验内容2&3：

#include <bits/stdc++.h>
using namespace std;
#define randnum 10 //随机数的个数定为10
//直接插入
void xx_insertsort(int a[]) {
    for(int i=2; i<=randnum; i++) {
        if(a[i] < a[i-1]) {
            a[0]=a[i];
            a[i]=a[i-1];
            for(int j=i-2; a[0]<a[j]; --j) {
                a[j+1]=a[j];
            }//for往前搜索是否存在不恰当的位置存储a[j+1]=a[0];//最终待插入元素的位置确定
        } //if表示如果待插入元素是小于前面的元素
    }
}
//折半插入排序
void xx_binsertsort(int a[]) {
    int m=0;
    for(int i=2; i<=randnum; i++) {
        a[0]=a[i];
        int low=1;
		int high=i-1;
        while(low <= high) {
            m=(low+high)/2;
            if(a[0]<a[m]) {
                high=m-1; //表示在前半段
            }else low=m+1;
        } //while循环查找待查元素的应放位置high+1
        
		for(int j=i-1; j>=high+1; --j) {
            a[j+1]=a[j];
            a[high+1]=a[0]; //最后将待查元素放入到high+1位置
		}
	}
}   
int main(){
    int xx_irand[randnum+1];
    for(int i=1; i<randnum; i++) {
        xx_irand[i]=rand()%randnum;
    } // for循环产生随机数存数起来
    printf("直接插入排序\n");
    xx_insertsort(xx_irand);
    for(int j=1; j<randnum+1; j++) 
        printf("第%d个元素是:%d\n", j, xx_irand[j])
	printf("折半插入排序\n");
    xx_binsertsort(xx_irand);
    for(int j=1; j<randnum+1; j++) 
        printf("第%d个元素是:%d\n", j, xx_irand[j]);
	return 0;
}


实验内容4：
#include <bits/stdc++.h>
#define N 100
using namespace std;
int p,q,g=0,h=0;

//起泡排序
void gensort(int b[],int n){
	int i,j,s=0,t=0;
	for(i=0;i<n-1;i++) {
		for(j=i+1;j<n;j++) {
			t++;
			if(b[i]>b[j]) {
				int temp=b[i];
				b[i]=b[j];
				b[j]=temp;
				s+=3;
			}
		}
	}
	cout<<"移动次数="<<s<<","<<"比较次数="<<t<<end;
}

// 插入排序
typedef int KeyType
	
struct rec{
	KeyType key;
}; 
typedef rec sqlist[N];

void insertsort(sqlist b,int n) {
	int i,j,s=0,t=0;
	for(i=2;i<n;i++) {
		b[0].key=b[i].key;
		s++;
		j=i-1;
		t++;
		while(b[0].key<b[j].key) {
			b[j+1]=b[i];
			j--;
            s++;
            t++;
		}
		b[j+1]=b[0];
		s++;
	}
	cout<<"移动次数="<<s<<","<<"比较次数="<<t<<endl;
}

//折半插入排序
void so(sqlist num,int n)
{
	int s=0;
	int low,high,m; //分别指向低、高、中的位置
	int i,j,k=0,t; //i,j循环 k交换次数 t哨兵
	for(i=1;i<n;i++) {
		t=num[i].key;
		low=0;
		high=i-1;
		while(low<=high) {
			m=(low+high)/2;
			if(t<num[m].key) {
				high=m-1;
				k++;
			}
			else low=m+1;
		}
		for(j=i-1; j>=high+1; j--) {
			num[j+1].key=num[j].key;
			s++;
		}
		num[high+1].key=t;
	}
	cout<<"移动次数="<<s<<","<<"比较次数="<<k<<endl;
}


//希尔排序
void shellsort(sqlist b,int n)
{
	int i,j,gap;
	rec x;
	int s=0,t=0;
	gap=n/2;
	while(gap>0) {
		for(i=gap+1;i<n;i++) {
			j=i-gap;
			while(j>0) {
				t++;
				if(b[j].key>b[j+gap].key) {
					x=b[j];
					b[j]=b[j+gap];
					b[j+gap]=x;
					j-=gap;
					s+=3; 
				}
				else j=0;
				gap /= 2;
			}
		}
		cout<<"移动次数="<<s<<","<<"比较次数="<<t<<endl;
	}
}

// 选择排序 
void gentsort(int b,int n)
{
	int i,j,k,s=0,t=0;
	for(i=0; i<n-1; i++) {
		k=i;
		for(j=i+1; j<n; j++) {
			t++;
			if(b[k]>b[j]) k=j;
		}
		if(k!=i) {
			int temp=b[k];
			b[k]=b[i];
			b[i]=temp;
			s+=3;
		}
	}
	cout<<"移动次数="<<s<<","<<"比较次数="<<t<<endl;
} 

//快速排序
void output(qist b,int n) { //输出元素值 
    for(int i=0; i<n; i++)
        cout<<setw(4)<<b[i].key;
    cout<<endl;
} 

void display(int n,int m) { //输出计数
	cout<<"移动次数="<<n<<","<<"比较次数="<<m<<endl;
}

void BeforeSort { //初始化计数器 
	p=0; q=0;
}

void quicksort(sqlist r,int s,int t)
{
	int i=s,j=t;
	if(s<t) {
		r[0]=r[s];	p++;
		while(i<j) {
			p++;
			while(i<j&&r[j].key>=r[0].key) j--;
			r[i]=r[j];	q++;	p++;
			p++;
			while(i<j&&r[i].key<=r[0].key) i++;
			r[j]=r[i];  q++;  p++;
		}
		r[i]=r[0];  p++;
	}
	else return;
	quicksort(r,s,j-1);
	quicksort(r,j+1,t);
}

void sort(sqlist r,int s,int t) {
	BeforeSort();
	quicksort(r,s,t);
	display(p,q);
}

//2-路插入排序
void sort3(sqlist nu,int n) { //int maxn=n;
    #define max 20
	int first,final;
	int cache[max+1];
	int i,j,s=0,t=0;
	for(i=0;i<n;i++) {
		if(0==i) {
			first=0;
			final=0;
			cache[0]=nu[0].key;
		}
		else {
			if(nu[i].key>=cache[final]) {
				t++;
				final++;
				cache[final]=nu[i].key;
				s++;
			}
			else if(nu[i].key<=cache[first]) {
				t++;
				if(first==0) first=n;
				first--;
				cache[first]=nu[i].key;
				s++;
			}
			else {
				t++;
				for(j=first;nu[i].key>cache[j];) {
					if(0==j) cache[n-1]=cache[0];
					else cache[j-1]=cache[j];
					s++;  j++;
					if(j==n) j=0;
				}
				if(0==first) first=n-1;
				else first--;
				if(0==j) j=n;
				cache[j-1]=nu[i].key;
				s++;
			}
		}
	}
	for(i=first,j=0;j<i;j++) {
		nu[j].key=cache[i];
		i++;
		if(i==n) i=0;
	}
	cout<<"移动次数="<<s<<","<<"比较次数="<<t<<endl;
}

// 二路归并 
void Merge(sqlist a,sqlist b,int low,int mid,int high)
{
	int i=low,j=mid+1,k=low;
	while( (i<=mid)&&(j<=high) ) {
		if(a[i].key<=a[j].key) {
			h++;
			b[k++]=a[i++];
			g++;
			++i;
		}
		else {
			h++;
			b[k++]=a[j++];
			g++;
			++j;
		}
		++k;
	}
	// if(i<=mid) 
	while(i<=mid) {
		b[k++]=a[i++];
		g++;
	}
	//else 
	while(j<=high) {
		b[k++]=a[j++];
		g++;
	}
} 

// 进行一趟归并 
void MergePass(sqlist a, sqlist b,int n,int lenth) {
	int i=0,k=0;
	while(i<=n-2*lenth) {
		Merge(a,b,i,i+lenth-1,i+2*lenth-1);
		i+=2*lenth;
	}
	if(i<n-lenth) 
	    Merge(a,b,i,i+lenth-1,n-1);
	else {
		for(k=i;k<=n-1;k++){
	    	b[k]=a[k];
	    	g++;
		}
	}
} 

// 进行二路归并 
void MergeSort(sqlist a, int n){
	sqlist b;
	//int* b=(int* )malloc(n*sizeof(int));
	int lenth=1;
	while(lenth<n/2+1) {
		MergePass(a,b,n,lenth);
		    lenth=2*lenth;
        MergePass(b, a, n, lenth);
            lenth=2*lenth;
	}
	cout<<"移动次数="<<g<<","<<"比较次数="<<h<<endl;
}

// 堆排序

void sift(sqlist r,int s, int m)
{
    int j;
    rec x;
    x=r[s];
	for(j=2*s;j<=m;j*=2) {
		q++;
		if(j<m&&(r[j].key<r[j+1].key))  ++j;
		q++;
		if(!(x.key<r[j].key))  break;
		r[s]=r[j];
		s=j;
		p++;
	}
}

void heapsort(sqlist &r,int m)
{
	int i;
	rec w;
	for(i=m/2; i>0; --i)  sift(r,i,m);
	for(i=m; i>1; --i) {
		w=r[i];  r[i]=r[1];  r[1]=w;
		p+=3;
		sift(r,1,i-1);
	}
}

void sorting(sqlist &r,int t)
{
	BeforeSort();
	heapsort(r,t);
	display(p,q);
}

void init(int a[]) //随机生成N个整数并 
{
	int i;
	//#define N 100
	srand((unsigned int)time(NULL));
	for(i=0; i<N; i++)  a[i]=rand()%99+1;
}

void main()
{
	int g=0,h=0,al[N],i,e=N;
	sqlist a,b,c,d,mum,R,nu,a2,b2;
	int cl[N],low=0,high=10;
	int dat[N];
	init(al)//随机产生个数
	for(i=0; i<N; i++) {
		cl[i]=al[i];
		a[i].key=al[i];
		b[i].key=al[i];
		c[i].key=al[i];
		d[i].key=al[i];
		num[i].key=al[i];
		R[i].key=al[i];
		nu[i].key=al[i];
		dat[i]=al[i];
	}
	cout<<"排序前数组:\n";
	for(i=0; i<N; i++)  cout<<setw(4)<<al[i];
	cout<<endl;
	
	cout<<"起泡排序运行结果:\n";
	gensort(al,sizeof(al)/sizeof(int));
    cout<<"插入排序运行结果:\n";
    insertsort(a,N);
    cout<<"希尔排序运行结果:\n";
    shellsort(b,N);
    cout<<"选择排序运行结果:\n";
    gentsort(cl,N);
    cout<<"快速排序运行结果:\n";
	sort(c,low,high);
    cout<<"堆排序运行结果:\n";
	sorting(d,N);
    cout<<"折半插入排序运行结果:\n";
	so(num,N);
    cout<<"二路插入排序运行结果:\n";
	sort3(mu,N);
	cout<<"二路归并的排序结果:\n";
	MergeSort(a2,N);
	cout<<"基数排序的排序结果:\n"; 
}

五、运行结果

六、实验总结

通过这次实验，我理解并掌握各种常用内部排序算法的基本概念、思想和方法。掌握常用内部排序算法流程，深刻理解排序的定义和各种排序方法的特点，能够通过计数统计各算法的关键字比较次数和关键字移动次数，分析算法的时间复杂度、空间复杂度及稳定性等各项指标。

内容总结

以上是互联网集市为您收集整理的数据结构实验之排序算法及其应用【附代码&实验成果】全部内容，希望文章能够帮你解决数据结构实验之排序算法及其应用【附代码&实验成果】所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---