排序算法性能分析.doc

*******************
实践教学
*******************

兰州理工大学

计算机与通信学院

2011年春季学期

数据结构课程设计

题目：
专业班级：
姓名：
学号：
指导教师：
成绩：_____________________
目录

TOC\o"1-3"\u摘要 PAGEREF_Toc216233
前言 PAGEREF_Toc75714
正文 PAGEREF_Toc77325
1.采用类c语言定义相关的数据类型 PAGEREF_Toc39395
2.各模块的伪码算法 PAGEREF_Toc35385
3.函数的调用关系图 PAGEREF_Toc232946
4.调试分析 PAGEREF_Toc78707
a、调试中遇到的问题及对问题的解决方法 PAGEREF_Toc9337
b、算法的时间复杂度和空间复杂度 PAGEREF_Toc283377
5.源程序 PAGEREF_Toc86308
总结 PAGEREF_Toc124113
参考文献 PAGEREF_Toc3093114
致谢 PAGEREF_Toc1236615


摘要
排序是计算机程序设计中的一种重要操作。各种部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。

关键字：排序，性能分析。

前言
排序是计算机程序设计中的一种重要操作。它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。内部排序的方法很多，但是就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合在不同的环境下使用。如果按排序过程中依据的不同原则对内部排序方法进行分类，则大致可分为插入排序，交换排序，选择排序，归并排序和记数排序等五类。
这几种排序算法是在顺序存储结构上实现的，因此在排序过程中需要进行大量记录的移动。当记录很大时，时间耗费很大，此时可采用静态链表作存储结构。但是有的排序方法，无法实现表排序。在这种情况下可以进行地址排序，即另设一个地址向量指示相应记录。

正文
采用类c语言定义相关的数据类型
int整型，char字符型，
各模块的伪码算法
（1）插入排序伪码算法：
voidInsertSort(Splist&L){
for(i=2;i<=L.length;++i)
if(LT(L.r[i].key,L.r[i-1].key))／／“《”，须将Ｌ.r[i]插入有序子表
{L.r[0]=L.r[i];／／复制为哨兵
L.r[i]=L.r[i-1];
For(j)i-2;LT(L.r[0].key,L.r[j].key);--j)
L.r[j+1]=L.r[j];／／记录后移
L.r[j+1]=L.r[0];／／插入到正确位置
}
}//InsertSort
(2)希尔排序
voidshllInsert(Splist&L,intdk){
for(i=dk+1;i<=L.length;++i)
if(LT(L.r[i].key,L.r[i-dk].key)){
L.r[0]=L.r[i];／／暂存
for(j=i-dk;j>0&&LT(L.r0].key,L.r[j].key);j-=dk)
L.r[j+dk]=L.r[j];／／记录后移
L.r[j+dk]=L.r[0];}／／插入
}//shellsort
voidshllsort(Splist&L,intdata[],intt){
for(k=0;k<t;++k)
shllInsert(L,data[k]);
}//shellsort
（3）快速排序
intpart(sqlist&L,intlow,inthigh){
／／交换顺序表Ｌ中子表Ｌ。R[low..high]的记录，使枢轴记录到位，并返回其所在位
／／此时在它之前（后）的记录均不大（小）于它。
pivotkey=L.[Low].key;
while(loe<high){
While(low<high&&l.r[high].key>=pivotkey)--high;
L.r[lowL.r[high];
while(low<high&&l.r[low].key>=pivotkey)++low;
L.r[lowL.r[high];
}
returnlow
}//partition
(4)选择排序
voidselectsort(splist&L){
for(i=1;i<L.length;++i){
j=selectMinKey(L,i);
if(