24小时热门版块排行榜

返回列表

进击的城管

银虫 (初入文坛)

应助: 0 (幼儿园)
金币: 372.5
帖子: 20
在线: 7.6小时
虫号: 2540181
注册: 2013-07-10
专业: 通信理论与系统

[求助] 分配排序问题

要求：随机生成若干个随机数进行排序（如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;
}