内部排序算法比较.docx
《内部排序算法比较.docx》由会员分享，可在线阅读，更多相关《内部排序算法比较.docx（18页珍藏版）》请在冰点文库上搜索。
内部排序算法比较
内部排序算法比较
班级：
姓名：
学号：
完成日期：
题目：
试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。
一．需求分析
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;i{for（j=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+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{
bj3++;
if（L.elem[j].key}
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{
yd4++;
while（low=pivotkey）
--high;
L.elem[low]=L.elem[high];
bj4++;
yd4++;
while（low++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{
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{
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（j++j;
bj6++;
if（!
（rc.elem[0].keyL.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<<"简单选择:
"<cout<<"快速排序:
"<cout<<"希尔排序:
"<cout<<"堆排序:
"<cout<gotoa;
}七．用户手册
（1）本程序执行文件为“内部排序算法比较.exe”。
（2）采用伪随机数程序产生随机数作为排序的数据。
（3）用户只需按提示选择程序功能，并输入随机数个数即可得到结果，而且可以选择继续运行程序或者退出程序。
升级会员 