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

1、数据结构实验四题目一排序实 验报告数据结构实验报告实验名称:实验四排序学生姓名：XX 班 级:班内序号:学 号：日 期：1.实验要求实验目的：liiJ通过选择实验内容中的两个题目之一，学 习、实现、对比、各种排序的算法，掌握各种 排序算法的优劣，以及各种算法使用的情况。题目1：使用简单数组实现下面各种排序算法，并 进行比较。排序算法如下：1、插入排序；2、希尔排序；3、4、5、6、7、8、9、冒泡排序； 快速排序； 简单选择排序； 堆排序； 归并排序； 基数排序（选作）;其他。具体要求如下：1、测试数据分成三类：正序、逆序、随机 数据。2、对于这三类数据，比较上述排序算法中 关键字的比较次数和

2、移动次数（其中关键 字交换记为3次移动）。3、对于这三类数据，比较上述排序算法中 不同算法的执行时间，精确到微妙。4、对2和3的结果进行分析，验证上述各 种算法的时间复杂度。5、编写main（）函数测试各种排序算法 的正确性。程序分析北京邮电大学信息与通信工程学院2.1存储结构存储结构：数组0A11A22A33A44A55A6NAn-12.2关键算法分析 一、关键算法:1、插入排序取排序的第二个数据与前一若比前一个小，则赋值给哨a、个比较b、c、从后向前比较，将其插入在 比其小的元素后d、循环排序2、希尔排序a、将数组分成两份b、将第一份数组的元素与哨兵 比较c、若其大与哨兵，其值赋给哨 兵d

3、、哨兵与第二份数组元素比 较，将较大的值赋给第二份数组e、循环进行数组拆分3、对数据进行编码a、取数组元素与下一个元素比 较b、若比下一个元素大，则与其 交换c、后移，重复d、改变总元素值，并重复上述4、快速排序a、选取标准值b、比较高低指针指向元素，若指针保持前后顺 序，且后指针元素大于标准值，后指针前移， 重新比较c、否则后面元素赋给前面元素d、若后指针元素小于标准值，前指针后移，重 新比较e、否则前面元素赋给后面元素5、简单选择排序a、从数组中选择出最小元素b、若不为当前元素，则交换c、后移将当前元素设为下一个元素6、堆排序a、生成小顶堆b、将堆的根节点移至数组的最后c、去掉已做过根节点

4、的元素继续生成小顶堆d、数组倒置7、归并排序a、将数组每次以1/2拆分，直到为最小单位b、小相邻单位数组比较重排合成新的单位c、循环直至完成排序 二、代码详细分析：1、插入排序关键代码：取排序的第二个数据与前一个比较:if(riri-1)若比前一个小，则赋值给哨兵:r0=ri;从后向前比较，将其插入在比其小的元素后：for(j=i-1;r0rj;j-)rj+1=rj;a+; rj+1=r0;循环排序2、希尔排序关键代码：将数组分成两份：d=n/2将第一份数组的元素与哨兵比较：for(inti=d+1;i=n;i+)若其大与哨兵，其值赋给哨兵：if(r00&r0=1;d=d/2)3、冒泡排序关键

5、代码：取数组元素与下一个元素比较：for(inti=1;iri+1)曲若比下一个元素大，则与其交换：r0=ri;北京邮电大学信息与通信工程学院ri=ri+1; ri+1=r0;后移，重复：for(int i=1;ibound;i+)改变总元素值，并重复上述代码：intbound=pos;4、快速排序关键代码：选取标准值：r0=ri比较高低指针指向元素，若指针保持前后顺 序，且后指针元素大于标准值，后指针前 移，重新比较：while(i=flag) j-;否则后面元素赋给前面元素：ri=rj;若后指针元素小于标准值，前指针后移，重新比较：while(ij&ri=flag) i+;否则前面元素赋给

6、后面元素：rj=ri;5、简单选择排序关键代码：从数组中选择出最小元素：for(int北京邮电大学信息与通信工程学院j=i+1;j=n;j+)if(rjrindex) index=j; 若不为当前元素，则交换：if(index!=i)r0=ri; ri=rindex; rindex=r0;后移将当前元素设为下一个元素：for(inti=1;in;i+)6、堆排序关键代码：生成小顶堆：while(j=m)if(jrj+1) j+;if(ri0;i-)coutri”;7、归并排序关键代码：将数组每次以1/2拆分，宜到为最小单位:mid=(low+high)/2;小相邻单位数组比较重排合成新的单位：

7、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=high;i+,k+) L.ri=tk;1 5 * |E：151115192648596177三、计算关键算法的时间、空间复杂度 插入排序O（02） 希尔排序O（02） 冒泡排序O（02） 快速排序O（nlog2n）简单选择排序O（02） 堆排序O（nlog2n） 归并排序O（nlog2n）程序运行结果1、测试主函数流程：流程图如图所示流程图示意图程序运行结果图

