数据结构实验排序算法C++实现.docx
《数据结构实验排序算法C++实现.docx》由会员分享，可在线阅读，更多相关《数据结构实验排序算法C++实现.docx（19页珍藏版）》请在冰点文库上搜索。
数据结构实验排序算法C++实现
实验三排序
姓名：
班级：
学号：
1.实验要求
1.1实验目的通过选择下面题目，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。
1.2实验内容使用简单数组实现下面各种排序算法，并进行比较。
排序算法：
1、插入排序
2、希尔排序
3、冒泡排序
4、快速排序
5、简单选择排序
6、堆排序（选作）
7、归并排序（选作）
8、基数排序（选作）
9、其他
要求：
1、测试数据分成三类：
正序、逆序、随机数据
2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。
3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）
4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main（）函数测试线性表的正确性。
2程序分析与关键代码
2.1存储结构
存储结构：
一维数组
2.2关键算法分析
1．直接插入排序：
数组分为有序区与无序区，初始时首个元素为有序。
从第二个元素开始，每个元素一趟，顺序查找获得插入点。
一趟实现，将待插入记录赋值给哨兵r[0],从后向前进行顺序查找，元素后移。
代码实现
if（r[i]{
r[0]=r[i];//待插入元素赋值给r[0]r[i]=r[i-1];
for（intj=i-2;r[0]r[j+1]=r[j];
r[j+1]=r[0];
}
2.希尔排序：
将数组分成两份，将第一份数组的元素与哨兵比较，若其大于哨兵，将其值赋给哨兵，
哨兵与第二份数组元素比较，将较大的值赋给第二份数组，循环进行，将数组拆分。
关键代码
for（inti=d+1;i<=n;i++）//一趟希尔排序
{
if（r[i]r[0]=r[i];
intj;
for（j=i-d;j>0&&r[0]{
r[j+d]=r[j];
r[j+d]=r[0];
3.改进的冒泡排序：
排序过程分为有序区与无序区，一趟冒泡排序将一个元素由无序区添加到有序区，初试有序区为空，将无序区由前向后依次将相邻元素关键码进行比较，正序不变，反序交换，
关键码大的逐渐后移，重复比较，直至结尾。
为去除对无序区中部分有序元素的无用比较，将前一趟最后交换位置定为pos，若前一趟排序没有元素交换，即排好序，排序算法结束。
关键代码：
intpos=n;
while（pos!
=0）
{
intbound=pos;//将前一趟最后交换位置定为pos，即无序元素范围pos=0;//设置本趟排序元素交换起始位置
for（inti=1;i{
if（r[i]>r[i+1]）//相邻比较
{
r[0]=r[i];
r[i]=r[i+1];
r[i+1]=r[0];//交换pos=i;//记录本次交换位置
}
}
4．快速排序：
选取轴值，将排序元素分为两个区，左侧关键码小于轴值，右侧大于轴值，在各个小
分区重复上述过程，直至有序。
选取轴值，比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，
后指针前移，重新比较。
否则后面元素赋给前面元素，若后指针元素小于标准值，前
指针后移，重新比较，否则前面元素赋给后面元素。
左右侧如此扫描，重复，直至左右侧值相等，排序结束。
代码实现一趟快排
intSORT:
:
Partion（intr[],intfirst,intend）//一趟快排
{
inti=first;//分区的左界
intj=end;//分区的右界
intpivot=r[i];//保存第一个元素，作为基准元素
while（i{
while（（i=pivot））//右侧扫描，寻找{
j--;
Cnum++;
}
r[i]=r[j];
while（（ipivot的元素后移
Cnum++;
将其置于有
重复扫描无
则不用交换
r[j]=r[i];
}
r[i]=pivot;//将轴值移动到i=j的位置
returni;//返回分区的分界值i
}
5.简单选择排序：
仍将待排序数列分为有序区与无序区，一趟扫描，获得数组中最小的元素，序区中（即将最小数据与第一个数据交换，将有序区放置在数组前部分。
序区数据，每次获得最小的数据，并置于有序区中。
扫描数组，交换，为关键算法。
代码实现一趟排序：
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];
}
6.堆排序：
在简单选择排序一趟结束时，堆排序能够保留其比较结果，减少比较次数，提高排序效率。
实现方法需建立大根堆或者小根堆，通过对建成的堆进行排序。
关键算法为建堆，排序，如小根堆。
生成小跟堆：
while（j<=m）{if（jr[j+1]）{j++;}
if（r[i]else{intx;x=r[i];r[i]=r[j];r[j]=x;i=j;j=2*i;}}
将堆的根节点移至数组的最后：
x=r[1];r[1]=r[n-i+1];r[n-i+1]=x;去掉已做过根节点的元素继续生成小根堆：
sift（r,1,n-i,x,y）;
数组倒置输出:
for（inti=n;i>0;i--）cout<堆排序
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）;//重建堆
3.各排序算法时间复杂度
插入排序O（n2）
希尔排序O（nlog2n~n2）
冒泡排序O（n2）
快速排序O（nlog2n）
简单选择排序O（n2）
堆排序O（nlog2n）
归并排序O（nlog2n）
4.测试结果
5.总结
调试总是出错，测试函数写得不好，不怎么会写，几个选作的最后还是没调出来。
心得体会：
学习、实现、对比、各种排序的算法，掌握各种排序算法的优劣，在数组情况下，差距不很明显，不同的排序方法移动次数比较次数和所用时间都是有所区别的。
学会各种算法使用的情况
下一步的改进：
改进计数器，寻找其他排序方式。
5.附原代码
#includeusingnamespacestd;
intCnum=0;//统计比较
intMnum=0;//统计移动
classSORT
{
private:
intcompare;//比较次数
intmove;//移动次数
public:
voidInsertSort（intr[],intn）;
//直接插入排序
voidShellInsert（intr[],intn）;
//希尔排序
voidBubbleSort（intr[],intn）;
//冒泡排序
intPartion（intr[],intfirst,intend）;
//一趟快排
voidSelectSort（intr[],intn）;
//选择排序
voidSift（intr[],intk,intm）;
//建堆
voidHeapSort（intr[],intn）;
//堆排序
voidSORT:
:
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<<"比较次数为"<voidSORT:
:
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<<"比较次数为"<voidSORT:
:
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<<"比较次数为"<}
intSORT:
:
Partion（intr[],intfirst,intend）//一趟快排
{
inti=first;//分区的左界
intj=end;//分区的右界
intpivot=r[i];//保存第一个元素，作为基准元素
while（i{
while（（i=pivot））//右侧扫描，寻找{
j--;
Cnum++;
r[i]=r[j];
{
i++;
Cnum++;
}
r[j]=r[i];
}
r[i]=pivot;//将轴值移动到i=j的位置
returni;//返回分区的分界值i
}
voidSORT:
:
Qsort（intr[],inti,intj）
{
if（i{Mnum++;
intpivotloc=Partion（r,i,j）;
Qsort（r,i,pivotloc-1）;//左分区快速排序
Qsort（r,pivotloc+1,j）;//右分区快速排序
}
else
{
voidSORT:
:
SelectSort（intr[],intn）
//简单选择排序
compare=0;
move=0;
for（inti=1;i{
intindex=i;
for（intj=i+1;j<=n;j++）
{
//n-1趟排序
//查找最小记录的位置
index
compare++;
if（r[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<<"比较次数为"<}
voidSORT:
:
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;
}
}
voidSORT:
:
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）;
}
}
intmain（）//测试主函数
{
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<SORTl;
for（inti=1;i<=j;i++）
{
R[i]=r1[i];
cout<<"直接插入排序正序输出结果：
cout<for（inti=1;i<=j;i++）
{
R[i]=r2[i];
}
cout<<"直接插入排序逆序输出结果：
cout<for（inti=1;i<=j;i++）
{
R[i]=r3[i];
}
cout<<"直接插入排序乱序输出结果：
cout<for（inti=1;i<=j;i++）
{
R[i]=r1[i];
}
cout<<"希尔排序正序输出结果：
cout<for（inti=1;i<=j;i++）
";l.InsertSort（R,j）;
";l.InsertSort（R,j）;
";l.InsertSort（R,j）;
";l.ShellInsert（R,j）;
R[i]=r2[i];
}
cout<<"希尔排序逆序输出结果：
cout<for（inti=1;i<=j;i++）
{
R[i]=r3[i];
}
cout<<"希尔排序乱序输出结果：
cout<for（inti=1;i<=j;i++）
{
R[i]=r1[i];
}
cout<<"冒泡排序正序输出结果：
cout<for（inti=1;i<=j;i++）
{
R[i]=r2[i];
}
cout<<"冒泡排序逆序输出结果：
";l.ShellInsert（R,j）;
";l.ShellInsert（R,j）;
";l.BubbleSort（R,j）;
";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<<"比较次数为"<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];
";l.SelectSort（R,j）;
";l.SelectSort（R,j）;
cout<<"简单选择排序逆序输出结果：
cout<for（inti=1;i<=j;i++）
{
R[i]=r3[i];
}
cout<<"简单选择排序乱序输出结果：
cout<}
升级会员 