三个数据结构小程序

#include<iostream.h> #include <stdio.h> #include<windows.h> #define MAX 1000000 class paixu { public: void XuanzePaixu();//简单选择排序 void MaopaoPaixu();//冒泡排序 void CharuPaixu();//直接插入排序 int Huafen(int l,int h); void KPaixu(int l,int h); void KuaisuPaixu();//快速排序 void dui(int s,int m); void DuiPaixu();//堆排序 void XierPaixu();//希尔排序 void suijishu(int y);//产生随机数 }; int RA1[MAX],RA2[MAX],jj,a,b,c; //============================================================================== //简单选择排序 void paixu::XuanzePaixu() { int v,n=0; for(int i=1;i <= jj;i++) {RA2[i] = RA1[i];} for( i = 1 ; i < jj ; ++i) { int j = i; for(int k = i+1 ; k <= jj ; k++) if(RA2[k] < RA2[j]) j = k; if(i != j) { v = RA2[j]; RA2[j] = RA2[i]; RA2[i] = v; n++; } } cout<<"排序后的元素为:"<<endl; for( i=1;i <= jj;i++) cout<<RA2[i]<<" "; cout<<endl; cout<<"一共移动次数为："<<n; } //============================================================================== //起泡排序 void paixu::MaopaoPaixu() { int k=jj; int w,n=0; for(int i=1;i <= jj;i++) {RA2[i] = RA1[i];} while(k>1) { int Index=1; for(int j=1;j<k;j++) { if(RA2[j+1]<RA2[j]) { w=RA2[j]; RA2[j]=RA2[j+1]; RA2[j+1]=w; //互换记录 Index=j; n++; } }k=Index; } cout<<"排序后的元素为:"<<endl; for( i=1;i <= jj;i++) cout<<RA2[i]<<" "; cout<<endl; cout<<"一共移动次数为："<<n; } //============================================================================== //直接插入排序 void paixu::CharuPaixu() { int n=0; for(int i=1;i <= jj;i++) {RA2[i] = RA1[i];} for(i=2;i<=jj;++i) if(RA2[i]<RA2[i-1]) { RA2[0]=RA2[i]; //复制为哨兵 for(int j=i-1;RA2[0]<RA2[j];--j) RA2[j+1]=RA2[j]; //记录后移 RA2[j+1]=RA2[0]; //插入到正确位置 n++; } cout<<"排序后的元素为:"<<endl; for( i=1;i <= jj;i++) cout<<RA2[i]<<" "; cout<<endl; cout<<"一共移动次数为："<<n; } //============================================================================== //快速排序 int paixu::Huafen(int l,int h) //划分 { RA2[0] = RA2[l]; int pt = RA2[l]; //枢轴记录关键字 while(l < h) //从表的两端交替地向中间扫描 { while(l < h && RA2[h] >= pt) -- h; RA2[l] = RA2[h]; //将比枢轴记录小的记录移到底端 while (l < h && RA2[l] <= pt) ++ l; RA2[h] = RA2[l]; //将比枢轴记录大的记录移到高端 }// while a++; RA2[l] = RA2[0]; //枢轴记录移到正确位置 a++; return l; //返回枢轴的位置 } //Huafen void paixu::KPaixu(int l,int h) { if(l < h) //长度大于1 { int pivotloc = Huafen(l,h); KPaixu(l,pivotloc-1); //对底端子序列递归排序 KPaixu(pivotloc+1,h); //对高断子序列递归排序 } //if }// KuaisuPaixu void paixu::KuaisuPaixu() //快速排序 { for(int i=1;i <= jj;i++) {RA2[i] = RA1[i];} KPaixu(1,jj); cout<<"排序后的元素为:"<<endl; for(i=1;i <= jj;i++) cout<<RA2[i]<<" "; cout<<endl; cout<<"一共移动次数为："<<a; } //KuaisuPaixu //============================================================================== //堆排序 void paixu::dui(int s,int m) { for(int i=1;i <= jj;i++) {RA2[i] = RA1[i];} int rc = RA2[s]; //暂存根结点的记录 for(int j = 2*s;j<=m;j*=2) //沿较大的孩子结点向下筛选 { if(j<m&&RA2[j]<RA2[j+1])++j; if(RA2[s]>=RA2[j])break; //不需要调整 RA2[s] = RA2[j]; //把大于关键字记录往上调 b++; s = j; } RA2[s] = rc;b++; //回移筛选小的记录 } void paixu::DuiPaixu() { int w; for(int i = jj/2;i>0;--i) dui(i,jj); w = RA2[1]; RA2[1] = RA2[jj]; RA2[jj] = w; //交换"堆顶"和"堆底"的记录 for(i = jj-1;i>1;--i) { dui(1,i); w = RA2[1];RA2[1] = RA2[i];RA2[i] = w; //将堆顶记录和当前的"堆底"记录相互交换使已有序的记录堆移到底部 } cout<<"排序后的元素为:"<<endl; for( i=1;i <= jj;i++) cout<<RA2[i]<<" "; cout<<endl; cout<<"一共移动次数为："<<b; } //============================================================================== //希尔排序 void paixu::XierPaixu() { for(int i=1;i <= jj;i++) {RA2[i] = RA1[i];} int dt=5; do { dt = dt/3+1; //1 前后记录位置的增量是dt，而不是1 for(int i=dt+1;i<=jj;++i) if(RA2[i]<RA2[i-dt]){ //需将RA2.[i]插入有序增量子表 RA2[0]=RA2[i]; //暂存在RA2.[0] c++; int j=i-dt; do { RA2[j+dt] = RA2[j];c++; j = j - dt; }while(j > 0&&RA2[0] < RA2[j]); //记录后移，查找插入位置 RA2[j+dt]=RA2[0];c++; //插入 } }while(dt > 1); cout<<"排序后的元素为:"<<endl; for( i=1;i <= jj;i++) cout<<RA2[i]<<" "; cout<<endl; cout<<"一共移动次数为："<<c; }//XierPaixu//一趟增量为dt[k]的插入排序 //============================================================================== //随机生成函数 void paixu::suijishu(int y) { int i; for(i=1;i<=y;i++) RA1[i]=(int)rand(); cout<<"随机产生的所有元素为:"<<endl; for(i=1;i<=y;i++) cout<<RA1[i]<<" "; cout<<endl; } void main() { paixu m; cc: system("cls"); cout<<" ◆◆◆◆内部排序算法比较程序◆◆◆◆"<<endl<<endl; cout<<" ***********************************\t"<<endl; cout<<" *\t 1、内部排序比较 *\t"<<endl; cout<<" *\t 2、退出系统 *\t"<<endl; cout<<" ***********************************\t"<<endl; char b; dt: cin>>b; if(b == '1') { system("cls"); cout<<"------------------------------------------------"<<endl; cout<<" \t ⊙返回上页 \t"<<endl; cout<<" \t ①简单选择排序 \t"<<endl; cout<<" \t ②起泡排序 \t"<<endl; cout<<" \t ③直接插入排序 \t"<<endl; cout<<" \t ④快速排序 \t"<<endl; cout<<" \t ⑤堆排序 \t"<<endl; cout<<" \t ⑥希尔排序 \t"<<endl; cout<<"请输入要处理的1组随机数的总个数: "; int q; cin>>q; system("cls"); if(q==0) goto cc; jj=q; m.suijishu(q); cout<<endl; while(1) { cout<<"------------------------------------------------"<<endl; cout<<" \t ⊙返回上页 \t"<<endl; cout<<" \t ①简单选择排序 \t"<<endl; cout<<" \t ②起泡排序 \t"<<endl; cout<<" \t ③直接插入排序 \t"<<endl; cout<<" \t ④快速排序 \t"<<endl; cout<<" \t ⑤堆排序 \t"<<endl; cout<<" \t ⑥希尔排序 \t"<<endl; char k; cout<<"请选择你要排序的方法："; cin>>k; switch(k) { case '0': goto cc; case '1': m.XuanzePaixu(); cout<<endl; cout<<"按任意键返回！"<<endl; getchar(); system("cls"); break; case '2': m.MaopaoPaixu(); cout<<endl; cout<<"按任意键返回！"<<endl; getchar(); system("cls"); break; case '3': m.CharuPaixu(); cout<<endl; cout<<"按任意键返回！"<<endl; getchar(); system("cls"); break; case '4': m.KuaisuPaixu(); cout<<endl; cout<<"按任意键返回！"<<endl; getchar(); system("cls"); break; case '5': m.DuiPaixu(); cout<<endl; cout<<"按任意键返回！"<<endl; getchar(); system("cls"); break; case '6': m.XierPaixu(); cout<<endl; cout<<"按任意键返回！"<<endl; getchar(); system("cls"); break; default: cout<<"输入信息错误！请重新输入！"<<endl; break; } } } if(b == '2') exit(0); else cout<<"输入信息错误！请重新输入:"<<endl; goto dt; }