数据结构排序算法综合实验(3)

if(!flag) break; //本趟未交换过记录，排序结束 } }

//快速排序，递归算法

int Partition(list R,int p,int q) {//对R[p]到R[q]划分，返回基准位置 int i,j;rectype x; //辅助量(可用R[0]代替)

i=p;j=q;MPP,x=R[p]; //x存基准(无序区第一个记录) do {

while((CPP,R[j].key>=x.key) && i

while((CPP,R[i].key<=x.key) && i

MPP,R[i]=x; //基准移到最终位置 return i; //最后i=j }

void QuickSort1(list R,int s,int t) { int i;

if(s>=t) return; //只有一个记录或无记录时无需排序 i=Partition(R,s,t); //对R[s]到R[t]做划分 QuickSort1(R,s,i-1); //递归处理左区间 QuickSort1(R,i+1,t); //递归处理右区间 }

//归并排序

void Merge(list R,list R1,int low,int mid,int high) {

//合并R的两个子表：R[low]~R[mid]、R[mid+1]~R[high]，结果在R1中 int i,j,k; i=low; j=mid+1; k=low;

while(i<=mid && j<=high)

if(CPP,R[i].key<=R[j].key) MPP,R1[k++]=R[i++]; //取小者复制 else MPP,R1[k++]=R[j++];

while(i<=mid) MPP,R1[k++]=R[i++]; //复制左子表的剩余记录 while(j<=high) MPP,R1[k++]=R[j++]; //复制右子表的剩余记录 }

//一趟归并

void MergePass(list R,list R1,int n,int len) {//对R做一趟归并，结果在R1中

int i,j;

i=1; //i指向第一对子表的起始点 while(i+2*len-1<=n) { //归并长度为len的两个子表 Merge(R,R1,i,i+len-1,i+2*len-1);

i=i+2*len; //i指向下一对子表起始点 }

if(i+len-1

else //子表个数为奇数,剩一段 for(j=i;j<=n;j++) //将最后一个子表复制到R1中 MPP,R1[j]=R[j]; }

//二路归并排序

void MergeSort(list R,list R1,int n) {//对R二路归并排序，结果在R中(非递归算法) int len; len=1;

while(len

MergePass(R,R1,n,len);len=len*2; //一趟归并，结果在R1中 MergePass(R1,R,n,len);len=len*2; //再次归并，结果在R中 } }

//堆排序

void Sift(list R,int p,int q) //筛选算法 { int i,j; R[0]=R[p]; i=p; j=2*i; while(j<=q) { if(j=R[j].key) break; R[i]=R[j]; i=j; j=2*i; } R[i]=R[0]; }

void HeapSort(list R,int n) //堆排序主程序 { int i; for(i=n/2;i>=1;i--) Sift(R,i,n); for(i=n;i>=2;i--) { MP3,R[0]=R[1]; R[1]=R[i]; R[i]=R[0]; Sift(R,1,i-1); } }

//选择排序

void SelectSort(list R,int n) { int i,j,k; for(i=1;i<=n-1;i++) { k=i; for(j=i+1;j<=n;j++) if(R[j].key

int random1(int num) {return rand();} //0~RAND_MAX=32767 int random3(int num) {//素数模乘同余法,0~M

int A=16807; // 16807,39722040,764261123,630360016 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);

48271? if(x1>=0) x=x1; else x=x1+M; return x; }

int main() {

rectype *R,*R1,*S; //R1用于归并排序的辅助存储，S用于保存初始排序数据 R=new list;if(R==NULL) {cout<<\数组太大!\\n\ R1=new list;if(R1==NULL) {cout<<\数组太大!\\n\ S=new list;if(S==NULL) {cout<<\数组太大!\\n\ int i,n=maxsize; int choice; clock_t t1,t2; float s,t;

// srand( (unsigned)time( NULL ) ); for(i=1;i<=n;i++)

S[i].key=random3(n); //生成0-n之间的随机数

do { C=M=0;

for(i=1;i<=n;i++)

R[i].key=S[i].key; //取出初始数据用于排序

cout<<\选择排序方法(0: 退出): 11：直接插入(带监视哨) 12：直接插入(无监视哨) 21：冒泡(上升) 22：冒泡(下沉） 31：快速(递归) 41：二路归并(非递归) 51: 堆排序 61: 选择排序 71: 希尔(希尔)排序 cin>>choice; switch(choice) { case 11:

t1=clock();

InsertSort1(R,n); t2=clock(); break; case 12:

t1=clock();

InsertSort2(R,n); t2=clock(); break; case 21:

\\n\\ \\n\\ \\n\\ \\n\\ \\n\\ \\n\\ \\n\\ \\n\ t1=clock();

BubbleSort1(R,n); t2=clock(); break; case 22:

t1=clock();

BubbleSort2(R,n); t2=clock(); break; case 31:

t1=clock();

QuickSort1(R,1,n); t2=clock(); break; case 41:

t1=clock();

MergeSort(R,R1,n); t2=clock(); break; case 51:

t1=clock(); HeapSort(R,n); t2=clock(); break; case 61:

t1=clock();

SelectSort(R,n); t2=clock(); break; case 71:

t1=clock(); ShellSort(R,n); t2=clock(); break; default:; }

check(R,n); // disp(R,n);

cout<<\ cout<<\时间：\ } while(choice!=0); delete R;delete S; // delete R1; }