试验十二排序技术试验报告汇总

1、特殊线性表实验十二 排序技术实验一、 实验目的 掌握各种排序算法的基本思想； 掌握各种排序算法的实现方法； 掌握各种排序算法的时间性能及其花费时间的计算。 掌握各种排序算法所适应的不同场合。二、 实验内容1、随机函数产生 10000 个随机数，用直接插入、希尔、冒泡、直接选择等排序方法排序，并统计每 一种排序所花费的时间。2、随机函数产生 30000 个随机数，用快速、堆、归并等排序方法排序，并统计每一种排序所花费的时 间。、设计与编码#include #include #include using namespace std; void ShuChu(int r,int n) cout 输出

2、： ;for(int i=0;in;i+) coutrit;coutendl;coutendl;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(i

3、nt 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=r

4、i;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

5、 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

6、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 MergeSor

7、t(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()coutcout 排序技术实验 endl;endl;cout1. 直接插入排序 endl;cout2. 希尔排序 endl;cout3. 冒泡排序 endl; cout4. 直接选择排序 endl;cout5. 快速排序 endl;cout6. 堆排序 endl;cout7. 归并排序 endl; cout8. 退出 endl;int main()clock_t start,end;men

8、u();int flag=1; while(flag)coutint i;endl;couti;switch(i)case 1:int srand(30001);int a30001;int n;coutn;a0=0;秒endl;秒endl;秒endl;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 b

9、reak;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 break; case 3:int srand(30001);int a30001;int n;coutn;a0=0;for(int i=1;in;

10、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特殊线性表break; case 4: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();SelectS

11、ort(a,n);end=clock();ShuChu(a,n);double count=(double)(end-start)/1000;cout 排序所用时间为 :count 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)/1

12、000;cout 排序所用时间为 :count 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;:endl;秒endl;秒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(30

13、001);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 个随机数进行快速、堆、归