实验四 排序 实验报告(1)(11页)
时间:2020-11-10 20:45:14 来源:勤学考试网 本文已影响 人
PAGE
PAGE 1
数据结构实验报告
实验名称:实验四 排序
学生姓名:
班级:
班内序号:
学号:
日期:2012年12月21日
实验要求
题目2
使用链表实现下面各种排序算法,并进行比较。
排序算法:
1、插入排序
2、冒泡排序
3、快速排序
4、简单选择排序
5、其他
要求:
1、测试数据分成三类:正序、逆序、随机数据。
2、对于这三类数据,比较上述排序算法中关键字的比较次数和移动次数(其中关键字交换计为3次移动)。
3、对于这三类数据,比较上述排序算法中不同算法的执行时间,精确到微秒(选作)。
4、对2和3的结果进行分析,验证上述各种算法的时间复杂度。
编写测试main()函数测试线性表的正确性。
2、 程序分析
2.1存储结构
说明:本程序排序序列的存储由链表来完成。
其存储结构如下图所示。
(1)单链表存储结构:
结点 地址:
结点 地址:1000H
1080H
……
头指针地址:1020HA[0]
头指针
地址:1020H
10C0H
……
地址:1080H A[3]
地址:1080H
NULL
……
地址:10C0HA[1]
地址:10C0H
1000H
……
(2)结点结构
struct Node
{
int data;
Node * next;
};
示意图:
int dataNode * next
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)。
直接插入排序只需要一个记录的辅助空间,用来作为待插入记录的暂存单元和查找记录的插入位置过程中的“哨兵”。
直接插入排序是一种稳定的排序方法。直接插入排序算法简单容易实现,当序列中的记录基本有序或带排序记录较少时,他是最佳的排序方法。但当待排序的记录个数较多时,大量的比较和移动操作使直接插入排序算法的效率减低。
r
r1≤r2≤ … … ≤ri-1 ri ri+1 … … rn
有序区 无序区
直接插入排序的基本思想
插入到合适位置
直接插入排序过程
初始键值序列 [12] 15 9 20 6 31 24
第一趟排序结果 [12 15] 9 20 6 31 24
第二趟排序结果 [9 12 15] 20 6 31 24
第三趟排序结果 [9 12 15 20] 6 31 24
第四趟排序结果 [6 9 12 15 20] 31 24
第五趟排序结果 [6 9 12 15 20 31] 24
第六趟排序结果 [6 9 12 15 20 24 31]
(二)冒泡排序 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)。
冒泡排序是一种稳定的排序方法。
r
rj rj+1 ri+1 ≤ …… ≤ rn-1 ≤rn
无序区 有序区
1≤j≤i-1 已经位于最终位置
起泡排序的基本思想
反序则交换
初始键值序列
初始键值序列 [50 13 55 97 27 38 49 65]
第一趟排序结果 [13 50 55 27 38 49 65] 97
第二趟排序结果 [13 50 27 38 49] 55 65 97
第三趟排序结果 [13 27 38 49] 50 55 65 97
第四趟排序结果 13 27 38 49 50 55 65 97
冒泡排序过程
(三)快速排序 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)。
快速排序是一种不稳定的排序方法。
[
[ r1 … … ri-1 ] ri [ ri+1 … … rn ]
均≤ri 轴值 均≥ri
位于最终位置
快速排序的基本思想图解
(四)简单选择排序
基本思想为:第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;
Node * Min = P;
while(P->next) //查找最小记录的位置
{
CompareCount++;
if(P->next->data < Min->next->data)
Min = P;
P = P->next;
}
insert(Min, S);
S = S->next;
}
}
(3)时间和空间复杂度
简单选择排序最好、最坏和平均的时间复杂度为O(n2)。
简单选择排序是一种不稳定的排序方法。
初始键值序列
初始键值序列 [49 27 65 97 76 13 38]
第一趟排序结果 13 [27 65 97 76 49 38]
第二趟排序结果 13 27 [65 97 76 49 38]
第三趟排序结果 13 27 38 [97 76 49 65]
第四趟排序结果 13 27 38 49 [76 97 65]
第五趟排序结果 13 27 38 49 65 [97 76]
第六趟排序结果 13 27 38 49 65 76 97
简单选择排序的过程示例
(五)输出比较结果函数(含计算函数体执行时间代码)
(1)算法自然语言
1、依次调用直接插入排序、冒泡排序、快速排序、简单选择排序的函数体,进行序列的排序,并输出相应的比较次数、移动次数。
2、获取当前系统时间。在调用函数之前设定一个调用代码前的时间,在调用函数之后再次设定一个调用代码后的时间,两个时间相减就是代码运行时间。
说明:运用QueryPerformanceFrequency()可获取计时器频率;QueryPerformanceCounter()用于得到高精度计时器的值。
(2)源代码
void printResult(LinkSort &a, LinkSort &b, LinkSort &c, LinkSort &d)
{
_LARGE_INTEGER time_start; //开始时间
_LARGE_INTEGER time_over; //结束时间
double dqFreq; //计时器频率
LARGE_INTEGER f; //计时器频率
QueryPerformanceFrequency(&f);
dqFreq=(double)f.QuadPart;
a.print();
double TimeCount;
CompareCount = 0; MoveCount = 0; TimeCount = 0;
QueryPerformanceCounter(&time_start); //记录起始时间
a.InsertSort();
QueryPerformanceCounter(&time_over); //记录结束时间
TimeCount = ((time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000;
cout << "排序结果:"; a.print();
cout << "1.插入。
比较次数:" << setw(3) << CompareCount << "; 移动次数:" << setw(3) << MoveCount << "; 时间: " << TimeCount <<"us"<< endl;
CompareCount = 0; MoveCount = 0; TimeCount = 0;
QueryPerformanceCounter(&time_start); //记录起始时间
b.BubbleSort();
QueryPerformanceCounter(&time_over); //记录结束时间
TimeCount = ((time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000;
cout << "2.冒泡。
比较次数:" << setw(3) << CompareCount << "; 移动次数:" << setw(3) << MoveCount << "; 时间: " << TimeCount << "us"<<endl;
CompareCount = 0; MoveCount = 0; TimeCount = 0;
QueryPerformanceCounter(&time_start); //记录起始时间
c.Qsort();
QueryPerformanceCounter(&time_over); //记录结束时间
TimeCount = ((time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000 ;
cout << "3.快速。
比较次数:" << setw(3) << CompareCount << "; 移动次数:" << setw(3) << MoveCount << "; 时间: " << TimeCount << "us"<<endl;
CompareCount = 0; MoveCount = 0; TimeCount = 0;
QueryPerformanceCounter(&time_start); //记录起始时间
d.SelectSort();
QueryPerformanceCounter(&time_over); //记录结束时间
TimeCount = ((time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000;
cout << "4.选择。
比较次数:" << setw(3) << CompareCount << "; 移动次数:" << setw(3) << MoveCount << "; 时间: " << TimeCount << "us"<<endl;
}
(3)时间和空间复杂度
时间复杂度O(1)(因为不包含循环体)。
2.3其他
排序方法
平均情况
最好情况
最坏情况
辅助空间
直接插入排序
O(n2)
O(n)
O(n2)
O(1)
希尔排序
O(nlog2n)~O(n2)
O(n1.3)
O(n2)
O(1)
起泡排序
O(n2)
O (n)
O(n2)
O(1)
快速排序
O(nlog2n)
O(nlog2n)
O(n2)
O(log2n) ~O(n)
简单选择排序
O(n2)
O(n2)
O(n2)
O(1)
堆排序
O(nlog2n)
O(nlog2n)
O (nlog2n)
O(1)
归并排序
O(nlog2n)
O(nlog2n)
O(nlog2n)
O(n)
3、程序运行结果
(1)程序流程图
开始
开始
输入数据
输入数据
顺序数组四种排序和统计
顺序数组四种排序和统计
逆序数组四种排序和统计
逆序数组四种排序和统计
乱序数组四种排序和统计
乱序数组四种排序和统计
输出统计结果
输出统计结果
结
结 束
(2)测试条件
规模为10个数字,在正序、逆序和乱序的条件下进行测试,未出现问题。
(3)运行结果:
(4)说明:各函数运行正常,没有出现bug。
四、总结
1、调试时出现的问题及解决方法
由于经过一种排序后,原始数据改变,导致后面的排序所用的数据全为排好后的数据。将数据在排序前重新初始化后,该问题被排除。还有就是因为编程时没有注意格式,所以在调试错误时花费了不少时间。
2、心得体会
这是最后一次编程实验。这次试验,我觉得主要目的还是在掌握好课本知识的基础上,对代码进行相应的优化,以达到时间复杂度和空间复杂度的最佳。
其次,本次实验是经过借鉴课本上的程序进行编写,是基于课本完成的。考虑到若完全由自己编写,则又可能限于自己能力问题,将较简单的算法编写的过于麻烦,造成关键码的比较次数和移动次数比一些复杂算法还多,从而影响结果。
基于课本编写,最大好处是可以借鉴、仔细研读书上的优秀例子,开拓以后编写程序的思路。基于课本编写,最大坏处是自己独立思考、独立编写、修改程序的能力未得到锻炼。
对于正序序列,直接插入、起泡排序法有较高的效率。
对于逆序序列,简单选择排序效率较高。
对于在随机序列,快速排序法的效率比较高。
程序的优化是一个艰辛的过程,如果只是实现一般的功能,将变得容易很多,当加上优化,不论是效率还是结构优化,都需要精心设计。这次做优化的过程中,遇到不少阻力。由于优化中用到很多类的封装和访问控制方面的知识,而这部分知识恰好是大一一年学习的薄弱点。因而以后要多花力气学习C++编程语言,必须要加强这方面的训练,这样才能在将编程思想和数据结构转换为代码的时候能得心应手。