数据结构实验报告
实验名称:实验四排序
学生:
班级:
班序号:
学号:
日期:2012年12月21日
1、实验要求
题目2
使用链表实现下面各种排序算法,并进行比较。
排序算法:
1、插入排序
2、冒泡排序
3、快速排序
4、简单选择排序
5、其他
要求:
1、测试数据分成三类:正序、逆序、随机数据。
2、对于这三类数据,比较上述排序算法中关键字的比较次数和移动次数(其中关键字交换计为3次移动)。
3、对于这三类数据,比较上述排序算法中不同算法的执行时间,精确到微秒(选作)。
4、对2和3的结果进行分析,验证上述各种算法的时间复杂度。
编写测试main()函数测试线性表的正确性。
2、程序分析
2.1存储结构
说明:本程序排序序列的存储由链表来完成。
其存储结构如下图所示。
(1)单链表存储结构:
(2)结点结构
struct Node
{
int data;
Node * next;
};
示意图:
2.2关键算法分析
一:关键算法
(一)直接插入排序 void LinkSort::InsertSort()
直接插入排序是插入排序中最简单的排序方法,其基本思想是:依次将待排序序列中的每一个记录插入到一个已排好的序列中,直到全部记录都排好序。
(1)算法自然语言
1.将整个待排序的记录序列划分成有序区和无序区,初始时有序区为待排序记录序列中的第一个记录,无序区包括所有剩余待排序的记录;
2.将无须去的第一个记录插入到有序区的合适位置中,从而使无序区减少一个记录,有序区增加一个记录;
3.重复执行2,直到无序区中没有记录为止。
(2)源代码
void LinkSort::InsertSort() //从第二个元素开始,寻找前面那个比它大的
{
Node * P = front->next; //要插入的节点的前驱
while(P->next)
{
Node * S = front; //用来比较的节点的前驱
while(1)
{
CompareCount++;
if( P->next->data < S->next->data ) // P的后继比S的后
继小则插入
{
insert(P, S);
break;
}
S = S->next;
if(S==P) //若一趟比较结束,且不需要插入
{
P = P->next;
break; }
}
}
}
(3)时间和空间复杂度
最好情况下,待排序序列为正序,时间复杂度为O(n)。
最坏情况下,待排序序列为逆序,时间复杂度为O(n2)。
直接插入排序只需要一个记录的辅助空间,用来作为待插入记录的暂存单元和查找记录的插入位置过程中的“哨兵”。
直接插入排序是一种稳定的排序方法。直接插入排序算法简单容易实现,当序列中的记录基本有序或带排序记录较少时,他是最佳的排序方法。但当待排序的记录个数较多时,大量的比较和移动操作使直接插入排序算法的效率减低。
插入到合适位置
直接插入排序过程
(二)冒泡排序void LinkSort::BubbleSort()
冒泡排序是交换排序中最简单的排序方法,其基本思想是:两两比较相邻记录的关键码,如果反序则交换,直到没有反序的记录为止。本程序采用改进的冒泡程序。
(1)算法自然语言
1.将整个待排序的记录序列划分成有序区和无序区,初始状态有序区为空,无序区包括所有待排序的记录。
2.对无序区从前向后依次将相邻记录的关键码进行比较,若反序则交换,从而使得关键码小的记录向前移,关键码大的记录向后移(像水中的气泡,体积大的先浮上来)。
3.将最后一次交换的位置pos,做为下一趟无序区的末尾。
4.重复执行2和3,直到无序区中没有反序的记录。
(2)源代码
void LinkSort::BubbleSort()
{
Node * P = front->next;
while(P->next) //第一趟排序并查找无序围
{
CompareCount++;
if( P->data > P->next->data)
swap(P, P->next);
P = P->next;
}
Node * pos = P;
P = front->next;
while(pos != front->next)
{
Node * bound = pos;
pos = front->next;
while(P->next != bound)
{
CompareCount++;
if( P->data > P->next->data)
{
swap(P, P->next);
pos = P->next;
}
P = P->next;
}
P = front->next;
}
}
(3)时间和空间复杂度
在最好情况下,待排序记录序列为正序,算法只执行了一趟,进行了n-1次关键码的比较,不需要移动记录,时间复杂度为O(n);
在最坏情况下,待排序记录序列为反序,时间复杂度为O(n2),空间复杂度为O(1)。
冒泡排序是一种稳定的排序方法。
反序则交换
(三)快速排序void LinkSort::Qsort()
(1)算法自然语言
1.首先选一个轴值(即比较的基准),将待排序记录分割成独立的两部分,左侧记录的关键码均小于或等于轴值,右侧记录的关键码均大于或等于轴值。
2.然后分别对这两部分重复上述过程,直到整个序列有序。
3.整个快速排序的过程递归进行。
(2)源代码
void LinkSort::Qsort()
{
Node * End = front;
while(End->next)
{
End = End->next;
}
Partion(front, End);
}
void LinkSort::Partion(Node * Start, Node * End)
{
if(Start->next==End || Start==End) //递归返回
return ;
Node * Mid = Start; //基准值前驱
Node * P = Mid->next;
while(P!=End && P!=End->next)
{
CompareCount++;
if( Mid->next->data > P->next->data ) //元素值小于轴点值,则将该元素插在轴点之前
{
if( P->next == End ) //若该元素为End,则将其前驱设为End
End = P;
insert(P, Mid);
Mid = Mid->next;
}
else P = P->next;
}
Partion(Start, Mid); //递归处理基准值左侧链表Partion(Mid->next, End); //递归处理基准值右侧链表
}
(3)时间和空间复杂度
在最好的情况下,时间复杂度为O(nlog2n)。
在最坏的情况下,时间复杂度为O(n2)。
快速排序是一种不稳定的排序方法。
(四)简单选择排序
基本思想为:第i趟排序通过n-i次关键码的比较,在n-i+1(1≤i≤n-1)各记录中选取关键码最小的记录,并和第i个记录交换作为有序序列的第i个记录。
(1)算法自然语言
1.将整个记录序列划分为有序区和无序区,初始状态有序区为空,无序区含有待排序的所有记录。
2.在无序区中选取关键码最小的记录,将它与无序区中的第一个记录交换,使得有序区扩展了一个记录,而无序区减少了一个记录。
3.不断重复2,直到无序区之剩下一个记录为止。
(2)源代码
void LinkSort::SelectSort()
{
Node * S = front;
while(S->next->next)
{
Node * P = S;
数据结构实验报告 实验名称:实验四排序 学生姓名: 班级: 班内序号: 学号: 日期:2012年12月21日 1、实验要求 题目2 使用链表实现下面各种排序算法,并进行比较。 排序算法: 1、插入排序 2、冒泡排序 3、快速排序 4、简单选择排序 5、其他 要求: 1、测试数据分成三类:正序、逆序、随机数据。 2、对于这三类数据,比较上述排序算法中关键字的比较次数和移动次数(其中关键字交换计为3次移动)。 3、对于这三类数据,比较上述排序算法中不同算法的执行时间,精确到微秒(选作)。
4、对2和3的结果进行分析,验证上述各种算法的时间复杂度。编写测试main()函数测试线性表的正确性。 2、程序分析 存储结构 说明:本程序排序序列的存储由链表来完成。 其存储结构如下图所示。 (1)单链表存储结构: (2)结点结构 struct Node { int data;
Node * next; }; 示意图: 关键算法分析 一:关键算法 (一)直接插入排序 void LinkSort::InsertSort() 直接插入排序是插入排序中最简单的排序方法,其基本思想是:依次将待排序序列中的每一个记录插入到一个已排好的序列中,直到全部记录都排好序。 (1)算法自然语言 1.将整个待排序的记录序列划分成有序区和无序区,初始时有序区为待排序记录序列中的第一个记录,无序区包括所有剩余待排序的记录; 2.将无须去的第一个记录插入到有序区的合适位置中,从而使无序区减少一个记录,有序区增加一个记录; 3.重复执行2,直到无序区中没有记录为止。 (2)源代码 void 2. 3. 4.重复执行2和3 直接插入排序过程
《数据结构》实验报告排序实验题目: 输入十个数,从插入排序,快速排序,选择排序三类算法中各选一种编程实现。 实验所使用的数据结构内容及编程思路: 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、直接插入排序算法思想 直接插入排序的基本思想是将一个记录插入到已排好序的序列中,从而得到一个新的, 记录数增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学期 信息与软件工程学院算法排序问题实验报告
实验报告-排序与查找