大数据结构实验四题目一排序实验报告材料.docx
《大数据结构实验四题目一排序实验报告材料.docx》由会员分享，可在线阅读，更多相关《大数据结构实验四题目一排序实验报告材料.docx（22页珍藏版）》请在冰点文库上搜索。
大数据结构实验四题目一排序实验报告材料
数据结构实验报告
实验名称：
实验四——排序
学生姓名：
XX
班级：
班内序号：
学号：
日期：
1．实验要求
实验目的：
通过选择实验内容中的两个题目之一，学习、实现、对比、各种排序的算法，掌握各种排序算法的优劣，以及各种算法使用的情况。
题目1：
使用简单数组实现下面各种排序算法，并进行比较。
排序算法如下：
1、插入排序；
2、希尔排序；
3、冒泡排序；
4、快速排序；
5、简单选择排序；
6、堆排序；
7、归并排序；
8、基数排序（选作）；
9、其他。
具体要求如下：
1、测试数据分成三类：
正序、逆序、随机数据。
2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换记为3次移动）。
3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙。
4、对2和3的结果进行分析，验证上述各种算法的时间复杂度。
5、编写main（）函数测试各种排序算法的正确性。
2.程序分析
2.1存储结构
存储结构：
数组
0
A1
1
A2
2
A3
3
A4
4
A5
5
A6
……
……
N
An-1
2.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、后移将当前元素设为下一个元素
6、堆排序
a、生成小顶堆
b、将堆的根节点移至数组的最后
c、去掉已做过根节点的元素继续生成小顶堆
d、数组倒置
7、归并排序
a、将数组每次以1/2拆分，直到为最小单位
b、小相邻单位数组比较重排合成新的单位
c、循环直至完成排序
二、代码详细分析：
1、插入排序
关键代码：
1取排序的第二个数据与前一个比较：
if（r[i]2若比前一个小，则赋值给哨兵：
r[0]=r[i];
3从后向前比较，将其插入在比其小的元素后：
for（j=i-1;r[0]{r[j+1]=r[j];a++;}r[j+1]=r[0];
4循环排序
2、希尔排序
关键代码：
1将数组分成两份：
d=n/2
2将第一份数组的元素与哨兵比较：
for（inti=d+1;i<=n;i++）
3若其大与哨兵，其值赋给哨兵：
if（r[0]4哨兵与第二份数组元素比较，将较大的值赋给第二份数组：
for（j=i-d;j>0&&r[0]5循环进行数组拆分：
for（int;d>=1;d=d/2）
3、冒泡排序
关键代码：
1取数组元素与下一个元素比较：
for（inti=1;ir[i+1]）
2若比下一个元素大，则与其交换：
r[0]=r[i];r[i]=r[i+1];r[i+1]=r[0];
3后移，重复：
for（inti=1;i4改变总元素值，并重复上述代码：
intbound=pos;
4、快速排序
关键代码：
1选取标准值：
r[0]=r[i]
2比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，后指针前移，重新比较：
while（i=flag）{j--;}
3否则后面元素赋给前面元素：
r[i]=r[j];
4若后指针元素小于标准值，前指针后移，重新比较：
while（i5否则前面元素赋给后面元素：
r[j]=r[i];
5、简单选择排序
关键代码：
1从数组中选择出最小元素：
for（intj=i+1;j<=n;j++）
2{if（r[j]3若不为当前元素，则交换：
if（index!
=i）{r[0]=r[i];r[i]=r[index];r[index]=r[0];}
4后移将当前元素设为下一个元素：
for（inti=1;i6、堆排序
关键代码：
1生成小顶堆：
while（j<=m）{if（jr[j+1]）{j++;}
2if（r[i]3else{intx;x=r[i];r[i]=r[j];r[j]=x;i=j;j=2*i;}}
4将堆的根节点移至数组的最后：
x=r[1];r[1]=r[n-i+1];r[n-i+1]=x;
5去掉已做过根节点的元素继续生成小顶堆：
sift（r,1,n-i,x,y）;
6数组倒置输出:
for（inti=n;i>0;i--）cout<7、归并排序
关键代码：
1将数组每次以1/2拆分，直到为最小单位：
mid=（low+high）/2;
2小相邻单位数组比较重排合成新的单位：
while（i<=m&&j<=high）
if（L.r[i]<=L.r[j]）t[k++]=L.r[i++];
elset[k++]=L.r[j++];
while（i<=m）t[k++]=L.r[i++];
while（j<=high）t[k++]=L.r[j++];
for（i=low,k=0;i<=high;i++,k++）L.r[i]=t[k];
三、计算关键算法的时间、空间复杂度
插入排序O（n2）
希尔排序O（n2）
冒泡排序O（n2）
快速排序O（nlog2n）
简单选择排序O（n2）
堆排序O（nlog2n）
归并排序O（nlog2n）
3.程序运行结果
1、测试主函数流程：
流程图如图所示
流程图示意图
程序运行结果图如下：
2、测试条件：
按题目要求分别输入同组数据的正序、逆序、随机序列进行测试。
3、测试结论：
不同的排序方法移动次数比较次数和所用时间都是有所区别的。
4.总结
调试时出现的问题及解决的方法：
在调试时，开始在归并排序的时候，虽然代码编译成功，但调试出现了错误，通过逐步调试发现是由于发生了地址冲突。
因此将原本的直接调用数组改成了结构体数组，通过引用来实现归并排序，最终获得了成功
心得体会：
学习、实现、对比、各种排序的算法，掌握各种排序算法的优劣，以及各种算法使用的情况
下一步的改进：
改进计数器，寻找其他排序方式。
附：
源代码
#include
usingnamespacestd;
intCnum=0;
intMnum=0;
classLED
{
private:
intcompare;
intmove;
public:
voidInsertSort（intr[],intn）;//直接插入排序
voidShellInsert（intr[],intn）;//希尔排序
voidBubbleSort（intr[],intn）;//冒泡排序
voidQsort（intr[],inti,intj）;//快速排序
voidSelectSort（intr[],intn）;//选择排序
voidHeapSort（intr[],intn）;
voidMergePass（intr[],intr1[],intn,inth）;
intPartion（intr[],intfirst,intend）;
voidSift（intr[],intk,intm）;
voidMerge（intr[],intr1[],ints,intm,intt）;
};
voidLED:
:
InsertSort（intr[],intn）//插入排序
{
compare=0;
move=0;
for（inti=2;i<=n;i++）
{
if（r[i]{
r[0]=r[i];
move++;
r[i]=r[i-1];
move++;
intj;
for（j=i-2;r[0]{
compare++;
r[j+1]=r[j];
move++;
}
++compare;
r[j+1]=r[0];
move++;
}
++compare;
}
for（inti=1;i<=n;i++）
cout<cout<<"比较次数为"<}
voidLED:
:
ShellInsert（intr[],intn）//希尔排序
{compare=0;
move=0;
for（intd=n/2;d>=1;d=d/2）
{
for（inti=d+1;i<=n;i++）
{
if（r[i]{
move++;
r[0]=r[i];
intj;
for（j=i-d;j>0&&r[0]{
r[j+d]=r[j];
move++;
}
compare++;
r[j+d]=r[0];
move++;
}
compare++;
}
}
for（inti=1;i<=n;i++）
cout<cout<<"比较次数为"<}
voidLED:
:
BubbleSort（intr[],intn）//冒泡排序改进
{
compare=0;
move=0;
intpos=n;
while（pos!
=0）
{
intbound=pos;
pos=0;
for（inti=1;i{
compare++;
if（r[i]>r[i+1]）
{
r[0]=r[i];
r[i]=r[i+1];
r[i+1]=r[0];//交换
pos=i;
move=move+3;
}
}
}
for（inti=1;i<=n;i++）
cout<cout<<"比较次数为"<}
intLED:
:
Partion（intr[],intfirst,intend）
{
inti=first;//分区的左界
intj=end;//分区的右界
intpivot=r[i];//保存第一个元素，作为基准元素
while（i{
while（（i=pivot））//右侧扫描，寻找{
j--;
Cnum++;
}
r[i]=r[j];
while（（ipivot的元素后移
{
i++;
Cnum++;
}
r[j]=r[i];
}
r[i]=pivot;//将轴值移动到i=j的位置
returni;//返回分区的分界值i
}
voidLED:
:
Qsort（intr[],inti,intj）
{
if（i{Mnum++;
intpivotloc=Partion（r,i,j）;
Qsort（r,i,pivotloc-1）;//左分区快速排序
Qsort（r,pivotloc+1,j）;//右分区快速排序
}
else
{
}
}
voidLED:
:
SelectSort（intr[],intn）//简单选择排序
{
compare=0;
move=0;
for（inti=1;i{
intindex=i;//查找最小记录的位置index
for（intj=i+1;j<=n;j++）
{
compare++;
if（r[j]index=j;
}
if（index!
=i）//若第一就是最小元素，则不用交换
{
r[0]=r[i];
r[i]=r[index];
r[index]=r[0];//利用r[0]，作为临时空间交换记录
move+=3;
}
}
for（inti=1;i<=n;i++）
cout<cout<<"比较次数为"<}
/*
voidLED:
:
Sift（intr[],intk,intm）
{
inti=k,j=2*i;
while（j<=m）
{
if（jif（r[i]>=r[j]）break;
else
{
r[0]=r[i];
r[i]=r[j];
r[j]=r[0];
i=j;
j=2*i;
}
}
}
voidLED:
:
HeapSort（intr[],intn）
{
for（inti=n/2;i>=1;i--）//建堆
Sift（r,i,n）;
for（inti=n;i>1;i--）//堆排序
{r[0]=r[1];r[1]=r[i];r[i]=r[0];//输出堆顶元素
Sift（r,1,i-1）;//重建堆
}
}
voidLED:
:
Merge（intr[],intr1[],ints,intm,intt）
{
inti=s;
intj=m+1;
intk=s;
while（i<=m&&j<=t）
{
if（r[i]r1[k++]=r[i++];
else
r1[k++]=r[j++];
}
while（i<=m）
r1[k++]=r[i++];
while（j<=t）
r1[k++]=r[j++];
}
voidLED:
:
MergePass（intr[],intr1[],intn,inth）
{
inti=1;
while（i<=n-2*h+1）
{
Merge（r,r1,i,i+h-1,i+2*h-1）;
i+=2*h;
}
if（iMerge（r,r1,i,i+h-1,n）;
else
for（;i<=n;i++）
r1[i]=r[i];
}
*/
voidmain（）
{
intr1[10000],r2[10000],r3[10000];intR[10000];
chary;
intj=0;
cout<<"请输入元素个数：
"<cin>>j;
cout<<"请输入将要排序的元素（正序）：
"<for（inti=1;i<=j;i++）
{
cin>>r1[i];
}
cout<<"请输入将要排序的元素（逆序）：
"<for（inti=1;i<=j;i++）
{
cin>>r2[i];
}
cout<<"请输入将要排序的元素（乱序）：
"<for（inti=1;i<=j;i++）
{
cin>>r3[i];
}
cout<LEDl;
for（inti=1;i<=j;i++）
{
R[i]=r1[i];
}
cout<<"直接插入排序正序输出结果：
";l.InsertSort（R,j）;
cout<for（inti=1;i<=j;i++）
{
R[i]=r2[i];
}
cout<<"直接插入排序逆序输出结果：
";l.InsertSort（R,j）;
cout<for（inti=1;i<=j;i++）
{
R[i]=r3[i];
}
cout<<"直接插入排序乱序输出结果：
";l.InsertSort（R,j）;
cout<for（inti=1;i<=j;i++）
{
R[i]=r1[i];
}
cout<<"希尔排序正序输出结果：
";l.ShellInsert（R,j）;
cout<for（inti=1;i<=j;i++）
{
R[i]=r2[i];
}
cout<<"希尔排序逆序输出结果：
";l.ShellInsert（R,j）;
cout<for（inti=1;i<=j;i++）
{
R[i]=r3[i];
}
cout<<"希尔排序乱序输出结果：
";l.ShellInsert（R,j）;
cout<for（inti=1;i<=j;i++）
{
R[i]=r1[i];
}
cout<<"冒泡排序正序输出结果：
";l.BubbleSort（R,j）;
cout<for（inti=1;i<=j;i++）
{
R[i]=r2[i];
}
cout<<"冒泡排序逆序输出结果：
";l.BubbleSort（R,j）;
cout<for（inti=1;i<=j;i++）
{
R[i]=r3[i];
}
cout<<"冒泡排序乱序输出结果：
";l.BubbleSort（R,j）;
cout<for（inti=1;i<=j;i++）
{
R[i]=r1[i];
}
cout<<"快速排序正序输出结果：
";l.Qsort（R,1,j）;
for（intk=1;k<=j;k++）
cout<cout<<"比较次数为"<Cnum=0;Mnum=0;
cout<for（inti=1;i<=j;i++）
{
R[i]=r2[i];
}
cout<<"快速排序逆序输出结果：
";l.Qsort（R,1,j）;
for（intk=1;k<=j;k++）
cout<cout<<"比较次数为"<Cnum=0;Mnum=0;
cout<for（inti=1;i<=j;i++）
{
R[i]=r3[i];
}
cout<<"快速排序乱序输出结果：
";l.Qsort（R,1,j）;
for（intk=1;k<=j;k++）
cout<cout<<"比较次数为"<cout<for（inti=1;i<=j;i++）
{
R[i]=r1[i];
}
cout<<"简单选择排序正序输出结果：
";l.SelectSort（R,j）;
cout<for（inti=1;i<=j;i++）
{
R[i]=r2[i];
}
cout<<"简单选择排序逆序输出结果：
";l.SelectSort（R,j）;
cout<for（inti=1;i<=j;i++）
{
R[i]=r3[i];
}
cout<<"简单选择排序乱序输出结果：
";l.SelectSort（R,j）;
cout<}
升级会员 