实验十二排序技术实验报告.doc

实验十二 排序技术实验一、 实验目的1 掌握各种排序算法的基本思想； 掌握各种排序算法的实现方法； 掌握各种排序算法的时间性能及其花费时间的计算。 掌握各种排序算法所适应的不同场合。二、 实验内容 1、随机函数产生10000个随机数，用直接插入、希尔、冒泡、直接选择等排序方法排序，并统计每一种排序所花费的时间。2、随机函数产生30000个随机数，用快速、堆、归并等排序方法排序，并统计每一种排序所花费的时间。三、 设计与编码 #include #include #include using namespace std;void ShuChu(int r,int n)cout输出：;for(int i=0;in;i+)coutrit;coutendl;cout*endl;void InsertSort(int r,int n) /插入排序int a=r0;for(int i=2;in;i+)r0=ri;for(int j=i-1;r0=1;d=d/2)for(int i=d+1;i0 & r0rj;j=j-d)rj+d=rj; rj+d=r0;r0=a;void BubbleSort(int r,int n) /冒泡排序int exchange=n-1;while(exchange!=0)int bound=exchange;exchange=0;for(int j=1;jrj+1)int s=rj+1;rj+1=rj;rj=s;exchange=j;void SelectSort(int r,int n) /选择排序for(int i=0;in-1;i+)int index=i;for(int j=i+1;j=n-1;j+)if(rjrindex)index=j;if(index!=i)int a=rindex;rindex=ri;ri=a;ShuChu(r,n);int Partition(int r,int first,int end) /快速排序一次划分算法int i=first;int j=end;r0=ri;int p=ri;while(ij)while(ij&ri=rj)j-;if(ij)int a=rj;rj=ri;ri=a;i+;while(ij&ri=rj)i+;if(ij)int b=rj;rj=ri;ri=b;j-;return i;void QuickSort(int r,int first,int end) /快速排序算法int a=r0;if(firstend)int pivot=Partition(r,first,end);QuickSort(r,first,pivot-1);QuickSort(r,pivot+1,end);r0=a;void Sift(int r,int k,int m) /筛选法调整堆的算法int i=k;int j=2*i;while(j=m)if(jm&rj=rj)break;elseint a=rj;rj=ri;ri=a;i=j;j=2*i;void HeapSort(int r,int n) /堆排序算法for(int i=n/2;i=1;i-)Sift(r,i,n-1);for(i=2;in-1;i+)int a=rn-i+1;rn-i+1=r1;r1=a;Sift(r,1,i-1);void Merge(int r,int r1,int s,int m,int t) /一次归并算法int i=s;int j=m+1;int k=s;while(i=m&j=t)if(ri=rj)r1k+=ri+;else r1k+=rj+;if(i=m)while(i=m)r1k+=ri+;else while(j=t)r1k+=rj+;void MergePass(int r,int r1,int n,int h)int i=1;int a=n-2*h+1;while (i=a)Merge(r,r1,i,i+h-1,i+2*h-1);i+=2*h;if(in-h+1)Merge(r,r1,i,i+h-1,n);else for(int k=i;k=n;k+)r1k=rk;void MergeSort(int r,int r1,int n) /归并排序非递归算法int h=1;while (hn)MergePass(r,r1,n,h);h=2*h;MergePass(r1,r,n,h);h=2*h;void menu()cout排序技术实验endl; cout*endl;cout1.直接插入排序endl;cout2.希尔排序endl; cout3.冒泡排序endl;cout4.直接选择排序endl;cout5.快速排序endl;cout6.堆排序endl;cout7.归并排序endl; cout8.退出endl;int main() clock_t start,end; menu(); int flag=1; while(flag) int i; cout*endl; couti; switch(i) case 1:int srand(30001);int a30001;int n;coutn;a0=0;for(int i=1;in;i+)ai=rand();ShuChu(a,n);cout直接插入排序结果：endl;start=clock();InsertSort(a,n);end=clock(); ShuChu(a,n);double count=(double)(end-start)/1000;cout排序所用时间为:count秒endl;break;case 2:int srand(30001);int a30001;int n;coutn;a0=0;for(int i=1;in;i+)ai=rand();ShuChu(a,n);cout希尔排序结果：endl;start=clock();ShellSort(a,n);end=clock();ShuChu(a,n);double count=(double)(end-start)/1000;cout排序所用时间为:count秒endl;break; case 3: int srand(30001);int a30001;int n;coutn;a0=0;for(int i=1;in;i+)ai=rand();ShuChu(a,n); cout冒泡排序结果：endl; start=clock(); BubbleSort(a,n); end=clock(); ShuChu(a,n);double count=(double)(end-start)/1000;cout排序所用时间为:count秒endl; break; case 4:int srand(30001);int a30001;int n;cout请输入随机产生的随机数的个数:n;a0=0;for(int i=1;in;i+)ai=rand();ShuChu(a,n);cout直接选择排序结果：endl;start=clock();SelectSort(a,n);end=clock();ShuChu(a,n);double count=(double)(end-start)/1000;cout排序所用时间为:count秒endl;break; case 5:int srand(30001);int a30001;int n;coutn;a0=0;for(int i=1;in;i+)ai=rand();ShuChu(a,n);cout快速排序结果：endl;start=clock();QuickSort(a,1,n-1);end=clock();ShuChu(a,n);double count=(double)(end-start)/1000;cout排序所用时间为:count秒endl;break;case 6:int srand(30001);int a30001;int n;coutn;a0=0;for(int i=1;in;i+)ai=rand();ShuChu(a,n);cout堆排序结果：endl;start=clock();HeapSort(a,n);end=clock();ShuChu(a,n);double count=(double)(end-start)/1000;cout排序所用时间为:count秒endl;break; case 7:int srand(30001);int a30001;int n;int a130001;coutn;a0=0;for(int i=1;in;i+)ai=rand();ShuChu(a,n);cout归并排序结果：endl;start=clock();MergeSort(a,a1,n-1);end=clock();ShuChu(a,n);double count=(double)(end-start)/1000;cout排序所用时间为:count秒endl;break; case 8:flag=0;break; default:cout错误!endl;break;return 0; 四、 运行与调试a) 在调试程序的过程中遇到什么问题，是如何解决的？答：数据的下标经常出错，数组的第一个数应是a0.b) 设计了哪些设计数据？测试结果是什么？答：程序设计了对随机函数产生10000个随机数进行直接插入、希尔、冒泡、直接选择等排序方法排序，并统计每一种排序所花费的时间；对随机函数产生30000个随机数进行快速、堆、归并等排序方法排序，并统计每一种排序所花费的时间。结果实现各种排序方法的排序，并统计了排序所需时间。c) 程序运行的结果如何？因排序结果太长，故只设计显示排序时间五、 实验小结本实验通过不同的算法实现相同的排序，不同的排序算法时间性能亦不同，只要了解算法间的原理，程序就比较简单了，稍微要注意的是数组的下标问题，总的来说，本实验让我对个算法的理解更加深刻，也对数据结构的学习更深入，但还不够熟悉，需多多练习。