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

2024-07-09 13:59| 来源: 网络整理| 查看: 265

一、实验目的

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

二、实验环境

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

三、实验要求

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

四、实验内容

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

#include using namespace std; #define randnum 10 //随机数的个数定为10 //直接插入 void xx_insertsort(int a[]) { for(int i=2; i a[0]=a[i]; a[i]=a[i-1]; for(int j=i-2; a[0] int m=0; for(int i=2; i m=(low+high)/2; if(a[0] a[j+1]=a[j]; a[high+1]=a[0]; //最后将待查元素放入到high+1位置 } } } int main(){ int xx_irand[randnum+1]; for(int i=1; i int i,j,s=0,t=0; for(i=0;i t++; if(b[i]>b[j]) { int temp=b[i]; b[i]=b[j]; b[j]=temp; s+=3; } } } cout int i,j,s=0,t=0; for(i=2;i b[j+1]=b[i]; j--; s++; t++; } b[j+1]=b[0]; s++; } cout t=num[i].key; low=0; high=i-1; while(low 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 for(i=gap+1;i 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 k=i; for(j=i+1; j int temp=b[k]; b[k]=b[i]; b[i]=temp; s+=3; } } cout //输出计数 cout int i=s,j=t; if(s p++; while(i=r[0].key) j--; r[i]=r[j]; q++; p++; p++; while(i //int maxn=n; #define max 20 int first,final; int cache[max+1]; int i,j,s=0,t=0; for(i=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 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 int i=low,j=mid+1,k=low; while( (i h++; b[k++]=a[i++]; g++; ++i; } else { h++; b[k++]=a[j++]; g++; ++j; } ++k; } // if(i b[k++]=a[j++]; g++; } } // 进行一趟归并 void MergePass(sqlist a, sqlist b,int n,int lenth) { int i=0,k=0; while(i for(k=i;k sqlist b; //int* b=(int* )malloc(n*sizeof(int)); int lenth=1; while(lenth int j; rec x; x=r[s]; for(j=2*s;j 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 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

【本文地址】

公司简介

联系我们