数据结构与算法排序资料Word格式.docx
《数据结构与算法排序资料Word格式.docx》由会员分享，可在线阅读，更多相关《数据结构与算法排序资料Word格式.docx（18页珍藏版）》请在冰点文库上搜索。
stdio.h"
stdlib.h"
time.h"
#defineMAX50
//顺序表结构体
typedefstruct
{
ints[MAX];
//存放一批随机整数，数组大小MAX不能扩充
intlength;
//当前表中元素的个数
}SeqList;
//功能菜单
voidmenu（）
printf（"
\n\t*************排------序*************\n"
）;
\t*1随机产生一批整数*\n"
\t*2手动输入一批整数*\n"
\t*3将表中数据随机化*\n"
\t*4快速排序*\n"
\t*5希尔排序*\n"
\t*6堆排序*\n"
\t*7归并排序*\n"
\t*8依次显示表中所有数据*\n"
\t*0退出程序*\n"
\t************************************\n"
}
/*初始化一个空的顺序表*/
SeqList*init（）
//开辟顺序表空间
SeqList*p=（SeqList*）malloc（sizeof（SeqList））;
//设置顺序表的初始长度为0
p->
length=0;
//返回整个顺序表的（起始）地址
returnp;
/*随机产生一批整数到线性表中*/
voidrandGen（SeqList*p）
intnum,i;
请输入元素个数（<
=%d）：
\n"
MAX-1）;
scanf（"
%d"
&
num）;
srand（（int）time（0））;
if（num<
=MAX）
{
//随机产生num个整数存入顺序表中（从1号单元开始存放，0号单元留作“哨兵”）
for（i=1;
i<
=num;
i++）
p->
s[i]=1+（int）（100.0*rand（）/（RAND_MAX+1.0））;
p->
length=num;
printf（"
顺序表中已成功放入%d个整数!
num）;
}
else
顺序表空间不够，请重新输入元素个数!
/*手动输入一批整数到线性表中*/
voidmanInput（SeqList*p）
请输入%d个整数：
=MAX-1）
//输入num个整数存入顺序表中（从1号单元开始存放，0号单元留作“哨兵”）
scanf（"
（p->
s[i]））;
顺序表中已成功输入%d个整数!
/*将顺序表中现有元素打乱为随机排列*/
voidrandomizeList（SeqList*p）
inti,selectLoc,tmp;
//借助选择法排序的思想，每次从尚未挑选的序列中随机挑选一个元素，
//将随机选中的元素交换到尚未选中元素序列的最前面或最后面。
for（i=1;
p->
length;
//产生一个属于区间[i,p->
length]的随机数selectLoc
selectLoc=i+（int）（（p->
length-i）*rand（）/（RAND_MAX+1.0））;
if（selectLoc!
=i）
{
tmp=p->
s[i];
s[i]=p->
s[selectLoc];
s[selectLoc]=tmp;
}
//反过来再来一遍
for（i=p->
i>
1;
i--）
//产生一个属于区间[0，i]的随机数selectLoc
selectLoc=1+（int）（i*rand（）/（RAND_MAX+1.0））;
顺序表中的元素已经重新随机排列!
//快速排序——划分函数
intPartition（intR[],intlow,inthigh）
//对记录子序列R[low...high]进行一趟快速排序，并返回枢轴记录所在位置
intpivotkey;
R[0]=R[low];
pivotkey=R[low];
while（low<
high）//从表的两端交替向中间扫描
while（low<
high&
&
R[high]>
=pivotkey）
--high;
if（low<
high）
R[low++]=R[high];
//将比枢轴记录小的记录移到低端
R[low]<
++low;
R[high--]=R[low];
//将比枢轴记录大的记录移到高端
R[low]=R[0];
returnlow;
//最后返回枢轴的位置（下标）
//快速排序——递归函数
voidQSort（intR[],ints,intt）
//对记录R[s...t]进行快速排序
intpivotloc;
if（s<
t）
pivotloc=Partition（R,s,t）;
//对R[s...t]进行一次划分，并返回枢轴的位置
QSort（R,s,pivotloc-1）;
QSort（R,pivotloc+1,t）;
/*快速排序的主调函数*/
voidquickSort（SeqList*p）
//对顺序表P进行快速排序
QSort（p->
s,1,p->
length）;
已采用快速排序算法成功排序!
//一趟希尔插入排序（实质为直接插入排序的变形）
voidshellInsert（SeqList*p,intdk）
inti,j;
for（i=dk+1;
=p->
++i）
if（p->
s[i]<
s[i-dk]）
s[0]=p->
//设置插入排序的“哨兵”
for（j=i-dk;
j>
0&
s[0]<
s[j];
j-=dk）
p->
s[j+dk]=p->
s[0];
/*希尔排序（缩小增量排序），假设增量设置为5，3，1*/
voidshellSort（SeqList*p,intdlta[],intt）
intk;
//按增量序列dlta[0..t-1]对顺序表中的元素作希尔排序
for（k=0;
k<
t;
k++）
shellInsert（p,dlta[k]）;
已采用希尔排序算法成功排序!
//堆排序——将p->
s[m..n]区间元素重新调整为堆的函数
voidheapAdjust（SeqList*p,intm,intn）
//使得p->
s[m...n]成为大堆
intj,rc;
rc=p->
s[m];
for（j=2*m;
j<
=n;
j*=2）
if（j<
n&
s[j]<
s[j+1]）
++j;
if（rc>
s[j]）break;
s[m]=p->
m=j;
s[m]=rc;
/*堆排序*/
voidheapSort（SeqList*p）
{
//对顺序表p进行堆排序
intrc,i;
length/2;
0;
--i）
heapAdjust（p,i,p->
rc=p->
s[1];
s[1]=p->
s[i]=rc;
heapAdjust（p,1,i-1）;
已采用堆排序算法成功排序!
//归并排序——合并有序表
//将有序的SR[1..m]和SR[m+1..n]归并为有序的TR[i..n]
voidMerge（intSR[],intTR[],inti,intm,intn）
//将有序的SR[i...m]和SR[m+1...n]归并为有序的TR[i...n]
intk,j;
for（j=m+1,k=i;
=m&
++k）//将SR中记录由小到大的并入TR
if（SR[i]<
=SR[j]）
TR[k]=SR[i++];
elseTR[k]=SR[j++];
}
while（i<
=m）TR[k++]=SR[i++];
//将剩余的SR[i...m]复制到TR
while（j<
=n）TR[k++]=SR[j++];
//将剩余的SR[j...n]复制到TR
//归并排序——递归函数部分
//将SR[]中的数据借助辅助空间TR2排序后存入TR1[]中。
voidMsort（intSR[],intTR2[],intTR1[],ints,intt）
//对SR[s...t]进行归并排序，排序后的记录存入TR1[s...t]
voidMsort2（intSR[],intTR1[],ints,intt）;
Msort2（SR,TR1,s,t）;
voidMsort2（intSR[],intTR1[],ints,intt）
intm;
int*TR3=（int*）malloc（（t+1）*sizeof（int））;
if（s==t）TR1[s]=SR[s];
else
m=（s+t）/2;
//将SR[s...t]平分为SR[s...m]和SR[m+1...t]
Msort2（SR,TR3,s,m）;
Msort2（SR,TR3,m+1,t）;
Merge（TR3,TR1,s,m,t）;
/*归并排序——主调函数*/
voidmergeSort（SeqList*p）
//开辟辅助空间
int*auxSpa=（int*）malloc（（p->
length+1）*sizeof（int））;
//调用递归函数作归并排序
Msort（p->
s,auxSpa,p->
s,1,p->
//释放辅助空间
free（auxSpa）;
已采用归并排序算法成功排序!
/*显示表中所有数据*/
voidshowAll（SeqList*p）
inti;
if（p->
length>
0）
当前表中的元素个数为%d，依次如下：
p->
printf（"
%d"
s[i]）;
当前顺序表为空!
voidmain（）
intchoice=-1;
SeqList*plist;
intincArr[]={5,3,1};
//将希尔排序的增量设置为5，3，1
plist=init（）;
while
（1）
menu（）;
fflush（stdin）;
\t请选择一个菜单项：
"
scanf（"
choice）;
switch（choice）
case1:
//随机产生一组整数放入表中
randGen（plist）;
showAll（plist）;
break;
case2:
//手动输入一批整数放入表中
manInput（plist）;
case3:
//将现有表中数据随机化排列
randomizeList（plist）;
case4:
//快速排序
quickSort（plist）;
case5:
//希尔排序（增量为3个，依次为5，3，1）
shellSort（plist,incArr,3）;
case6:
//堆排序
heapSort（plist）;
case7:
//归并排序
mergeSort（plist）;
case8:
//按顺序显示表中所有数据
case0:
exit（0）;
default:
\t您输入的菜单项不存在，请重新选择!
choice=-1;
//表示未选择菜单项或者菜单项选择错误
升级会员 