8、如下：111111青输人珞要舞序的元孝正序，L 2 3 4 5清输入珞要拌斥的元素逆序：4 3 k 1青输入将要排序的元素（乱序）：C:Win dowsVsyste m 32cmd exe=回I 泾2 2 2 2 2 2 2 2 : rrLl-ftli-.TrrT 11111111 FF.匚！-.HK 士口士口士口 出杲杲果果果果hMeK出出4; -J ，一 .71-/71- . _M_ Fu S* 习.1 .-7- 数敖数：9 4 ; &数数数 多孜为/I为为为为为为为孜多 比比比*堡仇欢次次土的佻次.次比比比 .!，.- .I，-.-.I,.5 54 45 5 54 4 4瓷绐结詹薯结物矗

9、一 杉闫逆1迂w-予字予.吏予序序举工曰5 票小米泡泡泡速笛速单单.毕挖 宜希希希言言E可甘主行 HpflD rn 匚！-.LkEk 1 士口士 士口 *.，手-一动孜数为0 i 多动孜.数为6 ； 多动衩数为6 ；102、测试条件:按题目要求分别输入同组数据的 正序、逆序、随机序列进行测试。3、测试结论:不同的排序方法移动次数比较次数和所用时间都是有所区别的。4.总结调试时出现的问题及解决的方法：在调试时， 开始在归并排序的时候，虽然代码编译成功， 但调试出现了错误，通过逐步调试发现是由于 发生了地址冲突。因此将原本的直接调用数组 改成了结构体数组，通过引用来实现归并排 序，最终获得了成功心

10、得体会：学习、实现、对比、各种排序的算 法，掌握各种排序算法的优劣，以及各种算法 使用的情况下一步的改进：改进计数器，寻找其他排序 方式。附：源代码#includeusing namespace std;int Cnum = 0;int Mnum = 0;class LED private :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(

11、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)/插入排序co

12、mpare = 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;r0r|j;j-)compare+;北京邮电大学信息与通信工程学院rj+1=rj;move +;+compare;rj+1=r0;move +;+compare;fOr(int i=1;i=n;i+)coutri;cout比较次数为compare ;移动 次数为move=1;d=dI2)for(int i=d+1;i0&r0rj;j=j-d)rj+d=rj;move+;compare+;rj+d=r0;move+

13、;compare+;for(int i=1;i=n;i+)coutri;cout”比较次数为compare ;移动次数为move”;”;北京邮电大学信息与通信工程学院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;cout比较次数

14、为compare ;移动 次数为move”;”;int LED:Partion(int r ,int first ,int end )int i = first ;分区的左界int j = end;/分区的右界int pivot = ri;保存第一个元素，作为基准元素while(i j)while(i=pivot)/右侧扫描，寻找 pivot的元素前移j -;Cnum+;ri = rj ;/左侧扫while(ij)&(ri=pivot ) 描，寻找pivot的元素后移 i +； Cnum+; rj = ri;ri = pivot ;将轴值移动到i=j的位置return i;返回分区的分界值iv

15、oid LED:Qsort(int r,int i,int j) if(i j) Mnum +;int pivotloc = Partion(r,ij);Qsort (r,i,pivotloc -1);左分区快速排序Qsort (r,pivotloc +1j);/ 右分区快速排序 elsevoid LED:SelectSort(int r,int n)简单选择排序compare = 0;move = 0;/n-1趟排序IIfor(int i =1 ; i n ; i+)int index = i;查找最小记录的位置indexfor(int j = i + 1;j=n;j+)compare+;i

16、f(rjrindex)index = j;if(index != i)/若第一就是最小元素，则不用交换r0 = ri;ri = rindex;rindex = r0;利用 r0，作为临时空间交换记录move+=3;fOr(int i=1;i=n;i+) coutri;cout比较次数为compare ;移动 次数为move”;”;/*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 LE

17、D: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+

18、 = 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);elsefor(;i=n;i+) r1i = ri;*/void main()int r110000,r210000,r310000;intR10000;char y ;int j=0;cout请输入元素个数:j;cout请输入将要排序的元素(正序):endl;for(int i=1;ir1i;cou

19、t请输入将要排序的元素(逆序):endl;for(int i=1;ir2i;cout请输入将要排序的元素(乱序)：endl;for(int i=1;ir3i;coutendl;LED l;for(int i= 1;i=j;i+)Ri=r1i;cout直接插入排序正序输出结果：七l.InsertSort(RJ);coutendl;for(int i= 1;i=j;i+)Ri=r2i;cout直接插入排序逆序输出结果:七LInsertSort(RJ);coutendl;for(int i= 1;i=j;i+)Ri=r3i;cout直接插入排序乱序输出结果:”;l.InsertSort(RJ);co

20、utendl;for(int i= 1;i=j;i+)Ri=r1i;cout希尔排序正序输出结果： ;LShellInsert(RJ);北京邮电大学信息与通信工程学院coutendl;for(int i= 1;i=j;i+)Ri=r2i;cout”希尔排序逆序输出结果:七l.ShellInsert(RJ);coutendl;for(int i= 1;i=j;i+)Ri=r3i;cout希尔排序乱序输出结果:七l.ShellInsert(Rj);coutendl;for(int i= 1;i=j;i+)Ri=r1i;cout”冒泡排序正序输出结果:”;l.BubbleSort(Rj); coutendl;for(int i= 1;i=j;i+)Ri=r2i;cout冒泡排序逆序输出结果:七l.BubbleSort(Rj);coutendl;for(int i=