| 查看: 462 | 回复: 0 | ||
[求助]
分配排序问题
|
|
要求：随机生成若干个随机数进行排序（如n＝10^4，2＊10^4，10^5，…等），记录每个排序的时间耗费（绝对时间？逻辑时间（关键字比较次数，移动次数）？）。 （2）分别给出正序和反序的初始序列进行排序（如n＝10^4），检验算法对初始序列的敏感程度。 另给一个新的自己写的也行  我弄到这一步出现错误 不知道该怎么把随机生成的数组的每一位分配给分配排序的函数，然后又再正常输出 分配 排序的关键字是多维的 假如一个数是654321 则要存成 【6 5 4 3 2 1】来进行分配排序 #define CPP C++ #define MPP M++ #define MP2 M+=2 #define MP3 M+=3 #include <fstream.h> #include <iomanip.h> #include <stdlib.h> #include <time.h> #include <math.h> const int d=3; const int maxsize=100000; //数据表容量 typedef int datatype; typedef struct { datatype key[d]; //关键字域 int next; } rectype; //记录类型 typedef rectype list[maxsize+2]; //数据表类型，0号单元不用 __int64 C,M; //比较和移动次数 void check(list R,int n) { //检验排序结果 int i; for(i=2;i<=n;i++) if(R.key<R[i-1].key) {cout<<"Error!\n";return;} cout<<"Correct! "; } void disp(list R,int n) { //显示排序后的结果 int i; for(i=1;i<=n;i++) { cout<<setw(4)<<R.key; // if(i%20==0) cout<<endl; } cout<<endl; } int RadixSort(list R,int n){ const int r=10; typedef struct{ int f,e; }queue; int i,j,k,t,p; queue B[r]; for(i=0;i<n-1;i++) R.next=i+1; R[n-1].next=-1; p=0; for(j=d-1;j>=0;j--){ for(i=0;i<r;i++) B.f=B.e=-1; while(p!=-1){ k=R[p].key[j]; if(B[k].f==-1)B[k].f=p; else R[B[k].e].next=p; B[k].e=p; p=R[p].next; } i=0; while(B.f==-1)i++; p=B.f; t=B.e; while(i<r-1){ i++; if(B.f!=-1){ R[t].next=B.f; t=B.e; } } R[t].next=-1; } return p; } int random1(int num) {return rand();} //0~RAND_MAX=32767 int random3(int num) {//素数模乘同余法,0~M int A=16807; // 16807,39722040,764261123,630360016 48271? int M=2147483647; //有符号4字节最大素数,2^31-1 int Q=M/A; int R=M%A; static int x=1,n=0,g=0; //seed(set to 1) static double r,r1=0,r2=0; int x1; x1=A*(x%Q)-R*(x/Q); if(x1>=0) x=x1; else x=x1+M; return x; } void main() { rectype *R,*R1,*S; //R1用于归并排序的辅助存储，S用于保存初始排序数据 R=new list;if(R==NULL) {cout<<"数组太大!\n";exit(-1);} R1=new list;if(R1==NULL) {cout<<"数组太大!\n";exit(-1);} S=new list;if(S==NULL) {cout<<"数组太大!\n";exit(-1);} int i,n=maxsize; int choice; clock_t t1,t2; float s,t; //srand( (unsigned)time( NULL ) ); for(i=1;i<=10;i++){ for(j=1;j<d;j++) S.key[j]=random3(10); //生成0-n之间的随机数 } do { C=M=0; for(i=1;i<=n;i++) R.key=S.key; //取出初始数据用于排序 cout<<"选择排序方法(0: 退出): \n\ 11：直接插入(带监视哨) 12：直接插入(无监视哨) \n\ 21：希尔排序(无监视哨) \n\ 41：冒泡(上升) 42：冒泡(下沉） \n\ 51：快速(递归) \n\ 61：直接选择排序 \n\ 71：堆排序(非递归) \n\ 91：fenpei \n\ 81：二路归并(非递归) \n"; cin>>choice; switch(choice) { case 91: t1=clock(); RadixSort(R,n); t2=clock(); break; default:; } check(R,n); // disp(R,n); cout<<" C="<<C/1e6<<" M="<<M/1e6<<" C+M="<<(C+M)/1e6; cout<<" 时间："<<float(t2-t1)/CLK_TCK<<endl; } while(choice!=0); delete R; delete S; // delete R1; } |
回复此楼» 猜你喜欢
290调剂生物0860
已经有26人回复
-
2本，初试303，0860求调剂
已经有7人回复
-
材料工程281还有调剂机会吗
已经有28人回复
-
一志愿浙大生物325分求调剂
已经有5人回复
-
344 材料专业 求调剂211 无地域要求
已经有6人回复
-
一志愿085802 323分求调剂
已经有10人回复
-
一志愿哈工大 085600 277 12材科基求调剂
已经有26人回复
-
339求调剂
已经有8人回复
-
材料考研调剂
已经有28人回复
-
调剂求收留
已经有27人回复
找到一些相关的精华帖子，希望有用哦~
TLC淋洗剂改变物质顺序
已经有9人回复
- 干物质分配计算问题
已经有4人回复
- 求助线代问题～
已经有8人回复
- 农药残留分析前处理中关于柱层析净化的问题及怎么解决液液分配的乳化问题
已经有12人回复
- 英语的正确答题顺序?
已经有25人回复
- Chemistry of Materials分配编辑的问题
已经有10人回复
- 论文作者排序问题
已经有13人回复
- 求助endnote参考文献排序问题
已经有22人回复
- 发表SCI，作者排序问题
已经有53人回复
- 关于参考文献中第一作者和通讯作者的排序问题
已经有3人回复
- 关于工作基础的作者排序问题
已经有28人回复
- 湖北省2011年度国家社会科学基金项目名额分配
已经有3人回复
- 【求助】博士的公开招考（申请入学）问题
已经有6人回复
- 【求助】如何处理考研复习与上课的时间分配问题？
已经有13人回复
- Applied surface science分配主编的问题
已经有16人回复
- endnote排序混乱问题
已经有9人回复
点击这里搜索更多相关资源科研从小木虫开始，人人为我，我为人人
