数据结构实验9各种排序算法.docx
《数据结构实验9各种排序算法.docx》由会员分享，可在线阅读，更多相关《数据结构实验9各种排序算法.docx（10页珍藏版）》请在冰点文库上搜索。
数据结构实验9各种排序算法
9.1实现希尔排序算法
一，实验目的
1.熟悉掌握各种排序算法，深刻理解各种排序算法及其执行的过程；
2.学会分析各种排序算法的过程和性能。
二，实验内容
9.1实现希尔排序算法
编写一个程序实现希尔排序，dk={5,3,1}，并输出{6,9,7,8,0,1,3,2,4,5}的排序过程。
9.2实现快速排序算法
编写一个程序实现快速排序，并输出{49,38,65,97,76,13,27,49}的排序过程（要求输出每次枢轴记录到位后的关键字序列）。
9.3实现堆排序算法
编写一个程序实现堆排序，并输出{49,38,65,97,76,13,27,49}的排序过程（要求输出初始堆、第一个记录与堆尾交换后、重新调整成堆，直至排好序后的关键字序列）。
三，源代码及结果截图
9.1
//9.1实现希尔排序算法
#include
usingnamespacestd;
#defineMAX10
voidShellSorts（intsorts[],intdk）//一次希尔排序
{
inttemp,j,i;
cout<<"希尔排序过程：
"<for（i=dk;i{
if（sorts[i-dk]>sorts[i]）
{
temp=sorts[i];
sorts[i]=sorts[i-dk];
for（j=i-dk;j>=0&&sorts[j]>temp;j-=dk）
sorts[j+dk]=sorts[j];
sorts[j+dk]=temp;
}
}
for（i=0;icout<cout<}
intdlta[]={5,3,1};//希尔排序的DK
voidSHELL（intsorts[],intdk[]）//希尔排序
{
for（intk=0;k<3;k++）
ShellSorts（sorts,dlta[k]）;
}
voidShowSorts（inta[]）//显示排序后的结果
{
inti=0;
for（i;icout<cout<}
voidmain（）
{
intS[MAX]={6,9,7,8,0,1,3,2,4,5};//待排序数组
//intJG[MAX]={0,1,2,3,4,5,6,7,8,9};//正确排序结果，方便自己看的
intj=0;
cout<<"待排序数组:
"<for（j;jcout<cout<SHELL（S,dlta）;//希尔排序
cout<<"希尔排序后的结果:
"<ShowSorts（S）;//显示拍完序后的数组
}
9.2
//9.2实现快速排序算法
#include
#defineMAXE20//线性表中最多元素个数
typedefintKeyType;
typedefcharInfoType[8];
typedefstruct//记录类型
{
KeyTypekey;//关键字项
InfoTypedata;//其他数据项,类型为InfoType
}RedType;
voidQuickSort（RedTypeR[],intl,inth）//对R[s]至R[t]的元素进行快速排序
{
inti=l,j=h,k;
RedTypetemp;
if（l{
temp=R[l];//用区间的第个记录作为基准
while（i!
=j）//从区间两端交替向中间扫描,直至i=j为止
{
while（j>i&&R[j].key>temp.key）
j--;//从右向左扫描,找第个关键字小于temp.key的R[j]
if（i{
R[i]=R[j];
i++;
}
while（ii++;//从左向右扫描,找第个关键字大于temp.key的记录R[i]
if（i{
R[j]=R[i];
j--;}
}
R[i]=temp;
printf（""）;//输出每一趟的排序结果
for（k=0;k<8;k++）
if（k==i）
printf（"[%d]",R[k].key）;
else
printf（"%4d",R[k].key）;
printf（"\n"）;
QuickSort（R,l,i-1）;//对左区间递归排序
QuickSort（R,i+1,h）;//对右区间递归排序
}
}
voidmain（）
{
inti,k,n=8;
KeyTypea[]={49,38,65,97,76,13,27,49};
RedTypeR[MAXE];
for（i=0;iR[i].key=a[i];
printf（"\n"）;
printf（"初始关键字:
"）;//输出初始关键字序列
for（k=0;kprintf（"%4d",R[k].key）;
printf（"\n"）;
QuickSort（R,0,n-1）;
printf（"快速排序结果：
"）;//输出初始关键字序列
for（k=0;kprintf（"%4d",R[k].key）;
printf（"\n\n"）;
}
9.3
//9.3实现堆排序算法
#include
voidHeapAdjust（intdata[],ints,intm）/*排列成堆的形式*/
{
intj,rc;
rc=data[s];/*保存处理元素*/
for（j=2*s;j<=m;j*=2）/*处理父亲元素*/
{
if（jif（rc>data[j]）break;
data[s]=data[j];/*父节点比较大的孩子节点大则互换,保证父节点比所有子节点都大（父节点存储在前面）*/
s=j;
}
data[s]=rc;/*相当于data[j]=rc*/
}
voidDispHeap（intR[],inti,intn）/*以括号表示法输出建立的堆*/
{
if（i<=n）
cout<if（2*i<=n||2*i+1{
cout<<"（";
if（2*i<=n）
DispHeap（R,2*i,n）;/*递归调用输出左子树*/
cout<<",";
if（2*i+1<=n）
DispHeap（R,2*i+1,n）;/*递归调用输出右子树*/
cout<<"）";
}
}
voidHeap_sort（intdata[],intlong_n）/*堆排序函数*/
{
inti,temp;
for（i=long_n/2;i>0;--i）
HeapAdjust（data,i,long_n）;/*处理后，data[i]是这个数组后半部分的最大值*/
}
cout<<"初始堆:
";
DispHeap（data,1,long_n）;cout<for（i=long_n;i>0;--i）/*进行n-1次循环,完成推排序*/
{
cout<<"交换"<temp=data[1];/*把根元素（剩下元素中最大的那个）放到结尾,下一次只要排剩下的数就可以啦*/
data[1]=data[i];
data[i]=temp;
HeapAdjust（data,1,i-1）;
cout<<"筛选调整得到堆:
";
DispHeap（data,1,i-1）;cout<}
}
voidmain（）
{
inti,k,n=8;
inta[]={49,38,65,97,76,13,27,49};
intR[20];
for（i=1;i<=n;i++）
R[i]=a[i-1];
cout<cout<<"初始关键字:
";
for（k=1;k<=n;k++）
cout<cout<for（i=n/2;i>=1;i--）//循环建立初始堆
HeapAdjust（R,i,n）;
Heap_sort（R,n）;
cout<<"最终结果:
";//输出最终结果
for（k=1;k<=n;k++）
cout<cout<}
四，实验小结
1、通过本次实验，加深了我各种排序算法的认识。
2、将待排序列建成堆（初始堆生成）后，序列的第一个元素（堆顶元素）就一定是序列中的最大元素；
将其与序列的最后一个元素交换，将序列长度减一；
再将序列建成堆（堆调整）后，堆顶元素仍是序列中的最大元素，再次将其与序列最后一个元素交换并缩短序列长度；反复此过程，直至序列长度为一，所得序列即为排序后结果。
升级会员 