内部排序算法实现与性能分析课程设计综述.docx
《内部排序算法实现与性能分析课程设计综述.docx》由会员分享，可在线阅读，更多相关《内部排序算法实现与性能分析课程设计综述.docx（18页珍藏版）》请在冰点文库上搜索。
内部排序算法实现与性能分析课程设计综述
1、问题描述：
1.1题目内容:
内部排序算法实现与性能分析
1.2基本要求:
（1）数据结构定义
（2）利用随机函数产生30000个随机整数，利用插入排序、起泡排序、选择排序、快速排序、希尔等排序方法进行排序，并统计每一种排序上机所花费的时间,对各种排序算法做分析比较.
1.3测试数据:
由函数随机产生的数据，由于是随机产生的，所以在此不一一写出。
2、需求分析：
2.1程序的基本功能:
输入30000个随机整数，对这些数进行多种方法进行排序，并对这些排序做比较，在屏幕上输出每种排序方法所比较的次数，交换的次数，和时间复杂度。
2.2输入值、输出值以及输入输出形式:
由于程序中所需的数据都是有函数随机生成的整形数，不需要用户自己输入，用户只需要对演示程序中的一些提示做一些必要的选择以便于程序的执行。
程序输出的是对六种排序做的一些比较，即输出六种排序各排序过程中所比较的数据的个数，交换的数据的次数，和排序完成所用的时间。
六种排序依次在计算机终端上显示，便于用户观察。
2.3各个模块的功能要求：
一、随机函数：
产生随机数
二、选择排序函数：
对随机数进行选择排序
三、起泡排序函数：
对随机数进行气泡排序
四、直接插入函数：
对随机数进行直接插入排序
五、希尔排序函数：
对随机数进行希尔排序
六、快速排序函数：
对随机数进行快速排序
七、主函数
3、概要设计：
3.1所需的ADT，每个程序中使用的存储结构设计说明
typedefstruct
{
intkey;
}ElemType;//元素类型
typedefstruct
{
ElemType*elem;
intlength;
}SqList;//顺序表类型
3.2主程序流程以及模块调用关系
3.3每个模块的算法设计说明（流程图）
3.3.1气泡排序：
3.3.2直插排序
3.3.3选择排序
3.3.4希尔排序
3.3.5快速排序
4、详细设计：
4.1函数调用关系图
5、各个算法实现的源程序：
5.1、冒泡排序及其主要算法
voidqipao（SqList&L）//起泡
{
start_t=clock（）;
inti=1,j;
while（i{
for（j=1;j{
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;
}
}
i++;
}
5.2、直接插入排序及其主要算法
voidInsertSort（SqList&L）//直接插入
{
start_t=clock（）;
inti,j;
for（i=2;i<=L.length;i++）
{
if（L.elem[i].key<=L.elem[i-1].key）//“<”，需将L.r[i]插入有序子序列
{
L.elem[0].key=L.elem[i].key;//复制为哨兵
j=i-1;
while（L.elem[0].key{
L.elem[j+1].key=L.elem[j].key;//记录后移
j--;
}
L.elem[j+1].key=L.elem[0].key;//插入到正确位置
}
}
5.3、选择排序及其主要算法
voidSelectSort（SqList&L）//选择
{
inti,j,k,;
for（i=1;i{
for（j=i+1;j{
if（L.elem[j].key<=L.elem[k].key）
{
L.elem[0].key=L.elem[i].key;
L.elem[i].key=L.elem[k].key;
L.elem[k].key=L.elem[0].key;//与第i个记录交换
}
}
5.4、希尔排序及其主要算法
voidxier（SqList&L）//希尔排序并打印结果
{
start_t=clock（）;
inti,d=L.length/2,j,w=0,k,yd=0,bj=0;//间长为d
while（w{
for（i=1;i<=L.length;i++）//第i个与第i+d个相比较
{
j=i+d;
if（j<=L.length）
{if（L.elem[i].key>L.elem[j].key）
{
k=j;
bj++;
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;
}
}
}
}
d=d/2;//间隔变为原来的一半
}
5.5、快速排序及其主要算法
intPartition（SqList&L,intlow,inthigh）//快速排序
{
intpivotkey;
L.elem[0]=L.elem[low];
yd1++;
pivotkey=L.elem[low].key;//用子表的第一个记录作曲轴记录
while（low{
yd1++;
while（low=pivotkey）
--high;
L.elem[low]=L.elem[high];//将比轴记录小的记录交换到低端
while（lowL.elem[high]=L.elem[low];//将比轴记录大的记录交换到高端
}
L.elem[low]=L.elem[0];
returnlow;//返回曲轴所在位置
}
voidQSort（SqList&L,intlow,inthigh）
{//对顺序表L.r[low..high]做快速排序
intpivotloc;
inti=1;
if（low{
pivotloc=Partition（L,low,high）;//将L.r[low..high]一分为二
QSort（L,low,pivotloc-1）;//对低字表递归排序
QSort（L,pivotloc+1,high）;//对高字表递归排序
}
}
voidQuickSort（SqList&L）
{//对顺序表L做快速排序
intj;
BeforeSort（）;
QSort（L,1,L.length）;
for（j=1;j<=L.length;j++）
printf（"%d",L.elem[j]）;
display（yd1,bj1）;
}
6、调试分析：
1．产生随机数
2.排序
3.汇总
7、使用说明：
本演示程序对以下5种常用的内部排序算法进行实测比较：
起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序。
由系统生成30000个随机整数进行比较。
程序还可以考虑几组数据的典型性，如：
正序、逆序和不同程度的乱序。
注意采用分块调试的方法。
在该程序中可能回有很多让人不满意的地方，我会在以后的学习中逐加改进的。
8、测试结果：
9.主要参考文献
1．严蔚敏，吴伟民．数据结构（C语言版）．北京：
清华大学出版社，1997
2．朱战立．数据结构．西安：
西安电子科技大学出版社,2004
3．严蔚敏，吴伟民．数据结构题集（C语言版）．北京：
清华大学出版社,2000
升级会员 