数据结构实验9各种排序算法Word文件下载.docx
《数据结构实验9各种排序算法Word文件下载.docx》由会员分享，可在线阅读，更多相关《数据结构实验9各种排序算法Word文件下载.docx（10页珍藏版）》请在冰点文库上搜索。
希尔排序过程：
endl;
for（i=dk;
i<
MAX;
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;
cout<
sorts[i]<
"
;
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;
a[i]<
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;
待排序数组:
for（j;
j<
j++）
S[j]<
SHELL（S,dlta）;
//希尔排序
希尔排序后的结果:
ShowSorts（S）;
//显示拍完序后的数组
9.2
//9.2实现快速排序算法
#include<
stdio.h>
#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<
h）//区间内至少存在一个元素的情况
{
temp=R[l];
//用区间的第个记录作为基准
while（i!
=j）//从区间两端交替向中间扫描,直至i=j为止
{
while（j>
i&
R[j].key>
temp.key）
j--;
//从右向左扫描,找第个关键字小于temp.key的R[j]
if（i<
j）/*表示找到这样的R[j],R[i]、R[j]交换*/
{
R[i]=R[j];
i++;
}
while（i<
j&
R[i].key<
//从左向右扫描,找第个关键字大于temp.key的记录R[i]
j）//表示找到这样的R[i],R[i]、R[j]交换/
R[j]=R[i];
}
R[i]=temp;
printf（"
）;
//输出每一趟的排序结果
for（k=0;
8;
if（k==i）
printf（"
[%d]"
R[k].key）;
else
%4d"
\n"
QuickSort（R,l,i-1）;
//对左区间递归排序
QuickSort（R,i+1,h）;
//对右区间递归排序
inti,k,n=8;
KeyTypea[]={49,38,65,97,76,13,27,49};
RedTypeR[MAXE];
for（i=0;
n;
R[i].key=a[i];
printf（"
初始关键字:
//输出初始关键字序列
for（k=0;
printf（"
QuickSort（R,0,n-1）;
快速排序结果：
\n\n"
9.3
//9.3实现堆排序算法
iostream.h>
voidHeapAdjust（intdata[],ints,intm）/*排列成堆的形式*/
intj,rc;
rc=data[s];
/*保存处理元素*/
for（j=2*s;
=m;
j*=2）/*处理父亲元素*/
if（j<
m&
data[j]<
data[j+1]）++j;
/*取较大的孩子节点*/
if（rc>
data[j]）break;
data[s]=data[j];
/*父节点比较大的孩子节点大则互换,保证父节点比所有子节点都大（父节点存储在前面）*/
s=j;
}
data[s]=rc;
/*相当于data[j]=rc*/
voidDispHeap（intR[],inti,intn）/*以括号表示法输出建立的堆*/
if（i<
=n）
R[i];
/*输出根结点*/
if（2*i<
=n||2*i+1<
n）
（"
if（2*i<
DispHeap（R,2*i,n）;
/*递归调用输出左子树*/
"
if（2*i+1<
DispHeap（R,2*i+1,n）;
/*递归调用输出右子树*/
）"
voidHeap_sort（intdata[],intlong_n）/*堆排序函数*/
inti,temp;
for（i=long_n/2;
i>
0;
--i）
HeapAdjust（data,i,long_n）;
/*处理后，data[i]是这个数组后半部分的最大值*/
初始堆:
DispHeap（data,1,long_n）;
cout<
/*输出初始堆*/
for（i=long_n;
--i）/*进行n-1次循环,完成推排序*/
{
交换"
data[i]<
与"
data[1]<
输出"
data[1]<
temp=data[1];
/*把根元素（剩下元素中最大的那个）放到结尾,下一次只要排剩下的数就可以啦*/
data[1]=data[i];
data[i]=temp;
HeapAdjust（data,1,i-1）;
筛选调整得到堆:
DispHeap（data,1,i-1）;
/*输出每一趟的排序结果*/
inta[]={49,38,65,97,76,13,27,49};
intR[20];
for（i=1;
=n;
R[i]=a[i-1];
for（k=1;
R[k]<
for（i=n/2;
=1;
i--）//循环建立初始堆
HeapAdjust（R,i,n）;
Heap_sort（R,n）;
最终结果:
//输出最终结果
四，实验小结
1、通过本次实验，加深了我各种排序算法的认识。
2、将待排序列建成堆（初始堆生成）后，序列的第一个元素（堆顶元素）就一定是序列中的最大元素；
将其与序列的最后一个元素交换，将序列长度减一；
再将序列建成堆（堆调整）后，堆顶元素仍是序列中的最大元素，再次将其与序列最后一个元素交换并缩短序列长度；
反复此过程，直至序列长度为一，所得序列即为排序后结果。
升级会员 