内部排序问题(数据结构和算法分析课程设计)

#include <cstdlib> #include <iostream> #define N 11 // 用来存排序用的数据，其中第一个元素经常作为“哨兵”和交换用 int sjs[7],sjj[7],kjs[7],kjj[7]; //分别用来描述排序所用的时间和空间性能,从第二个 元素开始使用 int sum; //用来计排序的次数 int sm[N]; //用来作为辅助存储空间，用于2-路归并排序中 using namespace std; //函数声明 int zjcr(int s[]); int jdxz(int s[]); int ddpx(int s[],int n); int mppx(int s[]); int kspx(int s[],int low,int high); int gbpx(int s[],int sm[],int n); int main() { cout<<"*********************************************************************"<<endl; cout<<" 内 部 排 序 问 题 "<<endl; cout<<"*********************************************************************"<<endl; cout<<" "<<endl; cout<<" 2006级 计算机科学与技术专业 王 琼 2006180728 "<<endl; int ch,c=1; //其中ch用来标记所选择的排序方法，c用来判断是否推出排序程序 while(c!=0) { cout<<"\n====================================================================="<<endl; cout<<"请选择您要用的排序方法： "<<endl; cout<<" 0 退出排序程序"<<endl; cout<<" 1 直接插入排序 2 简单选择排序"<<endl; cout<<" 3 堆排序 4 冒泡排序 "<<endl; cout<<" 5 快速排序 6 2-路归并排序"<<endl; cout<<"====================================================================="<<endl; cin>>ch; //随机产生排序用的数据 int s[N]; for(int i=1;i<=N-1;i++) {s[i]=rand()%100;} cout<<"\n随机产生用来排序的原始数据如下： "<<endl<<endl; for(int i=1;i<=N-1;i++) {cout<<s[i]<<" ";} cout<<endl<<endl; switch(ch) { case 0:c=0;break; case 1:zjcr(s);break; case 2:jdxz(s);break; case 3:ddpx(s,N-1);break; case 4:mppx(s);break; case 5:kspx(s,1,N-1);break; case 6:gbpx(s,sm,N-1);break; default:cout<<"您的输入不正确，选择的范围是〈0，1，2，3，4，5，6〉，请重新输入： "<<endl; } } system("PAUSE"); return EXIT_SUCCESS; } //=====================================函 数 的 定 义============================================ //直接插入排序算法 int zjcrs(int s[]) //升序 { sum=0; int i,j; for(i=2;i<=N-1;i++) { if(s[i]<s[i-1]) {s[0]=s[i]; //s[0]作为哨兵 for(j=i-1;s[0]<s[j];j--) { s[j+1]=s[j]; sjs[1]++; } s[j+1]=s[0]; } sum++; cout<<"\n"<<"第"<<sum<<"趟排序结果: "; for(int i=1;i<=N-1;i++) {cout<<s[i]<<" ";} } kjs[1]=1; //该算法中只有一个辅助存储空间即s[0] cout<<"\n\n该方法的时间复杂度为： "<<"O("<<sjs[1]<<"); 空间复杂度为： "<<"O("<<kjs[1]<<")"<<endl; } int zjcrj(int s[]) //降序 { sum=0; int i,j; for(i=2;i<=N-1;i++) { if(s[i]>s[i-1]) {s[0]=s[i]; //s[0]作为哨兵 for(j=i-1;s[0]>s[j];j--) { s[j+1]=s[j]; sjj[1]++; } s[j+1]=s[0]; } sum++; cout<<"\n"<<"第"<<sum<<"趟排序结果: "; for(int i=1;i<=N-1;i++) {cout<<s[i]<<" ";} } kjj[1]=1; //该算法中只有一个辅助存储空间即s[0] cout<<"\n\n该方法的时间复杂度为： "<<"O("<<sjj[1]<<"); 空间复杂度为： "<<"O("<<kjj[1]<<")"<<endl; } int zjcr(int s[]) //直接插入排序的主要函数 { cout<<"\n您选择的是: [直接插入排序方法] \n"<<endl; cout<<"请选择您要用的排序顺序： \n"<<endl; cout<<" 0 非降序\n"<<endl; cout<<" 1 非升序"<<endl; int chh; cin>>chh; switch(chh) { case 0: cout<<"\n\n您选择的是: [直接插入排序法的升序排序] "<<endl; cout<<"\n数据的初始顺序如下: "<<endl; for(int i=1;i<=N-1;i++) {cout<<s[i]<<" ";} cout<<endl; sjs[1]=kjs[1]=0; //时空计数清零 zjcrs(s); cout<<"\n排序后数据的顺序如下： "<<endl; for(int i=1;i<=N-1;i++) {cout<<s[i]<<" ";} cout<<endl; break; case 1: cout<<"\n\n您选择的是: [直接插入排序法的降序排序] "<<endl; cout<<"\n数据的初始顺序如下： "<<endl; for(int i=1;i<=N-1;i++) {cout<<s[i]<<" ";} cout<<endl; sjj[1]=kjj[1]=0; zjcrj(s); cout<<"\n排序后数据的顺序如下： "<<endl; for(int i=1;i<=N-1;i++) {cout<<s[i]<<" ";} cout<<endl; break; default: cout<<"\n\n您的输入不正确，请重新选择排序的顺序 〈0，1〉： "<<endl; break; } } //简单选择排序算法 int jdxzs(int s[]) //升序 { sum=0; int i,j,k; for(i=1;i<=N-1;i++) { k=i ; //记录关键字最小的记录位置 for(j=i+1;j<=N-1;j++) { if(s[j]<s[k]) k=j; //更新最小记录的位置 } if(k!=i)//与第i个记录进行交换 { s[0]=s[i]; s[i]=s[k]; s[k]=s[0]; sjs[2]++; } sum++; cout<<"\n"<<"第"<<sum<<"次排序结果: "; for(int i=1;i<=N-1;i++) {cout<<s[i]<<" ";} } kjs[2]=1; //只有一个辅助空间s[0] cout<<"\n\n该方法的时间复杂度为： "<<"O("<<sjs[2]<<"); 空间复杂度为： "<<"O("<<kjs[2]<<")"<<endl; } int jdxzj(int s[]) //降序 { sum=0; int i,j,k; for(i=1;i<=N-1;i++) { k=i ; //记录关键字最大的记录位置 for(j=i+1;j<=N-1;j++) { if(s[j]>s[k]) k=j; //更新最大记录的位置 } if(k!=i)//与第i个记录进行交换 { s[0]=s[i]; s[i]=s[k]; s[k]=s[0]; sjj[2]++; } sum++; cout<<"\n"<<"第"<<sum<<"次排序结果: "; for(int i=1;i<=N-1;i++) {cout<<s[i]<<" ";} } kjj[2]=1; //只有一个辅助空间s[0] cout<<"\n\n该方法的时间复杂度为： "<<"O("<<sjj[2]<<"); 空间复杂度为： "<<"O("<<kjj[2]<<")"<<endl; } int jdxz(int s[]) //简单选择排序的主要函数 { cout<<"\n您选择的是: [简单选择排序方法] \n"<<endl; cout<<"请选择您要用的排序顺序： \n"<<endl; cout<<" 0 非降序\n"<<endl; cout<<" 1 非升序"<<endl; int chh; cin>>chh; switch(chh) { case 0: cout<<"\n\n您选择的是: [简单选择排序法的升序排序] "<<endl; cout<<"\n数据的初始顺序如下: "<<endl; for(int i=1;i<=N-1;i++) {cout<<s[i]<<" ";} cout<<endl; sjs[2]=kjs[2]=0; jdxzs(s); cout<<"\n排序后数据的顺序如下： "<<endl; for(int i=1;i<=N-1;i++) {cout<<s[i]<<" ";} cout<<endl; break; case 1: cout<<"\n\n您选择的是: [简单选择排序法的降序排序] "<<endl; cout<<"\n数据的初始顺序如下： "<<endl; for(int i=1;i<=N-1;i++) {cout<<s[i]<<" ";} cout<<endl; sjj[2]=kjj[2]=0; jdxzj(s); cout<<"\n排序后数据的顺序如下： "<<endl; for(int i=1;i<=N-1;i++) {cout<<s[i]<<" ";} cout<<endl; break; default: cout<<"\n\n您的输入不正确，请重新选择排序的顺序 〈0，1〉： "<<endl; break; } } //堆排序算法 int jdd(int s[],int i,int n) //调整大根堆 { s[0]=s[i]; //倍份待筛结点元素值 int j=2*i; //s[j]为s[i]的左孩子 while(j<=n) //当 s[i]的左孩子不为空时 { if(j<n&&s[j]<s[j+1]) j++; //j为i 结点较大孩子的下标 if(s[0]>=s[j]) break; //找到位置,终止循环 sjs[3]++; s[i]=s[j]; i=j; j=2*i; } s[i]=s[0]; } int ddpxs(int s[],int n) //堆升序 { sum=0;