内部排序算法比较word文档良心出品Word下载.docx
《内部排序算法比较word文档良心出品Word下载.docx》由会员分享，可在线阅读，更多相关《内部排序算法比较word文档良心出品Word下载.docx（17页珍藏版）》请在冰点文库上搜索。
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.数据类型定义
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;
i<
n+1;
i++）
a:
{
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"
stdio.h"
stdlib.h"
string.h"
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为记录关键字比较和移动的次数
voidaddlist（SqList&
L）//初始化顺序表
printf（"
请输入你要输入的个数:
"
）;
scanf（"
%d"
&
n）;
if（n>
50000）
{
超出范围重新输入!
!
\n"
L.elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType））;
if（!
L.elem）exit（0）;
}
L）//随机数产生程序
}//使输入相同个数时每次产生的随机数不同
voidmemory（SqList&
L）//记录L，使每个排序算法都用一组相同的随机数
{
M.length=0;
for（inti=1;
{M.elem[i].key=L.elem[i].key;
++M.length;
voidBubbleSort（SqList&
L）//冒泡排序
inti,j;
for（i=1;
L.length;
{for（j=1;
j<
L.length-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）//直接插入排序
for（i=2;
=L.length;
if（L.elem[i].key<
L.elem[i-1].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--;
voidSelectSort（SqList&
L）//选择排序
inti,j,k;
k=i;
for（j=i+1;
bj3++;
if（L.elem[j].key<
L.elem[k].key）k=j;
if（i!
=k）
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）
while（low<
high&
&
L.elem[high].key>
=pivotkey）
--high;
L.elem[low]=L.elem[high];
bj4++;
L.elem[low].key<
++low;
L.elem[high]=L.elem[low];
L.elem[low]=L.elem[0];
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作快速排序
QSort（L,1,L.length）;
voidShellSort（SqList&
L）//希尔排序
inti,d=L.length/2,j,w=0,k;
while（w<
d）
w=1;
for（i=w;
i=i+d）
for（j=i+d;
j=j+d）
k=j;
bj5++;
yd5+=3;
w++;
d=d/2;
voidHeapAdjust（SqList&
L,ints,intm）
{//调整L.elem[s]的关键字，使L.elem[s…..m]成为一个大根堆
SqListrc;
rc.elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType））;
rc.elem）exit（0）;
intj;
rc.elem[0]=L.elem[s];
for（j=2*s;
=m;
j*=2）
{bj6++;
if（j<
m&
L.elem[j].key<
++j;
bj6++;
（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进行堆排序
inti;
for（i=L.length/2;
i>
0;
--i）
HeapAdjust（L,i,L.length）;
for（i=L.length;
1;
{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））;
M.elem）exit（0）;
cout<
<
---------------------------------内部排序算法比较-----------------------------\n"
;
cout<
************************************欢迎使用***********************************\n"
**********************************
（1）运行程序**********************************\n"
**********************************
（2）退出系统**********************************\n"
endl;
请选择:
a）;
switch（a）
case1:
system（"
cls"
addlist（L）;
break;
case2:
谢谢使用"
exit（0）;
random（L）;
memory（M,L）;
BubbleSort（M）;
InsertSort（M）;
SelectSort（M）;
QuickSort（M）;
ShellSort（M）;
HeapSort（L）;
*********比较次数**********移动次数*********\n"
冒泡排序：
"
bj1<
yd1<
直接插入：
bj2<
yd2<
简单选择:
bj3<
yd3<
快速排序:
bj4<
yd4<
希尔排序:
bj5<
yd5<
堆排序:
bj6<
yd6<
}七．用户手册
（1）本程序执行文件为“内部排序算法比较.exe”。
（2）采用伪随机数程序产生随机数作为排序的数据。
（3）用户只需按提示选择程序功能，并输入随机数个数即可得到结果，而且可以选择继续运行程序或者退出程序。
升级会员 