内部排序算法比较.docx
《内部排序算法比较.docx》由会员分享,可在线阅读,更多相关《内部排序算法比较.docx(19页珍藏版)》请在冰点文库上搜索。
内部排序算法比较
内部排序算法比较
班级:
姓名:
学号:
完成日期:
题目:
试通过随机数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。
一.需求分析
1.对常用的6种内部排序算法进行比较:
冒泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序.
2.待排序表的表长不小于100;其中的数据要用伪随机数产生程序产生;至少要用5组不同的输入数据作比较;比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换计为3次移动)
3.最后要对结果作出简单分析,包括对各组数据得到结果波动大小的解释.
二.概要设计
1.主界面设计
对六种内部排序算法进行比较,可通过随机数程序产生几组数,要求用户手动输入产生随机数的个数。
运行界面如图所示:
选择1运行程序,选择2退出程序
2.存储结构设计
本程序采用顺序表结构,具体结构定义如下:
typedefstruct
{
intkey;
}ElemType;
typedefstruct
{
ElemType*elem;
intlength;
}SqList;
3。
系统功能设计
1)分配内存空间。
创建顺序表
2)利用伪随机数产生程序产生随机数,作为程序运行的数据
3)实现每种排序算法的功能函数
三.模块设计
1。
模块设计
2.系统子程序及功能设计
本系统共设置13个函数,其中包括主函数。
各函数名及功能说明如下。
1)voidaddlist(SqList&L)//建立个空顺序表
2)voidrandom(SqList&L)//随机数产生函数
3)voidmemory(SqList&M,SqList&L)//记录L,以保证每个排序函数使用一组随机数
4)voidBubbleSort(SqList&L)//冒泡排序
5)voidInsertSort(SqList&L)//直接插入排序
6)voidSelectSort(SqList&L)//选择排序
7)intPartition(SqList&L,intlow,inthigh)//返回快速排序枢轴的位置
8)voidQSort(SqList&L,intlow,inthigh)//对子序列作快速排序
9)voidQuickSort(SqList&L)//对数序表作快速排序
10)voidShellSort(SqList&L)//希尔排序
11)voidHeapAdjust(SqList&L,ints,intm)//堆排序算法子程序
12)voidHeapSort(SqList&L)//对顺序表进行堆排序
13)voidmain()//主函数,调用各模块函数
3。
函数主要调用关系
四.详细设计
1.数据类型定义
typedefstruct
{
intkey;
}ElemType;
typedefstruct
{
ElemType*elem;
intlength;
}SqList;
2。
全局变量定义
intbj1=0,yd1=0,bj2=0,yd2=0,bj3=0,yd3=0,bj4=0,yd4=0,bj5=0,yd5=0,bj6=0,yd6=0;//记录每种算法的比较,移动次数
intn;//随机数的个数
2。
系统主要子程序详细设计
(1)主函数设计模块
主要是输入数据,以及程序界面的设计,调用系统的各个子程序,并输出结果。
(详见源程序)
(2)随机数产生模块
利用伪随机数产生程序产生数据,并存储到顺序表中。
voidrandom(SqList&L)
{
L.length=0;
staticboolfirst=true;
if(first)
{
srand(time(0));
first=false;
}//使每次产生的随机数不同
for(inti=1;ia:
{
L。
elem[i]。
key=rand();
if(L.elem[i].key〉30000)
gotoa;
++L。
length;
}
(3)排序算法模块
实现冒泡排序,直接插入排序,简单选择排序,快速排序,希尔排序以及堆排序的算法.(祥见源程序)
五.测试分析
运行程序后,得到如图所示:
输入:
1
输入:
100
选择1重复上述步骤,输入150,200,250,300得到另外四个结果:
退出程序,请选择:
2
结果分析:
冒泡排序,直接插入排序以及简单选择排序比较次数较多,快速排序,希尔排序及堆排序比较次数较少;并可得冒泡排序和直接插入排序相对较稳定,其他四种内部排序为不稳定排序.
六.源程序清单
#include"iostream"
#include"stdio.h”
#include”stdlib。
h”
#include”string。
h”
#include"time。
h”
usingnamespacestd;
#defineLIST_INIT_SIZE50000
intbj1=0,yd1=0,bj2=0,yd2=0,bj3=0,yd3=0,bj4=0,yd4=0,bj5=0,yd5=0,bj6=0,yd6=0,n;//yd,bj为记录关键字比较和移动的次数
typedefstruct
{
intkey;
}ElemType;
typedefstruct
{
ElemType*elem;
intlength;
}SqList;
voidaddlist(SqList&L)//初始化顺序表
{
a:
printf("请输入你要输入的个数:
");
scanf(”%d",&n);
if(n>50000)
{
printf(”超出范围重新输入!
!
!
\n”);
gotoa;
}
L。
elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!
L.elem)exit(0);
}
voidrandom(SqList&L)//随机数产生程序
{
L.length=0;
staticboolfirst=true;
if(first)
{
srand(time(0));
first=false;
}//使输入相同个数时每次产生的随机数不同
for(inti=1;ia:
{
L。
elem[i].key=rand();
if(L.elem[i]。
key>30000)
gotoa;
++L。
length;
}
}
voidmemory(SqList&M,SqList&L)//记录L,使每个排序算法都用一组相同的随机数
{
M。
length=0;
for(inti=1;i{M。
elem[i].key=L.elem[i]。
key;
++M.length;
}
}
voidBubbleSort(SqList&L)//冒泡排序
{
inti,j;
for(i=1;ilength;i++)
{for(j=1;jlength—i+1;j++)
{bj1++;
if(L.elem[j]。
key〉L.elem[j+1]。
key)
{
L.elem[0]。
key=L.elem[j].key;
L。
elem[j]。
key=L.elem[j+1]。
key;
L.elem[j+1].key=L。
elem[0].key;
yd1+=3;
}
}
}
}
voidInsertSort(SqList&L)//直接插入排序
{
inti,j;
for(i=2;i<=L。
length;i++)
{
if(L。
elem[i].key{
L。
elem[0]。
key=L.elem[i].key;
yd2++;
j=i-1;
bj2++;
while(L.elem[0].key〈L。
elem[j]。
key)
{
L.elem[j+1].key=L.elem[j].key;
j-—;
yd2++;
bj2++;
}
L。
elem[j+1].key=L。
elem[0]。
key;
yd2++;
}
}
}
voidSelectSort(SqList&L)//选择排序
{
inti,j,k;
for(i=1;i{
k=i;
for(j=i+1;j〈L。
length;j++)
{
bj3++;
if(L。
elem[j]。
keyelem[k].key)k=j;
}
if(i!
=k)
{
L.elem[0]。
key=L.elem[i].key;
L。
elem[i].key=L.elem[k]。
key;
L。
elem[k].key=L。
elem[0].key;
yd3+=3;
}
}
}
intPartition(SqList&L,intlow,inthigh)//快速排序
{
intpivotkey;
L.elem[0]=L.elem[low];
yd4++;
pivotkey=L。
elem[low]。
key;
while(low〈high)
{
yd4++;
while(low〈high&&L.elem[high]。
key〉=pivotkey)
--high;
L.elem[low]=L.elem[high];
bj4++;
yd4++;
while(low〈high&&L.elem[low].key〈=pivotkey)
++low;
L.elem[high]=L。
elem[low];
bj4++;
yd4++;
}
L。
elem[low]=L。
elem[0];
yd4++;
returnlow;
}
voidQSort(SqList&L,intlow,inthigh)
{//对顺序表的子序列作快速排序
intpivotloc;
if(low〈high)
{
pivotloc=Partition(L,low,high);
QSort(L,low,pivotloc—1);
QSort(L,pivotloc+1,high);
}
}
voidQuickSort(SqList&L)
{//对顺序表L作快速排序
QSort(L,1,L.length);
}
voidShellSort(SqList&L)//希尔排序
{
inti,d=L.length/2,j,w=0,k;
while(w{
w=1;
for(i=w;i〈L.length;i=i+d)
{
k=i;
for(j=i+d;j{
if(L。
elem[i]。
key〉L。
elem[j].key)
{
k=j;
bj5++;
}
}
if(i!
=k)
{
L。
elem[0]。
key=L。
elem[i]。
key;
L.elem[i].key=L.elem[k]。
key;
L.elem[k]。
key=L。
elem[0]。
key;
yd5+=3;
}
w++;
}
d=d/2;
w=1;
}
}
voidHeapAdjust(SqList&L,ints,intm)
{//调整L。
elem[s]的关键字,使L.elem[s…。
。
m]成为一个大根堆
SqListrc;
rc。
elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!
rc。
elem)exit(0);
intj;
rc.elem[0]=L.elem[s];
for(j=2*s;j<=m;j*=2)
{bj6++;
if(jkey〈L。
elem[j+1]。
key)
++j;
bj6++;
if(!
(rc。
elem[0].key〈L。
elem[j].key))break;
L.elem[s]=L.elem[j];
s=j;
yd6+=3;
}
L.elem[s]=rc。
elem[0];
}
voidHeapSort(SqList&L)
{//对顺序表L进行堆排序
inti;
for(i=L。
length/2;i〉0;—-i)
HeapAdjust(L,i,L.length);
for(i=L.length;i〉1;—-i)
{L。
elem[1]=L.elem[i];
yd6+=3;
HeapAdjust(L,1,i-1);
}
}
voidmain()
{
SqListL,M;
inta;
M。
elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!
M.elem)exit(0);
a:
cout<〈"—---——--—--—--——-—-—--—--—---——--内部排序算法比较——-——-—----—-—---——-——-—--—-—\n";cout<<"************************************欢迎使用***********************************\n”;
cout〈〈"**********************************
(1)运行程序**********************************\n";
cout<〈”**********************************
(2)退出系统**********************************\n”;
cout〈cout<<"请选择:
";
scanf(”%d",&a);
switch(a)
{
case1:
system(”cls”);addlist(L);break;
case2:
cout〈<”谢谢使用";exit(0);break;
}
random(L);
memory(M,L);
BubbleSort(M);
memory(M,L);
InsertSort(M);
memory(M,L);
SelectSort(M);
memory(M,L);
QuickSort(M);
memory(M,L);
ShellSort(M);
memory(M,L);
HeapSort(L);
cout〈<"*********比较次数**********移动次数*********\n";
cout<〈"冒泡排序:
”<cout<<”直接插入:
”〈cout〈<”简单选择:
”〈〈bj3<<”"〈cout<〈"快速排序:
"〈cout<〈"希尔排序:
”<cout<<”堆排序:
”<〈bj6〈〈"”<cout<gotoa;
}七.用户手册
(1)本程序执行文件为“内部排序算法比较。
exe”。
(2)采用伪随机数程序产生随机数作为排序的数据.
(3)用户只需按提示选择程序功能,并输入随机数个数即可得到结果,而且可以选择继续运行程序或者退出程序。