各种排序算法时间性能的比较.doc-资料库

liuyunyannan-4002674-4744300845199066736.doc.pdf-第1页.png

第1页 / 共14页

liuyunyannan-4002674-4744300845199066736.doc.pdf-第2页.png

第2页 / 共14页

liuyunyannan-4002674-4744300845199066736.doc.pdf-第3页.png

第3页 / 共14页

liuyunyannan-4002674-4744300845199066736.doc.pdf-第4页.png

第4页 / 共14页

liuyunyannan-4002674-4744300845199066736.doc.pdf-第5页.png

第5页 / 共14页

liuyunyannan-4002674-4744300845199066736.doc.pdf-第6页.png

第6页 / 共14页

liuyunyannan-4002674-4744300845199066736.doc.pdf-第7页.png

第7页 / 共14页

liuyunyannan-4002674-4744300845199066736.doc.pdf-第8页.png

第8页 / 共14页

天津城市建设学院课程设计任务书 2011 —2012 学年第一学期电子与信息工程系专业班级课程设计名称：数据结构课程设计设计题目：各种排序算法时间性能的比较完成期限：自 2012 年 1 月 2 日至 2012 年 1 月 6 日共 1 周设计依据、要求及主要内容（可另加附页）：一、设计依据 [1]《数据结构课程设计指导书》 [2]《数据结构课程设计大纲》二、设计要求通过这次设计，要求在数据结构的逻辑特性和物理表示，数据结构的选择的应用、算法的设计及其实现等方面中深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。三、设计内容 1) 问题描述对各种排序方法（直接插入排序、希尔排序、起泡排序、快速排序、直接选择排序、堆排序和归并排序）的时间性能进行比较。 2) 基本要求 (1) 设计并实现上述各种排序算法； (2) 产生正序和逆序的初始排列分别调用上述排序算法，并比较时间性能； (3) 产生随机的初始排列分别调用上述排序算法，并比较时间性能。 3) 设计思想上述各种排序方法都是基于比较的内排序，其时间主要消耗在排序过程中进行的记录的比较次数和移动次数，因此，统计在相同数据状态下不同排序算法的比较次数和移动次数，即可实现比较各种排序算法的目的。直接插入排序、起泡排序、直接选择排序在教材中已经实现，请仿照教材中的方法在其他排序算法中的适当位置插入计数器统计元素的比较次数和移动次数。【思考题】如果测算每种排序算法所用实际的时间，应如何修改排序算法？ 1

四、参考资料 [1] 王红梅. 数据结构 C++.北京：清华大学出版社，2005. [2] 王红梅. 数据结构 C++实验指导书.北京：清华大学出版社，2005. [3] 严蔚敏，吴伟民．数据结构（C 语言版）．清华大学出版社指导教师（签字）：教研室主任（签字）：批准日期：年月日 2

目录一、需求分析...................................................................................................................................................4 1) 需求描述 .....................................................................................................................................4 2) 要求 .............................................................................................................................................4 3) 设计思想 .....................................................................................................................................4 二、总体设计...................................................................................................................................................4 1）程序的系统构造.........................................................................................................................4 2）程序的函数构造及其实现方式.................................................................................................5 三、详细设计...................................................................................................................................................5 1）数组的录入及其生成.................................................................................................................5 2）排序算法.....................................................................................................................................6 3）记录排序过程.............................................................................................................................8 4）分析并输出结果.........................................................................................................................8 四、调试与测试...............................................................................................................................................9 五、关键源程序清单和执行结果................................................................................................................ 12 1）快速排序和堆排序源程序.......................................................................................................12 2）执行结果概览...........................................................................................................................13 六、参考文献.................................................................................................................................................14 3

一、需求分析各种排序算法时间性能的比较 1) 需求描述对各种排序方法（直接插入排序、希尔排序、起泡排序、快速排序、直接选择排序、堆排序和归并排序）的时间性能进行比较。 2) 要求 (1) 设计并实现上述各种排序算法； (2) 产生正序和逆序的初始排列分别调用上述排序算法，并比较时间性能； (3) 产生随机的初始排列分别调用上述排序算法，并比较时间性能。 3) 设计思想上述各种排序方法都是基于比较的内排序，其时间主要消耗在排序过程中进行的记录的比较次数和移动次数，因此，统计在相同数据状态下不同排序算法的比较次数和移动次数，即可实现比较各种排序算法的目的。二、总体设计 1）程序的系统构造算法时间性能比较程序步数分析（生成顺序数组）步数分析（生成逆序数组）步数分析（生成随机数组）步数分析（手动输入数组）显示分析结果退出程序时间分析（生成随机数组） 4

