实验10排序子系统.docx
《实验10排序子系统.docx》由会员分享,可在线阅读,更多相关《实验10排序子系统.docx(29页珍藏版)》请在冰点文库上搜索。
实验10排序子系统
验证性实验10:
排序子系统
班级:
H1001学号:
09姓名:
陆俊实验日期:
2011.12.7
1.实验目的
(1)掌握常用排序方法的基本思想。
(2)通过实验加深理解各种排序算法。
(3)通过实验掌握各种排序方法的时间复杂度分析。
(4)了解各种排序方法的优缺点及适用范围。
2.实验内容
(1)编写直接插入排序程序。
(2)编写希尔排序程序。
(3)编写冒泡排序程序。
(4)编写快速排序程序。
(5)编写选择排序程序。
(6)编写归并排序程序。
(7)编写堆排序程序。
(8)程序执行时,要求能显示每一趟的排序结果。
(9)设计一个选择式菜单,以菜单方式选择上述排序程序。
排序子系统
***************************************************
*1------------更新排序数据*
*2------------直接插入排序*
*3------------希尔排序*
*4------------冒泡排序*
*5------------快速排序*
*6------------选择排序*
*7------------归并排序*
*8------------堆排序*
*0------------返回*
***************************************************
请选择菜单号(0--8):
3.实验程序
#include
#include
#include
#defineL8
#defineFALSE0
#defineTURE1
typedefstruct
{
intkey;
charotherinfo;
}RecType;
typedefRecTypeSeqlist[L+1];
intnum;
SeqlistR;
voidInsertsort();
voidBubblesort();
voidQuickSort(intlow,inthigh);
voidShellsort();
voidSelectsort();
voidMergesort();
intPartition(inti,intj);
voidHeap();
voidmain()
{
SeqlistS;
inti,k;
charch1,ch2,q;
printf("\n\t请输入%d个待排序数据(按【Enter】键分隔):
\n\t",L);
for(i=1;i<=L;i++)
{
scanf("%d",&S[i].key);
getchar();
printf("\t");
}
printf("\n\t排序数据已经输入完毕!
");
ch1='y';
while(ch1=='y'||ch1=='Y')
{
printf("\n");
printf("\n\t\t排序子系统");
printf("\n\t\t***************************************************");
printf("\n\t\t*1------------更新排序数据*");
printf("\n\t\t*2------------直接插入排序*");
printf("\n\t\t*3------------希尔排序*");
printf("\n\t\t*4------------冒泡排序*");
printf("\n\t\t*5------------快速排序*");
printf("\n\t\t*6------------选择排序*");
printf("\n\t\t*7------------归并排序*");
printf("\n\t\t*8------------堆排序*");
printf("\n\t\t*0------------返回*");
printf("\n\t\t***************************************************");
printf("\n\t\t请选择菜单号(0--8):
");
scanf("%c",&ch2);
getchar();
for(i=1;i<=L;i++)
R[i].key=S[i].key;
switch(ch2)
{
case'1':
printf("\n\t请输入%d个待排序数据(按【Enter】键分隔):
\n\t",L);
for(i=1;i<=L;i++)
{
scanf("%d",&S[i].key);
getchar();
printf("\t");
}
printf("\n\t排序数据已经输入完毕!
");
break;
case'2':
Insertsort();break;
case'3':
Shellsort();break;
case'4':
Bubblesort();break;
case'5':
printf("\n\t原始数据为(按【Enter】键开始排序):
");
for(k=1;k<=L;k++)
printf("%5d",R[k].key);
getchar();
printf("\n");
num=0;
QuickSort(1,L);
printf("\n\t排序的最终结果是:
");
for(k=1;k<=L;k++)
printf("%5d",R[k].key);
printf("\n");break;
case'6':
Selectsort();break;
case'7':
Mergesort();break;
case'8':
Heap();break;
case'0':
ch1='n';break;
default:
printf("\n\t输入出错!
");
}
if(ch2!
='0')
{
if(ch2=='2'||ch2=='3'||ch2=='4'||ch2=='5'||ch2=='6'||ch2=='7'||ch2=='8')
printf("\n\t排序输出完毕!
");
printf("\n\n\t按回车键返回。
");
q=getchar();
if(q!
='\xA')
{
getchar();
ch1='n';
}
}
}
}
voidInsertsort()
{
inti,j,k,m=0;
printf("\n\t原始数据为(按【Enter】键开始排序):
");
for(k=1;k<=L;k++)
printf("%5d",R[k].key);
getchar();
printf("\n");
for(i=2;i<=L;i++)
{
if(R[i].key{
R[0]=R[i];j=i-1;
while(R[0].key{
R[j+1]=R[j];
j--;
}
R[j+1]=R[0];
}
m++;
printf("\t第%d趟排序结果为(按【Enter】键继续):
",m);
for(k=1;k<=L;k++)
printf("%5d",R[k].key);
getchar();
printf("\n");
}
printf("\n\t排序的最终结果是:
");
for(i=1;i<=L;i++)
printf("%5d",R[i].key);
printf("\n");
}
voidShellsort()
{
inti,j,gap,x,m=0,k;
printf("\n\t原始数据为(按【Enter】键开始排序):
");
for(k=1;k<=L;k++)
printf("%5d",R[k].key);
getchar();
printf("\n");
gap=L/2;
while(gap>0)
{
for(i=gap+1;i<=L;i++)
{
j=i-gap;
while(j>0)
{
if(R[j].key>R[j+gap].key)
{
x=R[j].key;R[j].key=R[j+gap].key;
R[j+gap].key=x;
j=j-gap;
}
else
j=0;
}
}
gap=gap/2;
m++;
printf("\t第%d趟排序结果为(按【Enter】键继续):
",m);
for(k=1;k<=L;k++)
printf("%5d",R[k].key);
getchar();
printf("\n");
}
printf("\n\t排序的最终结果是:
");
for(i=1;i<=L;i++)
printf("%5d",R[i].key);
printf("\n");
}
voidBubblesort()
{
inti,j,k;
intexchange;
printf("\n\t原始数据为(按【Enter】键开始排序):
");
for(k=1;k<=L;k++)
printf("%5d",R[k].key);
getchar();
printf("\n");
for(i=1;i<=L;i++)
{
exchange=FALSE;
for(j=L;j>=i+1;j--)
if(R[j].key{
R[0].key=R[j].key;
R[j].key=R[j-1].key;
R[j-1].key=R[0].key;
exchange=TURE;
}
if(exchange)
{
printf("\t第%d趟排序结果为(按【Enter】键继续):
",i);
for(k=1;k<=L;k++)
printf("%5d",R[k].key);
getchar();
printf("\n");
}
}
printf("\n\t排序的最终结果是:
");
for(i=1;i<=L;i++)
printf("%5d",R[i].key);
printf("\n");
}
intPartition(inti,intj)
{
RecTypepirot=R[i];
while(i{
while(i=pirot.key)
j--;
if(iR[i++]=R[j];
while(ii++;
if(iR[j--]=R[i];
}
R[i]=pirot;
returni;
}
voidQuickSort(intlow,inthigh)
{
intpirotpos,k;
if(low{
pirotpos=Partition(low,high);
num++;
printf("\t第%d趟排序结果为(按【Enter】键继续):
",num);
for(k=1;k<=L;k++)
printf("%5d",R[k].key);
getchar();
printf("\n");
QuickSort(low,pirotpos-1);
QuickSort(pirotpos+1,high);
}
}
voidSelectsort()
{
inti,j,k,h;
printf("\n\t原始数据为(按【Enter】键开始排序):
");
for(k=1;k<=L;k++)
printf("%5d",R[k].key);
getchar();
printf("\n");
for(i=1;i<=L;i++)
{
h=i;
for(j=i+1;j<=L;j++)
if(R[j].keyh=j;
if(h!
=j)
{
R[0]=R[i];
R[i]=R[h];
R[h]=R[0];
}
printf("\t第%d趟排序结果为(按【Enter】键继续):
",i);
for(k=1;k<=L;k++)
printf("%5d",R[k].key);
getchar();
printf("\n");
}
printf("\n\t排序的最终结果是:
");
for(i=1;i<=L;i++)
printf("%5d",R[i].key);
printf("\n");
}
voidMerge(intlow,intmm,inthigh)
{
inti=low,j=mm+1,p=0;
RecType*R1;
R1=newRecType[high-low+1];
if(!
R1)
printf("\n\t内存容量不够!
");
while(iR1[p++]=(R[i].key<=R[j].key)?
R[i++]:
R[j++];
while(i<=mm)
R1[p++]=R[i++];
while(i<=high)
R1[p++]=R[j++];
for(p=0,i=low;i<=high;p++,i++)
R[i]=R1[p];
}
voidMergePass(intlength)
{
inti;
for(i=1;i+2*length-1<=L;i=i+2*length)
Merge(i,i+length-1,i+2*length-1);
if(i+length-1Merge(i,i+length-1,L);
}
voidMergesort()
{
intlength,k,m=0;
printf("\n\t原始数据为(按【Enter】键开始排序):
");
for(k=1;k<=L;k++)
printf("%5d",R[k].key);
getchar();
printf("\n");
for(length=1;length{
MergePass(length);
m++;
printf("\t第%d趟排序结果为(按【Enter】键继续):
",m);
for(k=1;k<=L;k++)
printf("%5d",R[k].key);
getchar();
printf("\n");
}
printf("\n\t排序的最终结果是:
");
for(k=1;k<=L;k++)
printf("%5d",R[k].key);
printf("\n");
}
voidCreateHeap(introot,intindex)
{
intj,temp,finish;
j=2*root;
temp=R[root].key;
finish=0;
while(j<=index&&finish==0)
{
if(jif(R[j].keyj++;
if(temp>=R[j].key)
finish=1;
else
{
R[j/2].key=R[j].key;
j=j*2;
}
}
R[j/2].key=temp;
}
voidHeapSort()
{
inti,j,temp,k;
for(i=(L/2);i>=1;i--)
CreateHeap(i,L);
for(i=L-1,k=1;i>=1;i--,k++)
{
temp=R[i+1].key;
R[i+1].key=R[1].key;
R[1].key=temp;
CreateHeap(1,i);
printf("\t第%d趟排序结果为(按【Enter】键继续):
",k);
for(j=1;j<=L;j++)
printf("%5d",R[j].key);
getchar();
printf("\n");
}
}
voidHeap()
{
inti;
printf("\n\t原始数据为(按【Enter】键开始排序):
");
for(i=1;i<=L;i++)
printf("%5d",R[i].key);
printf("\n\t");
getchar();
HeapSort();
printf("\n\t排序的最终结果是:
");
for(i=1;i<=L;i++)
printf("%5d",R[i].key);
printf("\n");
}
4.程序运行
5.实验小结
这次试验,我也和以前一样把代码打完运行之后运行找错,结果又有错误了,两个地方漏了“;”,一运行就提示我错误信息,在我改正之后才能够顺利运行程序代码。
这次试验,我也遇到了很奇怪的问题,菜单中的第七个选项无法运行,以选择“7”就会弹出一个框框,让我“调试程序”活着“退出程序”的错误提示。
所以就直接关了后重新运行了一次,重新运行后就没有去选择7,其他的试过,能很好地给出我要的结果。
我想,会不会是因为我的系统是Win7的关系,才会出现这种提示嘛!
?
就算不是也无所谓了,归并排序也不是我们要考试的,我们主要掌握直接插入排序、希尔排序和冒泡排序就行了老师说,我也就没多想什么。
这章主要讲的是排序,排序是将数据的任意序列,重新排列成一个按关键字有序排列的序列,整过过程全部在内存进行的排序称为内排序。