数据结构实验四题目一排序实验报告

数据结构实验报告 实验名称： 实验四排序学生姓名：XX班 级：班内序号：学 号：日 期：1实验要求实验目的： 通过选择实验内容中的两个题目之一，学习、实现、对比、各种排序的算法，掌握 各种排序算法的优劣，以及各种算法使用的情况。题目 1： 使用简单数组实现下面各种排序算法，并进行比较。排序算法如下：1、插入排序；2、希尔排序；3、冒泡排序；4、快速排序；5、简单选择排序；6、堆排序；7、归并排序；8、基数排序（选作）9、其他。具体要求如下：1、测试数据分成三类：正序、逆序、随机数据。2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关 键字交换记为 3 次移动）。3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙。4、对2和 3的结果进行分析，验证上述各种算法的时间复杂度。5、编写main （）函数测试各种排序算法的正确性。2. 程序分析2.1 存储结构存储结构：数组0A11A22A33A44A55A6NAn-12.2 关键算法分析一、关键算法：1、插入排序a、取排序的第二个数据与前一个比较b、若比前一个小，则赋值给哨兵c、从后向前比较，将其插入在比其小的元素后d、循环排序2、希尔排序a、将数组分成两份b、将第一份数组的元素与哨兵比较c、若其大与哨兵，其值赋给哨兵d、哨兵与第二份数组元素比较，将较大的值赋给第二份数组e、循环进行数组拆分3、对数据进行编码a、取数组元素与下一个元素比较b、若比下一个元素大，则与其交换c、后移，重复d、改变总元素值，并重复上述代码4、快速排序a、选取标准值b、比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，后 指针前移，重新比较c、否则后面元素赋给前面元素d、若后指针元素小于标准值，前指针后移，重新比较e、否则前面元素赋给后面元素5、简单选择排序a、从数组中选择出最小元素b、若不为当前元素，则交换c、后移将当前元素设为下一个元素堆排序a、生成小顶堆b、将堆的根节点移至数组的最后c、去掉已做过根节点的元素继续生成小顶堆d、数组倒置7、归并排序a、将数组每次以1/2拆分，直到为最小单位b、小相邻单位数组比较重排合成新的单位c、循环直至完成排序二、代码详细分析：1、插入排序关键代码： 取排序的第二个数据与前一个比较：if(rivri-l) 若比前一个小，则赋值给哨兵： r0=ri; 从后向前比较，将其插入在比其小的元素后： for(j=i-l;r0rj;j-)rj+l=rj;a+; rj+l=r0; 循环排序2、希尔排序关键代码： 将数组分成两份： d=n/2 将第一份数组的元素与哨兵比较： for(int i=d+l;i=n;i+) 若其大与哨兵，其值赋给哨兵： if(r00&r0=l;d=d/2)3、冒泡排序关键代码： 取数组元素与下一个元素比较： for(int i=l;iri+l) 若比下一个元素大，则与其交换： r0=ri; ri=ri+l; ri+l=r0; 后移，重复： for(int i=l;ibound;i+) 改变总元素值，并重复上述代码： int bound=pos;4、快速排序关键代码： 选取标准值： r0=ri 比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，后指针前移，重新比较： while(i=flag) j-; 否则后面元素赋给前面元素： ri=rj; 若后指针元素小于标准值，前指针后移，重新比较： while(ij&ri=flag) i+; 否则前面元素赋给后面元素： rj=ri;5、简单选择排序关键代码： 从数组中选择出最小元素： for(int j=i+l;j=n;j+) if(rjrj+1) j+; if(ri0;i-)coutri;7、归并排序关键代码： 将数组每次以1/2拆分，直到为最小单位：mid=(low+high)/2; 小相邻单位数组比较重排合成新的单位：while(i=m&j=high)if(L.ri=L.rj) tk+=L.ri+;else tk+=L.rj+;while(i=m) tk+=L.ri+;while(j=high) tk+=L.rj+;for(i=low,k=0;i 4 J 2 1青输人将要排序的7T幸（乱序）:怜10为 :30丄24勺4亍1010勺-J :.勺 耳,13 6 羁 3 4 . .1 7一 数数数ml:数数数 比比比鬼珞ft认次逖认拧次比比比 5 5 5 5 .-IL-I 1LL1 . 1 r l +IlLl14 4 4 二 “二一 二- 4444 54 54 54 S4 51113 3- - 22HlzfiHnrp匚尸tthLLLh 1 1 结结结-WHM:曰g具曰頁具具匕頁出岀出 一一 剪里口4 口吐吐 口吐 口士 口4 口吐 口-tl 口別 申4#4-.牛片氏仗4-|片反|;-芦4-.|芝 VF4-.午丄：iw# - 正口一3S.-3 3 3 2 12 2 2 2 rrP rrP ttP1111 E3T匚尹sh 士口-B 口士 了-42岀丄出出出丄岀出学土 卡屯匚通乱一匸沌fLr両乱 寸Aflw亠应厅序亠总匡匡厅一予序ffti爭事42、测试条件：按题目要求分别输入同组数据的正序、逆序、随机序列进行测试。3、测试结论：不同的排序方法移动次数比较次数和所用时间都是有所区别的。4. 总结 调试时出现的问题及解决的方法：在调试时，开始在归并排序的时候，虽然代码编译成 功，但调试出现了错误，通过逐步调试发现是由于发生了地址冲突。因此将原本的直接 调用数组改成了结构体数组，通过引用来实现归并排序，最终获得了成功 心得体会：学习、实现、对比、各种排序的算法，掌握各种排序算法的优劣，以及各种 算法使用的情况下一步的改进：改进计数器，寻找其他排序方式。附：源代码#includeusing namespace std;int Cnum = 0;int Mnum = 0;class LEDprivate :int compare;int move;public:void InsertSort(int r , int n) ;/直接插入排序void ShellInsert(int r,int n) ;/希尔排序void BubbleSort(int r,int n); 冒泡排序void Qsort(int r,int i,int j)； 快速排序void SelectSort(int r,int n); 选择排序void HeapSort (int r,int n);void MergePass(int r,int r1,int n ,int h);int Partion(int r ,int first ,int end );void Sift(int r,int k , int m);void Merge(int r,int r1,int s,int m,int t);void LED:InsertSort(int r , int n)/插入排序compare = 0;move = 0;for(int i=2;i=n;i+)if(riri-1)r0=ri;move +;ri=ri-1;move +;int j;for(j=i-2;r0rj;j-) compare+; rj+1=rj; move +;+compare;rj+1=r0;move +;+compare;for(int i=1;i=n;i+) coutri ;coutvv比较次数为vvcompare =1;d=d/2)for(int i=d+1;i=n;i+) if(ri0&r0rj;j=j-d)rj+d=rj;move+;compare+;rj+d=r0;move+;compare+;for(int i=1;i=n;i+)coutri ;coutvv比较次数为vvcompare ;移动次数为vvmovevv;void LED:BubbleSort(int r,int n)/冒泡排序改进compare = 0;move = 0;int pos = n ; while(pos != 0)int bound = pos;pos = 0;for(int i =1;i ri+1)r0 = ri;ri = ri+1;ri+1 = r0;/交换pos = i; move=move+3;for(int i=1;i=n;i+)coutri ;coutvv比较次数为vvcompare ;移动次数为vvmovevv;右侧扫描，寻找 pivot的元素前移左侧扫描，寻找pivot的元素后移int LED:Partion(int r ,int first ,int end ) int i = first ;int j = end;int pivot = ri;while(i j)/分区的左界/分区的右界/保存第一个元素，作为基准元素while(i=pivot) j - ; Cnum+;ri = rj ;while(ij)&(ri=pivot )i +;Cnum+; rj = ri;ri = pivot ;将轴值移动到i=j的位置return i;返回分区的分界值ivoid LED:Qsort(int r,int i,int j) if(i j) Mnum +;int pivotloc = Partion(r,i,j);Qsort (r,i,pivotloc -1);/左分区快速排序Qsort (r,pivotloc +1,j);/ 右分区快速排序else /简单选择排序n-l趟排序查找最小记录的位置indexvoid LED:SelectSort(int r,int n)compare = 0;move = 0;for(int i =1 ; i n ; i+)int index = i;for(int j = i + 1;j=n;j+)compare+; if(rjrindex) index = j;if(index != i)/若第一就是最小元素，则不用交换r0 = ri;ri = rindex;rindex = r0;利用r0，作为临时空间交换记录move+=3;for(int i=l;i=n;i+) coutri ;coutvv比较次数为vvcompare ;移动次数为vvmovevv; /*void LED:Sift(int r,int k , int m) int i = k, j = 2*i;while(j=m)if(jm&rj=rj)break;elser0 = ri; ri = rj; rj = r0; i = j ;j = 2* i;void LED:HeapSort (int r,int n) for(int i = n/2; i = 1 ; i-) Sift(r,i,n);for(int i = n;i1;i-) r0 = r1; r1 = ri;ri= r0;Sift(r,1,i-1); void LED: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(rirj) r1k+ = ri+;elser1k+ = rj+;/建堆/堆排序/输出堆顶元素/重建堆while(i=m)r1k+ = ri+;while(j=t) r1k+ = rj+;void LED:MergePass(int r,int r1,int n ,int h)int i = 1;while(i=n-2*h+1)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(;ij;coutvv请输入将要排序的元素(正序):vvendl;for(int i=1;iv=j;i+) cinr1i;coutvv请输入将要排序的元素(逆序):vvendl;for(int i=1;iv=j;i+) cinr2i;coutvv请输入将要排序的元素(乱序)：vvendl; for(int i=1;iv=j;i+) cinr3i;coutvvendl;LED l;for(int i= 1;iv=j;i+)Ri=r1i;coutvv直接插入排序正序输出结果：”;l.InsertSort(R,j); coutendl;for(int i= 1;i=j;i+) Ri=r2i;coutvv直接插入排序逆序输出结果：;l.InsertSort(R,j); coutendl;for(int i= 1;iv=j;i+) Ri=r3i;coutvv直接插入排序乱序输出结果：;l.InsertSort(R,j); coutvvendl;for(int i= 1;iv=j;i+) Ri=r1i;coutvv希尔排序正序输出结果：;l.ShellInsert(R,j); coutvvendl;for(int i= 1;iv=j;i+) Ri=r2i;coutvv希尔排序逆序输出结果：;l.ShellInsert(R,j); coutvvendl;for(int i= 1;iv=j;i+) Ri=r3i;coutvv希尔排序乱序输出结果：;l.ShellInsert(R,j); coutvvendl;for(int i= 1;iv=j;i+) Ri=r1i;coutvv冒泡排序正序输出结果：”;l.BubbleSort(R,j); coutvvendl;for(int i= 1;iv=j;i+) Ri=r2i;coutvv冒泡排序逆序输出结果：”;l.BubbleSort(R,j); coutendl;for(int i= 1;i=j;i+) Ri=r3i;coutvv冒泡排序乱序输出结果：”;l.BubbleSort(R,j); coutendl;for(int i= 1;iv=j;i+) Ri=r1i;coutvv快速排序正序输出结果：”;l.Qsort(R,l,j);for(int k=1;kv=j;k+) coutvvRkvv ;coutvv比较次数为vvCnum vv;移动次数为vvMnumvv; Cnum = 0;Mnum = 0;coutvvendl;for(int i= l;iv=j;i+) Ri=r2i;coutvv快速排序逆序输出结果：”;l.Qsort(R,1,j);for(int k=l;kv=j;k+) coutvvRkvv ;coutvv比较次数为vvCnum vv;移动次数为vvMnumvv; Cnum = 0;Mnum = 0;coutvvendl;for(int i= 1;iv=j;i+) Ri=r3i;coutvv快速排序乱序输出结果：”;l.Qsort(R,1,j);for(int k=1;kv=j;k+) coutvvRkvv ;coutvv比较次数为vvCnum vv;移动次数为vvMnumvv; coutvvendl;for(int i= 1;iv=j;i+) Ri=r1i;coutvv简单选择排序正序输出结果：;l.SelectSort(R,j); coutvvendl;for(int i= 1;iv=j;i+)Ri=r2i;coutvv简单选择排序逆序输出结果：”;l.SelectSort(R,j); coutendl;for(int i= 1;i=j;i+) Ri=r3i;coutvv简单选择排序乱序输出结果：”;l.SelectSort(R,j); coutendl;