山东大学数据结构实验二.doc

数据结构实验报告实验二实验题目：排序算法学号：201300121111日期：14-11-19班级：13物联网姓名：卢日辉Email：2466379123实验目的：掌握各种排序方法实现思想任务要求：1.提供操作：选择排序，冒泡排序，插入排序，基数排序，快速排序，归并排序。2.显示中间过程软件环境：Win7 操作系统开发工具：Visual C+ 6.0实验步骤：代码如下：#include#includeint t=0,p=0,k=0;void xuanze(int a)/选择排序int i,j,local,temp,max,op;for(i=0;i8;i+)max=ai; local=i;for(j=i+1;jmax)max=aj;local=j;if(i!=local)temp=ai;ai=alocal;alocal=temp;coutstepi+1:endl;for(op=0;op9;op+)coutaop,;coutendl;void maopao(int a)/冒泡排序int n,j,temp,op;for(n=0;n8;n+)for(j=0;j8-n;j+)if(ajaj+1)temp=aj;aj=aj+1;aj+1=temp;coutstepn+1:endl;for(op=0;op9;op+)coutaop,;coutendl;void charu(int a)int b9=0;int i,j,op;for(i=0;i0;j-) if(bj-1=ai) bj=bj-1; else break; bj=ai;coutstepi+1:endl;for(op=0;op9;op+)coutbop,;coutendl;int maxbit(int data, int n) /辅助函数，求数据的最大位数 int d = 1; /保存最大的位数 int p = 10; for(int i = 0; i = p) p *= 10; +d; return d;void jishu(int data, int n) /基数排序n=9;int op; int d = maxbit(data, n); /数组中的元素的最大位数 int *tmp = (int *)malloc(n * sizeof(int); int *count = (int *)malloc(10 * sizeof(int); /计数器 int i, j, k; int radix = 1; for(i = 1; i = d; i+) /进行d次排序 for(j = 0; j 10; j+) countj = 0; /每次分配前清空计数器 for(j = 0; j n; j+) k = (dataj / radix) % 10; /计算每次循环某一位的数字 countk+; /统计每个桶中的记录数 for(j = 1; j = 0; j-) /将所有桶中记录依次收集到tmp中 k = (dataj / radix) % 10; tmpcountk - 1 = dataj; countk-; for(j = 0; j n; j+) /将临时数组的内容复制到data中 dataj = tmpj; coutstepkendl;k+;for(op=0;op9;op+)coutdataop,;coutendl;radix = radix * 10; free(tmp); free(count); void kuaisu(int a,int start,int end) /快速排序 int op; coutsteptendl;t+;for(op=0;op9;op+)coutaop,;coutendl;int i=start,j=end; int pivot = ai; while(ij) while(ij & pivot=aj) j-; ai = aj; while(ij & aistart) kuaisu(a,start,i); if(iend) kuaisu(a,i+1,end); void Merge(int a,int s,int mid, int e) /归并辅助函数，将两个排列好 /的数组排好整合到一个数组中int *b=new int9; for(int w=0;w9;w+) bw=aw; int i=s; int j=mid+1; int k=s; while(i=mid & j=e) if(bibj) ak+ = bi+; else ak+ = bj+; while(i=mid) ak+ = bi+; while(j=e) return; MergeSort(a,s,(s+e)/2); MergeSort(a,(s+e)/2+1,e); Merge(a,s,(s+e)/2,e);coutstepp+1endl;p+; for(op=0;op9;op+)coutaop,;coutendl; int main(void)int ch;kaishi:cout默认待排序数列：40，91，43，1，66，75，12，108，97endl;cout选择排序方法:endl;cout1,选择排序endl;cout2,冒泡排序endl;cout3,插入排序endl;cout4,基数排序endl;cout5,快速排序endl;cout6,归并排序ch;system(cls);int a19=40,91,43,1,66,75,12,108,97;int a29=40,91,43,1,66,75,12,108,97;int a39=40,91,43,1,66,75,12,108,97;int a49=40,91,43,1,66,75,12,108,97;int a59=40,91,43,1,66,75,12,108,97;int a69=40,91,43,1,66,75,12,108,97;switch(ch)case 1:xuanze(a1);break;case 2:maopao(a2);break;case 3:charu(a3);break;case 4:jishu(a4,9);break;case 5:kuaisu(a5,0,8);break;case 6:MergeSort(a6,0,8);break;system(pause);system(cls);goto kaishi;return 0;具体设计和实现：各函数如上注释。主