排序C语言实验报告.docx

排序数学系 李一鹏 PB12001076 第五组1. 试验题目：排序2. 实验目的：掌握各种内部排序思想。3. 实验内容：每一个在令狐冲身边出现的女性都会在令狐冲心中占有一定“地位”，例如小师妹的地位值是23456，任盈盈的地位值是30000，东方不败的地位值是32767，蓝凤凰的是1234，市集卖菜大妈41，市集路过小姑娘2000现在令狐冲希望把她们按顺序一个个攻略，请编一个程序，把她们按地位排序。4. 算法思想：本程序有冒泡，快排，插入，希尔，选择，堆排，归并七个排序。下面介绍堆排和归并。堆排：建堆时先把初态视为只有一个结点的大根堆，每加入一个数据与父结点比较，若父结点小于当前结点则上移，重复操作直至父结点比当前结点大。排序时交换堆尾与根，堆尾指标前移，根与子结点比较，与大者交换，重复操作直至子结点均小于当前结点。归并：把序列半分，先把两个子序列排序，然后用两个指标记录子序列当前最小值，把右指标插入两指标之间的序列，左指标记录为当前插入点的下一个位置，右指标右移。5. 程序清单：#include#include#includetypedef struct datatypeint node,data;dtype;dtype a1000;int n,sum1,sum2;/sum1记录比较次数，sum2移动次数void readln()/用文件读入待排序数据int i;FILE *f1;f1=fopen(a300.txt,r);fscanf(f1,%d,&n);for(i=1;i=n;i+)ai.node=i;fscanf(f1,%d,&ai.data);fclose(f1);void bubblesort()/冒泡排序int i,j;dtype t;for(i=n-1;i;i-)for(j=i;jaj+1.data)t=aj;aj=aj+1;aj+1=t;sum2+;void qsort(int l,int r)/快速排序int i,j,m;dtype t;i=l;j=r;m=al.data;sum2+;while(i=j)while(ai.datam)j-,sum1+;if(il)qsort(l,j);if(ir)qsort(i,r);void insertsort()/插入排序int i,j,m;for(i=2;im)aj+1=aj;j-;sum1+;sum2+;aj+1=a0;sum2+;void shellsort(int d)/隔了d个数的插入排序int i,j,m,k;for(i=1;i=d;i+)for(j=i+d;j0&ak.datam)ak+d=ak;k-=d;sum2+;sum1+;ak+d=a0;sum2+;void shells()/希尔排序int i,m,d100;printf(Input the sum of your shellarray:n);scanf(%d,&m);printf(Input your shellarray:n);for(i=1;i=m;i+)scanf(%d,&di);while(getchar()!=10);for(i=m;i;i-)shellsort(di);void selectsort()/选择排序int i,j,k,m;dtype t;for(i=1;in;i+)m=ai.data;k=i;sum2+;for(j=i+1;j=n;j+)sum1+;if(aj.datam)m=aj.data;k=j;sum2+;t=ak;ak=ai;ai=t;sum2+;void create(int i)/创建堆int m;a0=ai;m=a0.data;sum2+;while(ai/2.datam)ai=ai/2;i/=2;/a0起了哨兵作用保证i值不为0sum1+;sum2+;ai=a0;sum2+;void treesort(int i)/排序的一步并维护堆int j,m;a0=ai;m=a0.data;ai=a1;j=1;i-;sum2+;while(2*jm)if(a2*j+1.dataa2*j.data)aj=a2*j+1;j=2*j+1;elseaj=a2*j;j=2*j;else if(a2*j+1.datam)aj=a2*j+1;j=2*j+1;else break;if(2*j=i)if(a2*j.datam)aj=a2*j;j=2*j;sum2+;aj=a0;sum2+;sum1+;void pilesort()/堆排序int i;for(i=2;i1;i-) treesort(i);void msort(int l,int r)/归并排序int i,m,mid;mid=(l+r+1)/2;if(mid-1l)msort(l,mid-1);if(midr)msort(mid,r);while(lmid)m=amid.data;a0=amid;while(al.datal;i-)ai=ai-1;/移动(跟插入排序一样)al=a0;l+;mid+;if(midr)break;sum1+;sum2+;main()int c,num,i;while(1)sum1=0;sum2=0;readln();printf(=main=);printf(Press 0 to down sort and else to up sort:n);scanf(%d,&c);while(getchar()!=10);printf(Choose the number to the sortsn);printf(0.no sortn);printf(1.bubblesortn);printf(2.quicksortn);printf(3.insertsortn);printf(4.shellsortn);printf(5.selectsortn);printf(6.pilesortn);printf(7.mergesortn);printf(else to exitn);scanf(%d,&num);while(getchar()!=10);switch(num) case 0:break;case 1:bubblesort();break;case 2:qsort(1,n);break;case 3:insertsort();break;case 4:shells();break;case 5:selectsort();break;case 6:pilesort();break;case 7:msort(1,n);break;default:exit(1);printf(=data=);if(c) for(i=1;i=n;i+)printf(%dt,ai.data);else for(i=n;i;i-)printf(%dt,ai.data);putchar(10);printf(Here is the times of the compare:n%dn,sum1);printf(Here is the times of the movement:n%dn,sum2);while(getchar()!=10);system(CLS);6. 运行结果：7. 调试分析：调试时没有建工程，导致程序出现了未知问题，但在建工程后得到解决，但在不同的计算机中并不需要建工程也能正常运行。另：数据是编了一个生成随机数的小程序来生成的。8. 统计分析：排序名称Bubble冒泡Quick快排Insert插入Shell希尔Select选择Pile堆排Merge归并比较次数44850238921974219744485023952016移动次数21974962225722367618683295993数据一共n=300个。不难看出选择和冒泡的比较次数都几乎是1/2*n2，冒泡移动、插入和希尔的比较及移动次数都是1/4*n2