实验四排序实验报告材料

1、数据结构实验报告实验名称：实验四 排序学生：班级：班序号：学号：日期： 2012 年 12 月 21 日1、实验要求题目 2使用链表实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、冒泡排序3、快速排序4、简单选择排序5、其他要求：1、测试数据分成三类：正序、逆序、随机数据。2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换 计为 3 次移动）。3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度。编写测试main()函数测试线性表的正确性。2、程序分析2.1存储结构说明：本

2、程序排序序列的存储由链表来完成。 其存储结构如下图所示。(1) 单链表存储结构：（2 ）结点结构struct Nodeint data;Node * n ext;；示意图:int dataNode * next2.2关键算法分析一：关键算法（一）直接插入排序 void Lin kSort:l nsertSort（）直接插入排序是插入排序中最简单的排序方法，其基本思想是：依次将待排序序列中的每 一个记录插入到一个已排好的序列中，直到全部记录都排好序。（1）算法自然语言1. 将整个待排序的记录序列划分成有序区和无序区，初始时有序区为待排序记录序列中的 第一个记录，无序区包括所有剩余待排序的记录；2

3、. 将无须去的第一个记录插入到有序区的合适位置中，从而使无序区减少一个记录，有序 区增加一个记录；3. 重复执行2,直到无序区中没有记录为止。(2) 源代码/从第二个元素开/要插入的节点的void LinkSort:lnsertSort()始，寻找前面那个比它大的Node * P = fron t- >n ext;前驱while (P->next)Node * S = front;/ 用来比较的节点的前while (1)CompareCount+;/P的后继比S的后if ( P->next->data < S->next->data ) 继小则插入in

4、sert(P, S); break ;/ 若一趟比较结束， 且不需S = S->next;if (S=P)要插入P = P->next;break ; （3）时间和空间复杂度最好情况下，待排序序列为正序，时间复杂度为最坏情况下，待排序序列为逆序，时间复杂度为直接插入排序只需要一个记录的辅助空间，的插入位置过程中的“哨兵” 。O（n）。O（n2）。用来作为待插入记录的暂存单元和查找记录直接插入排序是一种稳定的排序方法。 直接插入排序算法简单容易实现， 当序列中的记 录基本有序或带排序记录较少时， 他是最佳的排序方法。 但当待排序的记录个数较多时， 大 量的比较和移动操作使直接插入排序

5、算法的效率减低。（二）冒泡排序void LinkSort:BubbleSort()冒泡排序是交换排序中最简单的排序方法， 其基本思想是： 两两比较相邻记录的关键码，如果反序则交换，直到没有反序的记录为止。本程序采用改进的冒泡程序。1）算法自然语言1. 将整个待排序的记录序列划分成有序区和无序区，初始状态有序区为空，无序区包括所有 待排序的记录。2. 对无序区从前向后依次将相邻记录的关键码进行比较，若反序则交换，从而使得关键码小 的记录向前移，关键码大的记录向后移（像水中的气泡，体积大的先浮上来） 。3将最后一次交换的位置 pos，做为下一趟无序区的末尾。4. 重复执行 2和 3，直到无序区中没

6、有反序的记录。（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-&

7、gt;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),空间复杂度为 0(1)。在最坏情况下，待排序记录序列为反序，时间复杂度为冒泡排序是一种稳定的排序方法。初始键值序列:5013559727384965

8、 第一趟排序结果:13505527384965 97第二趟排序结果:1350273849556597第三趟排序结果:1327384950556597(三) 快速排序 void LinkSort:Qsort()(1) 算法自然语言1. 首先选一个轴值(即比较的基准)，将待排序记录分割成独立的两部分，左侧记录的关 键码均小于或等于轴值，右侧记录的关键码均大于或等于轴值。2. 然后分别对这两部分重复上述过程，直到整个序列有序。3. 整个快速排序的过程递归进行。(2) 源代码void LinkSort:Qsort()Node * End = front;while (End->next)End

9、= End->n ext;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 )/ 递归返回/ 基准值前驱/ 元素值小于轴