时间分析是附加功能，时间分析比步数分析更能精确的记录程序的运行过程。 2）程序的函数构造及其实现方式生成正/逆序数组输入正序/逆序生成随机数组排序，记录步数排序，记录时间分析排序输出结果 (1)程序存储结构所有输入均使用顺序表存储结构。在二叉树的操作中，用 n*2 计算左孩子节点， n*2-1 计算右孩子节点；同理，使用 n/2 计算孩子的父节点。数组的赋值操作是使用循环对其各项一一赋值。 (2)排序，记录步数对同一个数组一次进行直接插入排序、希尔排序、起泡排序、快速排序、直接选择排序、堆排序和归并排序，统计各个算法中的比较次数和移动次数。 (3)分析结果对各个算法运行后记录下的总步数进行排序，比较出效率最好的算法和最差第算法。三、详细设计 1）数组的录入及其生成生成数组后，用循环对数组进行赋值，代码如下： void initYours( int *test,int n) { for( int i = 0; i < n; i++) 5

cin >> test[ i]; { } } 在数组的赋值过程中，必须传入数组长度。然后从 test[0..n]依次对数组进行赋值。在随机数组的生成过程中，使用 rand()函数产生伪随机数，用当前时间为随机数的种子，使每次产生的随机数组都不一样。随机数存入数组的代码如下： void initArr( int *myArr, int n) //初始化数组，将随机数存存入 { } int ran_num; srand( (unsigned)time( 0 ) ); for(int i = 0; i < n; i++) { } ran_num = rand()%1000; myArr[ i] = ran_num; 种子函数为：srand( (unsigned)time( 0 ) );生成 0-1000 之间的伪随机数依次存入数组。 2）排序算法（1）直接插入排序直接插入排序类似于玩纸牌时整理手中纸牌的过程，其基本思想是：依次将待排序序列中的每一个记录插入到一个已排好的序列中，直到全部记录都排好。（2）希尔排序先将整个待排序列分割成若干个子序列，在子序列中分别进行直接插入排序，待整个序列基本有序时，再对整个记录进行一次直接插入排序。在本程序的希尔排序中，希尔“逐段分割”的“增量”的计算方法使用：d=d/3+1;d 的初始值为 n，即数组长度。（3）冒泡排序两两比较相邻记录的关键码，如果凡序则交换，直到没有反序记录为止。具体排序过程为： 1. 将整个待排序的记录划分为有序区和无序区，初始状态有序区为空，无序区包所所有待排记录； 2. 对无序区从前向后依次将相邻记录的关键码进行比较，若反序则交换，从而使得关键码小的记录向前移动，大大记录向后移动； 3. 重复执行 2，直到无序区中没有反序的记录。（4）快速排序在快速排序中，记录的比较和移动是从两端向中间进行的，关键码较大的记录一次就能从前面移动到后面，关键码较小的记录一次就能从后面直接移动到前面，记录移动距离较远，从 6

而减少了总的移动次数。快速排序的伪代码如下： 1. 将 i 和 j 分别指向待排序区域的最左和最右侧记录的位置； 2. 重复下述过程，知道 i=j a) 右侧扫描，直到记录 j 的关键码小于基准记录的关键码； b) 如果 i

以下是归并的例子：图 2 3）记录排序过程在排序函数中，添加变量 Ccount 和变量 Ecount 的引用，分别对比较次数和交换次数做比较。当发生一次比较是 Ccount 自动加 1，发生一次交换时 Ecount 则自动加 1。如下代码，直接插入排序中的 Ccount 和 Ecount 引用： /////////////////////////////////////直接插入排序 void insert_sort( int *a, int n, int &cc, int &ec) { } int i, j, temp; for( i = 1; i < n; i++) { temp = a[ i]; for( j = i ,/* 测试*/ cc++; j > 0 && temp < a[ j-1]; j-- ) { } a[ j] = a[ j-1]; /* 测试*/ ec++; a[ j] = temp; } “/*测试*/ cc++”和“/*测试*/ cc++”分别是对 Ccount 和 Ecount 的自动加值，每运行一次，则这两个变量自动加 1。 4）分析并输出结果在 3）中得到的 Ccount 和 Ecount 的值将汇总传入对象数组 myseult[7]中，myseult[7]对象数组中包括排序名称和排序过程的记录值。对象的声明如下代码所示： class Result { public: string sortName; 8

资料库

各种排序算法时间性能的比较.doc

相关推荐

课程资源

热门标签

最新资料