实验报告3
实验名称:数据结构与软件设计实习
题目:内部排序算法比较
专业:生物信息学班级:01 姓名:学号:实验日期:2010.07.24
一、实验目的:
比较冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序;
二、实验要求:
待排序长度不小于100,数据可有随机函数产生,用五组不同输入数据做比较,比较的指标为关键字参加比较的次数和关键字移动的次数;
对结果做简单的分析,包括各组数据得出结果的解释;
设计程序用顺序存储。
三、实验内容
对各种内部排序算法的时间复杂度有一个比较直观的感受,包括关键字比较次数和关键字移动次数。
将排序算法进行合编在一起,可考虑用顺序执行各种排序算法来执行,最后输出所有结果。
四、实验编程结果或过程:
1. 数据定义
typedef struct { KeyType key; }RedType; typedef struct { RedType r[MAXSIZE+1]; int length;
}SqList;
2. 函数如下,代码详见文件“排序比较.cpp”int Create_Sq(SqList &L)
void Bubble_sort(SqList &L)//冒泡排序void InsertSort(SqList &L)//插入排序
void SelectSort(SqList &L) //简单选择排序int Partition(SqList &L,int low,int high) void QSort(SqList &L,int low,int high)//递归形式的快速排序算法
void QuickSort(SqList &L)
void ShellInsert(SqList &L,int dk)//希尔排序
void ShellSort(SqList &L,int dlta[ ])
3. 运行测试结果,运行结果无误,如下图语速个数为20
元素个数为100
错误调试无。
调试分析:
时间复杂度与空间复杂度:
理论分析可以得出各种排序算法的时间复杂度和空间复杂度,如下表所示(图6):
◆待排序的记录数目n 的大小。
◆记录本身数据量的大小,也就是记录中除关键字外的其他信息量的大小。
◆关键字的结构及其分布情况。
◆对排序稳定性的要求
从结果中还可看出:
对于一般的排序,比较次数多,而交换次数相对较少;而快速排序比较次数和交换次数都较少,两者相差不如前者大。其中冒泡排序比较和交换次数都很大。
五、实验总结:
(1)实验中的存在问题和提高
存在问题:程序有待增强。
提高:界面处理简洁。
(2)收获与体会
随机数的生成
附录源程序
#include
#include
#include
#include
#define LS(a,b) ((a)<(b))
#define LL(a,b) ((a)>(b))
#define MAXSIZE 10000
typedef int KeyType;
typedef struct {
KeyType key;
}RedType;
typedef struct {
RedType r[MAXSIZE+1];
int length;
}SqList;
int compare=0;
int change=0;
int Create_Sq(SqList &L)
{
int k;
cout<<"元素个数:";
cin>>k;
L.length=k;
srand(time(NULL));
for (int x=1; x<=k; x++)
{
L.r[x].key= rand() % k;//随机域为0~k }
return 1;
}
void Bubble_sort(SqList &L)//冒泡排序
for(i=1;i<=L.length-1;++i){
for(j=1;j<=k-1;++j){
++m;
if(LL(L.r[j].key,L.r[j+1].key)){
l=L.r[j].key;
L.r[j].key=L.r[j+1].key;
L.r[j+1].key=l;
++n;
}
}
--k;
}
cout< cout<<" "< cout< cout<<"冒泡排序的比较次数:"; cout< cout<<"冒泡排序的交换次数:"; cout< } void InsertSort(SqList &L)//插入排序 { int i,j,m=0,n=0; cout< for(i=2;i<=L.length;++i) if(LS(L.r[i].key,L.r[i-1].key)) { ++m; ++n; L.r[0]=L.r[i]; L.r[i]=L.r[i-1]; for(j=i-2;LS(L.r[0].key,L.r[j].key);--j) { ++m; L.r[j+1]=L.r[j]; } L.r[j+1]=L.r[0]; } cout<<"-----直接插入排序后的序列-----"< cout<<"直接插入排序的比较次数:"; cout< cout<<"直接插入排序的交换次数:"; cout< } void SelectSort(SqList &L) //简单选择排序{ int l,i,j,m=0,n=0; cout< for(i=1;i L.r[0]=L.r[i]; j=i+1; l=i; for(j;j<=L.length;++j){ ++m; if(LL(L.r[0].key,L.r[j].key)){ l=j; L.r[0]=L.r[j]; } } if(l!=i){ ++n; L.r[l]=L.r[i]; L.r[i]=L.r[0]; } } cout<<"-----简单选择排序后的序列-----"< cout<<" "< cout< cout<<"简单选择排序的比较次数:"; cout< cout<<"简单选择排序的交换次数:"; cout< } int Partition(SqList &L,int low,int high){ int pivotkey; L.r[0]=L.r[low]; pivotkey=L.r[low].key; while(low while(low --high; } while(low ++compare; ++low; } ++change; L.r[high]=L.r[low]; } L.r[low]=L.r[0]; return low; } void QSort(SqList &L,int low,int high)//递归形式的快速排序算法{ int pivotloc; if(low pivotloc=Partition(L,low,high); QSort(L,low,pivotloc-1); QSort(L,pivotloc+1,high); } } void QuickSort(SqList &L){ int i; QSort(L,1,L.length); cout<<"-----快速排序后的序列为-----"< for(i=1;i<=L.length;i++) cout<<" "< cout< cout<<"快速排序的比较次数:"; cout< cout<<"快速排序的交换次数:"; cout< compare=0; change=0; } void ShellInsert(SqList &L,int dk)//希尔排序 { int i; int j; for(i=dk+1;i<=L.length;++i) if(LS(L.r[i].key,L.r[i-dk].key)){ ++compare; L.r[0]=L.r[i]; for(j=i-dk;j>0&&LS(L.r[0].key,L.r[j].key);j-=dk){ ++compare; } L.r[j+dk]=L.r[0]; } } void ShellSort(SqList &L,int dlta[])//希尔排序{ int k,j=L.length/2,t=0; while(j>=0){ ++t; j-=2; } j=L.length/2; for(k=0;k { if(j==0) j=1;//定义最后一趟排序的增量 dlta[k]=j; j-=2; } for(k=0;k ShellInsert(L,dlta[k]); cout<<"-----希尔排序后的序列为-----"< cout<<" "< cout< cout<<"希尔排序的比较次数:"; cout< cout<<"希尔排序的交换次数:"; cout< compare=0; change=0; } void main(){ int i; int dlta[MAXSIZE]; SqList L,a,b,c,d; Create_Sq(L); a=b=c=d=L; Bubble_sort(L); InsertSort(a); SelectSort(b); QuickSort(c); ShellSort(d,dlta); } 《数据结构》实验报告排序实验题目: 输入十个数,从插入排序,快速排序,选择排序三类算法中各选一种编程实现。 实验所使用的数据结构内容及编程思路: 1. 插入排序:直接插入排序的基本操作是,将一个记录到已排好序的有序表中,从而得到一个新的,记录增一得有序表。 一般情况下,第i 趟直接插入排序的操作为:在含有i-1 个记录的有序子序列r[1..i-1 ]中插入一个记录r[i ]后,变成含有i 个记录的有序子序列r[1..i ];并且,和顺序查找类似,为了在查找插入位置的过程中避免数组下标出界,在r [0]处设置哨兵。在自i-1 起往前搜索的过程中,可以同时后移记录。整个排序过程为进行n-1 趟插入,即:先将序列中的第一个记录看成是一个有序的子序列,然后从第2 个记录起逐个进行插入,直至整个序列变成按关键字非递减有序序列为止。 2. 快速排序:基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。 假设待排序的序列为{L.r[s] ,L.r[s+1],…L.r[t]}, 首先任意选取一个记录 (通常可选第一个记录L.r[s])作为枢轴(或支点)(PiVOt ),然后按下述原则重新排列其余记录:将所有关键字较它小的记录都安置在它的位置之前,将所有关键字较大的记录都安置在它的位置之后。由此可以该“枢轴”记录最后所罗的位置i 作为界线,将序列{L.r[s] ,… ,L.r[t]} 分割成两个子序列{L.r[i+1],L.[i+2], …,L.r[t]}。这个过程称为一趟快速排序,或一次划分。 一趟快速排序的具体做法是:附设两个指针lOw 和high ,他们的初值分别为lOw 和high ,设枢轴记录的关键字为PiVOtkey ,则首先从high 所指位置起向前搜索找到第一个关键字小于PiVOtkey 的记录和枢轴记录互相交换,然后从lOw 所指位置起向后搜索,找到第一个关键字大于PiVOtkey 的记录和枢轴记录互相 交换,重复这两不直至low=high 为止。 具体实现上述算法是,每交换一对记录需进行3 次记录移动(赋值)的操作。而实际上, 数据结构与算法设计 实验报告 (2016 — 2017 学年第1 学期) 实验名称: 年级: 专业: 班级: 学号: 姓名: 指导教师: 成都信息工程大学通信工程学院 一、实验目的 验证各种简单的排序算法。在调试中体会排序过程。 二、实验要求 (1)从键盘读入一组无序数据,按输入顺序先创建一个线性表。 (2)用带菜单的主函数任意选择一种排序算法将该表进行递增排序,并显示出每一趟排序过程。 三、实验步骤 1、创建工程(附带截图说明) 2、根据算法编写程序(参见第六部分源代码) 3、编译 4、调试 四、实验结果图 图1-直接输入排序 图2-冒泡排序 图3-直接选择排序 五、心得体会 与哈希表的操作实验相比,本次实验遇到的问题较大。由于此次实验中设计了三种排序方法导致我在设计算法时混淆了一些概念,设计思路特别混乱。虽然在理清思路后成功解决了直接输入和直接选择两种算法,但冒泡 排序的算法仍未设计成功。虽然在老师和同学的帮助下完成了冒泡排序的算法,但还需要多练习这方面的习题,平时也应多思考这方面的问题。而且,在直接输入和直接选择的算法设计上也有较为复杂的地方,对照书本做了精简纠正。 本次实验让我发现自己在算法设计上存在一些思虑不周的地方,思考问题过于片面,逻辑思维能力太过单薄,还需要继续练习。 六、源代码 要求:粘贴个人代码,以便检查。 #include 实验七查找、排序的应用 一、实验目的 1、本实验可以使学生更进一步巩固各种查找和排序的基本知识。 2、学会比较各种排序与查找算法的优劣。 3、学会针对所给问题选用最适合的算法。 4、掌握利用常用的排序与选择算法的思想来解决一般问题的方法和技巧。 二、实验内容 [问题描述] 对学生的基本信息进行管理。 [基本要求] 设计一个学生信息管理系统,学生对象至少要包含:学号、姓名、性别、成绩1、成绩2、总成绩等信息。要求实现以下功能:1.总成绩要求自动计算; 2.查询:分别给定学生学号、姓名、性别,能够查找到学生的基本信息(要求至少用两种查找算法实现); 3.排序:分别按学生的学号、成绩1、成绩2、总成绩进行排序(要求至少用两种排序算法实现)。 [测试数据] 由学生依据软件工程的测试技术自己确定。 三、实验前的准备工作 1、掌握哈希表的定义,哈希函数的构造方法。 2、掌握一些常用的查找方法。 1、掌握几种常用的排序方法。 2、掌握直接排序方法。 四、实验报告要求 1、实验报告要按照实验报告格式规范书写。 2、实验上要写出多批测试数据的运行结果。 3、结合运行结果,对程序进行分析。 五、算法设计 a、折半查找 设表长为n,low、high和mid分别指向待查元素所在区间的下界、上界和中点,key为给定值。初始时,令low=1,high=n,mid=(low+high)/2,让key与mid指向的记录比较, 若key==r[mid].key,查找成功 若key 《排序问题求解》实验报告 一、算法的基本思想 1、直接插入排序算法思想 直接插入排序的基本思想是将一个记录插入到已排好序的序列中,从而得到一个新的, 记录数增1 的有序序列。 直接插入排序算法的伪代码称为InsertionSort,它的参数是一个数组A[1..n],包含了n 个待排序的数。用伪代码表示直接插入排序算法如下: InsertionSort (A) for i←2 to n do key←A[i] //key 表示待插入数 //Insert A[i] into the sorted sequence A[1..i-1] j←i-1 while j>0 and A[j]>key do A[j+1]←A[j] j←j-1 A[j+1]←key 2、快速排序算法思想 快速排序算法的基本思想是,通过一趟排序将待排序序列分割成独立的两部分,其中一 部分记录的关键字均比另一部分记录的关键字小,则可对这两部分记录继续进行排序,以达到整个序列有序。 假设待排序序列为数组A[1..n],首先选取第一个数A[0],作为枢轴(pivot),然后按照下述原则重新排列其余数:将所有比A[0]大的数都排在它的位置之前,将所有比A[0]小的数都排在它的位置之后,由此以A[0]最后所在的位置i 作为分界线,将数组A[1..n]分成两个子数组A[1..i-1]和A[i+1..n]。这个过程称作一趟快速排序。通过递归调用快速排序,对子数组A[1..i-1]和A[i+1..n]排序。 一趟快速排序算法的伪代码称为Partition,它的参数是一个数组A[1..n]和两个指针low、high,设枢轴为pivotkey,则首先从high 所指位置起向前搜索,找到第一个小于pivotkey 的数,并将其移到低端,然后从low 所指位置起向后搜索,找到第一个大于pivotkey 的数,并将其移到高端,重复这两步直至low=high。最后,将枢轴移到正确的位置上。用伪代码表示一趟快速排序算法如下: Partition ( A, low, high) A[0]←A[low] //用数组的第一个记录做枢轴记录 privotkey←A[low] //枢轴记录关键字 while low 电子科技大学实验报告 课程名称:数据结构与算法 学生姓名: 学号: 点名序号: 指导教师: 实验地点:基础实验大楼 实验时间: 5月20日 2014-2015-2学期 信息与软件工程学院《数据结构》实验报告——排序.docx
排序操作实验报告
(完整word版)查找、排序的应用 实验报告
算法排序问题实验报告
实验报告-排序与查找