10、点值， 则将该元素插在轴点之前if ( P->next = End )设为 EndEnd = P; insert(P, Mid); Mid = Mid->next;else P = P->next;Partion(Start, Mid);/若该元素为End,则将其前驱/递归处理基准值左侧链表Partion(Mid->next, End);/ 递归处理基准值右侧链表3)时间和空间复杂度在最好的情况下，时间复杂度为O( nlog2n)。在最坏的情况下，时间复杂度为O( n2)。快速排序是一种不稳定的排序方法。(四) 简单选择排序基本思想为：第i趟排序通过n-i次关键码的比较

11、，在 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 =

12、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）。简单选择排序是一种不稳定的排序方法。（五）输出比较结果函数（含计算函数体执行时间代码）（1）算法自然语言1、依次调用直接插入排序、冒泡排序、快速排序、简单选择排序的函数体，进行序列的排 序，并

13、输出相应的比较次数、移动次数。2、获取当前系统时间。在调用函数之前设定一个调用代码前的时间，在调用函数之后再次 设定一个调用代码后的时间，两个时间相减就是代码运行时间。说明：运用 QueryPerformanceFrequency（） 可获取计时器频率； QueryPerformanceCounter（） 用 于得到高精度计时器的值。(2) 源代码void printResult(LinkSort &a, LinkSort &b, LinkSort &c, LinkSort &d)_LARGE_INTEGER time_start;/ 开始时间_LARGE_IN

14、TEGER 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

15、_over);/ 记录结束时间TimeCount = (time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000;cout << "排序结果： " a.print();cout << "1. 插入。 比较次数： " << setw(3) << CompareCount << " 移 动次数：" << setw(3) << MoveCount << "时间: " <

16、;< 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 << "

17、;2. 冒泡。 比较次数： " << setw(3) << CompareCount << " 移 动次数： " << setw(3) << MoveCount << "时间 : " << TimeCount <<"us" <<endl;/ 记录起始时间CompareCount = 0; MoveCount = 0; TimeCount = 0;QueryPerformanceCounter(&time_sta

18、rt);c. Qsort();QueryPerforma nceCo unter(&time_over);/记录结束时间TimeCo unt = (time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000 ;cout << "3.快速。 比较次数："<< setw(3) << CompareCount << " 移 动次数："<< setw (3) << MoveCou nt <<" 时间："

19、;<< TimeCou nt <<"us" <<endl;CompareCo unt = 0; MoveCo unt = 0; TimeCo unt = 0;QueryPerformanceCounter(&time_start);/ 记录起始时间d. SelectSort();QueryPerforma nceCo unter(&time_over);/记录结束时间TimeCo unt = (time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000;cout <

20、< "4.选择。 比较次数："<< setw(3) << CompareCount << " 移 动次数："<< setw (3) << MoveCou nt <<" 时间:"<< TimeCou nt <<"us" <<endl;(3) 时间和空间复杂度时间复杂度0(1)(因为不包含循环体)。2.3其他排序方法平均情况最好情况最坏情况辅助空间直接插入排序0( n2)O(n)O(n2)O(1)希尔排序0

21、( nlog2n) O( n2)0( n13)0( n2)0(1)起泡排序0(")0 (n)0( n2)0(1)快速排序O(nlog 2n)0( nlog2n)0( n2)0( log2n) 0( n)简单选择排序0( n2)0( n2)0( n2)0(1)堆排序O(nlog 2n)0( nlog2n)0 (nlog 2n)0(1)归并排序O(nlog 2n)0( nlog2n)0( nlog2n)0( n)3、程序运行结果(1)程序流程图(2 )测试条件规模为10个数字，在正序、逆序和乱序的条件下进行测试，未出现问题。(3)运行结果：SB C:wi n dowssyste m 32

22、cmd esceia z« jh 牝 油 bu w tu vw 丄tw:0,977417uss 0.97741；2.44J5<iJisi 1.4bE»13usM.4K»7»»uS2.9322Sus7.Sl?33ns1.9E1B3H3:1.4bhl3ua :2 . d435-lciu :2.¥J2bus :l.?B493us0 V 5 5 9i- ee次次次次 0a动动 二0三宀亠胃0£戶 06O - -5 ;5 5 _7 5 44 14b040 LLLKULLLL IHHHb- I 7丄£卜.占 esww 0 E krwkr70G0 ; -J - f ->5 ¥ 5 9 44 2 50 142-'iv.A 2H 0 Fl D : 1Lh In L严70 0 4 0030804- -9 3V V n 7 9 0 9 n61 1- 黑次峻 0 动»1W S -K.- 1 66-f42H 点I/