数据结构课程设计-常用排序算法的比较.doc

xxxxxxxxxx课程设计报告重庆科技学院课程设计任务书设计题目：常用排序算法的比较学生姓名*课程名称数据结构课程设计专业班级 *地 点计算机基础自主学习中心起止时间 2011.11.16-12.5设计内容及要求利用随机函数产生n个随机整数，采用多种方法对这些数进行排序，然后分析各自的所需的排序时间找出较快的排序算法。要求：1) 分别采用的排序算法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序，实现这批数据的排序，并把排序后的结果保存在不同的文件中。2) 统计每一种排序算法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的算法。注：在完成以上数据的同时，还能采用其它的排序算法，适当加分。设计参数 测试数据要求：随机产生1000 个以上的随机整数，并保存在文本文件中。排序后的数据和所需的时间也保存在各自的txt文件中。进度要求 参考资料1严蔚敏 吴伟民 著， 数据结构，清华大学出版社，2007.32李春葆 著，数据结构教程，清华大学出版社，2005.13. richard f.gilberg behrouz a.forouzan, 数据结构的c+伪码实现（英文版），人民邮电出版社，2002.1其它说明.本表应在每次实施前一周由负责教师填写二份，院系审批后交院系办备案，一份由负责教师留用。.若填写内容较多可另纸附后。3.一题多名学生共用的，在设计内容、参数、要求等方面应有所区别。教研室主任： 指导教师： 2011年 11月 16日摘要排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，其中包含冒泡排序，直接插入排序，简单选择排序，希尔排序，快速排序，堆排序等，各有其特点。对排序算法比较的分析可以遵循若干种不同的准则，通常以排序过程所需要的算法步数作为度量，有时也以排序过程中所作的键比较次数作为度量。特别是当作一次键比较需要较长时间，例如，当键是较长的字符串时，常以键比较次数作为排序算法计算时间复杂性的度量。当排序时需要移动记录，且记录都很大时，还应该考虑记录的移动次数。究竟采用哪种度量方法比较合适要根据具体情况而定。本报告将描述如何利用随机函数产生n个随机整数，采用多种方法对这些数进行排序，然后分析各自的所需的排序时间找出较快的排序算法。关键词：排序算法 数据结构 随机函数 ii目录摘要i1 设计内容和要求11.1 设计内容11.2 设计要求12 需求分析22.1 直接插入排序22.2 希尔排序22.3 快速排序:（递归和非递归）22.4 堆排序33 概要设计43.1 头文件43.2 adt43.3 各种操作函数：43.4 主函数54 详细设计64.1 主函数64.2直接插入排序74.3希尔排序94.4起泡排序104.5快速排序114.6选择排序134.7堆排序154.8归并排序185 系统测试215.1 系统操作215.2 测试数据236 总结26致谢27参考文献281 设计内容和要求1.1 设计内容利用随机函数产生n个随机整数，采用多种方法对这些数进行排序，然后分析各自的所需的排序时间找出较快的排序算法。1.2 设计要求1) 分别采用的排序算法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序，实现这批数据的排序，并把排序后的结果保存在不同的文件中。 2) 统计每一种排序算法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的算法。282 需求分析2.1 直接插入排序思路:设有一组关键字k1,k2,.,kn,排序开始变认为k1是一个有序的序列,让k2插入到表长为1的有序序列,使之成为一个表长为2的有序序列, 让k3插入到表长为2的有序序列,使之成为一个表长为3的有序序列,依次类推,最后让kn插入上述表长为n-1的有序序列,得到一个表长为n的有序序列.2.2 希尔排序思路：先取一个正整数d1(d1n),把全部记录分成d1个组,所有距离为d1的倍数的记录看成是一组,然后在各组内进行插入排序;然后取d2(d2=1),即所有记录成为一个组为此.一般选d1约为n/2,d2为d1/2,.,di=12.3 快速排序:（递归和非递归）思路:以第一个关键字k1为控制字，将k1、k2、.kn分成两个子区，使左区的有关键字小于等于k1，右区所有关键字大于等于k1，最后控制居两个子区中间的适当位置。在子区内数据尚处于无序状态。将右区首、尾指针保存入栈，对左区进行与第（1）步相类似的处理，又得到它的左子区和右子区，控制字区中。重复第（1）、（2）步，直到左区处理完毕。然后退栈对一个个子区进行相类似的处理，直到栈空。分区处理函数hoare思路：首先用两个指针i、j分别指向首、尾两个关键字，i=1，j=8。如对(46、56、14、43、95、10、19、72)。第一个关键字46作为控制字，该关键字所属的记录另存储在一个x变量中。从文件右端元素rj.key开始与控制字x.key相比较，当rj.key大于等于x.key时，rj不移动，修改指针j，j-，直到rj.keyx.key，把记录rj移动到文件左边i所指向的位置;然后在文件左边修改i指针,i+，让ri.key与x.key相比较，当ri.key小于等于x.key时，ri不移动，修改指针i，i-，直到ri.keyx.key, 把记录ri移动到文件右边j所指向的位置;然后在文件右边修改j指针j-。重复上面的步骤.2.4 堆排序思路：把n个记录存于向量r之中，把它看成完全二叉树，此时关键字序列不一定满足堆的关系。堆排序大体分为两步处理：初建堆，从堆的定义出发，当i=1、2、。、2/n时应满足ki=k2i和ki=k2i+1.所以先取i=n/2(它一定是第n个结点的双亲编号),将以i结点为根的子树调整为堆，然后令i=i-1，将以不结点为根的子树调整为堆。此时可能会反复调整某些结点，直到i=1为止，堆初步建成。堆排序，首先输出堆顶元素（一般是最小值）,让堆中最后一个元素上移到原堆顶位置，然后恢复堆。因为经过第一步输出堆顶元素的操作后，往往破坏了堆关系，所以要恢复堆；重复执行输出堆顶元素、堆尾元素上移和恢复堆的步骤。3 概要设计3.1 头文件#include#include#include#include3.2 adt struct element int key;list20;struct rnodeint key;int point;3.3 各种操作函数：（1）创建一个数组函数：int creat()；（2）输出数组函数：void print(struct element a20,int n)；（3）保存函数：void save(struct element asize,int n, char filename ) （4）直接插入排序函数：void insert_sort(element a, int n)（5）希尔排序函数：void shell(struct element a20,int n)；（6）快速排序函数（分区处理函数）：int hoare(struct element a20,int l,int h)；（7）非递归的快速排序函数：void quick1(struct element a20,int n)；（8）递归的快速排序函数：void quick2(struct element a20,int l,int h)；（9）堆排序（调整堆的函数）：void heap(struct element a20,int i,int m)；（10）堆排序（主体函数）：void heapsort(struct element a20,int n)；（11）时间函数：start = clock();end = clock();3.4 主函数void main()接受命令（选择要执行的操作）；处理命令；输出结果； 4 详细设计4.1 主函数如下：为程序主函数。#include#include#include#include#define size 1000000struct element int key;listsize;/创建一个数组/int creat() int i,n; int num;n=0;printf(请输入元素个数:);scanf(%d,&num);for( i = 0;i num; i+ )listn.key = rand() % 10000;n+;return(n);/输出数组/void print(struct element asize,int n) int i;for(i=0;in;i+) printf(%5d,ai .key); printf(n);/保存到文件/void save(struct element asize,int n, char filename ) int m_wr=0; / 写入txt文件变量 file *fp;if ( ( fp = fopen ( filename, w ) ) = null ) printf(file writer errorn); for (int m=0; melem ) / 如果线性表为空exit ( error ); for ( i=2; ilength; +i) key = l-elemi; / 设定关键字if ( key elemi-1 ) / 与前一个数字比较，是否“elemi = l-elemi-1;l-elemi-1 = key;for ( j=i-2; key elemj ; -j ) l-elemj+1 = l-elemj; / 数据后移l-elemj+1 = key; / 插入到正确位置if ( ( fp = fopen ( d:顺序表直接插入排序.txt, a+ ) ) = null ) exit ( error ); for ( n=0; nlength; n+ )m_wr = l-elemn; / 获取线性表元素fprintf ( fp, %d , m_wr ); / 写入txt中 fclose ( fp );4.3 希尔排序如下：为希尔排序算法。void shell(struct element asize,int n)int i,j,k;for(i=n;i=1;i-)ai.key=ai-1.key;k=n/2;while(k=1)for(i=k+1;ia0.key)&(j=0)aj+k.key=aj.key;j=j-k;aj+k=a0;k=k/2;for(i=0;ielem ) exit ( error ); for ( j=1; jlength; j+ ) / j控制排序长度 for ( i=0; ilength-j; i+ ) / 每趟排序长度减1 if ( l-elemi elemi+1 ) / 顺序不变key = l-elemi+1; / 将较大值赋给keyelse / 如果小于，顺序交换key = l-elemi; / 利用关键字l-elemi = l-elemi+1; l-elemi+1 = key;if ( ( fp = fopen ( d:顺序表冒泡排序.txt, a+ ) ) = null ) exit ( error );for ( n=0; nlength; n+ )m_wr = l-elemn; fprintf(fp, %d , m_wr ); fclose ( fp );4.5 快速排序如下：为快速排序算法。int insertclass:partition ( sqlist *l, int low, int high )/ 交换子表中记录int key = 0;if ( !l-elem ) exit ( error ); key = l-elemlow; / 将子表的第一个做为记录的关键字while ( low high ) / 从表的两端交替向中间扫描 while ( lowelemhigh = key ) -high; l-elemlow = l-elemhigh; / 将比枢轴记录小的记录移到低端while ( lowelemlowelemhigh = l-elemlow; / 将比枢轴记录大的记录移到高端l-elemlow = key; / 枢轴记录到位return low; / 反回low的位置void insertclass:qsort ( sqlist *l, int low, int high )/ 对子表进行快速排序int pivotloc=0; if ( low elemlow.high一分为二qsort ( l, low, pivotloc-1 ); / 低子表递归排序qsort ( l, pivotloc+1, high ); / 高子表递归排序void insertclass:quicksort ( sqlist *l )/对顺序表l作快速排序int m_wr = 0;unsigned long n; file *fp; qsort ( l, 0, l-length-1 ); / 调用递归函数进行排序if ( ( fp = fopen ( d:顺序表快速排序.txt, a+ ) ) = null ) exit (error );for ( n=0 ; nlength ; n + )m_wr = l-elemn; fprintf ( fp, %d , m_wr ); fclose ( fp );4.6 选择排序如下：为选择排序算法void insertclass:treesort ( sqlist *l ) / 对顺序表l进行树形选择排序 int m_wr = 0;unsigned long floor, crunode,crunode1;unsigned long i, j, j1, m, n; elemtype *t; file *fp;if ( !l-elem ) exit ( error );m = l-length; floor = ( unsigned long ) ceil ( log(m) / log(2) ) + 1; / 完全二叉树的层数 crunode = ( unsigned long ) pow ( 2, floor ) - 1; / floor层完全二叉树的结点总数 crunode1 = ( unsigned long ) pow ( 2, floor - 1 ) - 1; / floor-1层完全二叉树的结点总数 t = (elemtype*) malloc ( crunode * sizeof ( elemtype ) ); / 二叉树采用顺序存储结构 / 创建完全二叉树 for ( i=0; ielem赋给叶子结点 tcrunode1+i = l-elemi; for ( i=crunode1+m; icrunode; i+ ) / 给多余的叶子的关键字赋无穷大 ti = int_max; / 头文件中的2147483647 j1 = crunode1; j = crunode; / 给非叶子结点赋值 while ( j1 ) for ( i=j1; ij; i+=2 ) ti ti+1 ? (t(i+1)/2-1=ti) : (t(i+1)/2-1 = ti+1); / 条件？表达式：表达式 j = j1; j1 = (j1-1) / 2; for ( i=0; ielemi l-elemi = t0; / 将当前最小值赋给l-elemi j1 = 0; for ( j=1; jfloor; j+ ) / 沿树根找结点t0在叶子中的序号j1 t2*j1+1 = tj1 ? (j1=2*j1+1) : (j1=2*j1+2); /if-else语句 tj1 = int_max; while ( j1 ) j1 = (j1+1) / 2 - 1; / 序号为j1的结点的双亲结点序号 t2*j1+1 = t2*j1+2 ? (tj1=t2*j1+1) : (tj1=t2*j1+2); if ( (fp = fopen ( d:顺序表树形选择排序.txt, a+ ) ) = null ) exit ( error );for ( n=0; nlength; n+ )m_wr = l-elemn; fprintf ( fp, %d , m_wr ); fclose ( fp ); free ( t );4.7 堆排序如下：为堆排序算法void insertclass:initheap ( sqlist *l, int n )/ 初始化大顶堆int key = 0; int i, j, k; for( i=(n-1)/2; i=0; i- ) / 从编号最大的终端节点开始 j = 2 * i + 1; / 编号为j的节点是i的左孩子 k = i; if( l-elemj elemj+1 & j+1elemj l-elemk & 2*k+1 elemk; / 如果大于，则交换 l-elemk = l-elemj; l-elemj = key;k = j; j = 2 * k + 1;if( l-elemj+1 l-elemj & j+1 n) / 交换以后可能造成堆的破坏,需要从交换的节点往后调整j+;/ 大顶堆调整void insertclass:adjustheap(sqlist *l,int n) int key = 0; int i = 0;int j = 0; while ( 2*i+1 elemj elemj+1 & j+1elemj l-elemi ) / 交换 key = l-elemi; / 利用关键字做中间保介质 l-elemi = l-elemj; l-elemj = key; i = j; / 对顺序表l进行堆排序void insertclass:heapsort(sqlist *l)int key = 0;int m_wr = 0; int i = 0;unsigned long n;file *fp;if ( !l-elem ) exit ( error ); initheap ( l, l-length ); / 初始化大顶堆 for ( i=l-length-1; i0; i- ) / 输出堆顶元素,不断调整堆if ( l-elem1 l-elem0 ) / 此句极其重要break;key = l-elemi; / 利用关键字l-elemi = l-elem0;l-elem0 = key;adjustheap ( l, i-1 ); / 调整if ( ( fp = fopen ( d:顺序表堆排序.txt, a+ ) )=null ) exit ( error );for ( n=0; nlength; n+ )m_wr = l-elemn; fprintf ( fp, %d , m_wr ); fclose ( fp );4.8 归并排序如下：为归并排序算法int b200000;void insertclass:merge ( int a, int low, int middle, int high )/ 将相邻两个子表合并 int h, i, j, k; h = low; i = low; j = middle+1; while ( h=middle & j=high ) / 前段子表 if ( ahmiddle ) / 后段子表 for ( k=j; k=high; k+ ) / 排序后的值放入到b后段中 bi = ak; i+; else for ( k=h; k=middle; k+ ) bi = ak; i+; for ( k=low; k=high; k+ ) ak = bk; void insertclass:msort(int a,int low,int high)/ 利用递归进行归并排序 int middle = 0; / 两子表的分隔点 if ( lowhigh ) middle = (low+high) / 2; msort ( a, low, middle ); / 前段子表排序 msort ( a, middle+1, high ); / 后段子表排序 merge ( a, low, middle, high ); void insertclass:mergesort ( sqlist *l ) / 对顺序表l作归并排序 int m_wr = 0;unsigned long n;file *fp; msort ( (*l).elem, 0, (*l).length-1 ); if ( ( fp = fopen ( d:顺序表归并排序.txt, a+ ) ) = null ) exit (error );for ( n=0; nlength; n+ )m_wr = l-elemn; fprintf(fp, %d , m_wr ); fclose ( fp );5 系统测试它的的任务是尽可能彻底地检查出程序中的错误，提高软件系统的可靠性，其目的是检验系统做得怎样？。这阶段又可分为三个步骤：模块测试，测试每个模块的程序是否有错误；组装测试，测试模块之间的接口是否正确；确认测试，测试整个软件系统是否满足用户功能和性能的要求。该阶段结束应交付测试报告，说明测试数据的选择，测试用例以及测试结果是否符合预期结果。测试发现问题之后要经过调试找出错误原因和位置，然后进行改正。是基于系统整体需求说明书的黑盒类测试，应覆盖系统所有联合的部件。系统测试是针对整个产品系统进行的测试，目的是验证系统是否满足了需求规格的定义，找出与需求规格不相符合或与之矛盾的地方。系统启动选择界面。5.1 系统操作图 5.1.1 系统主界面图 5.1.2生成排序元素图 5.1.3直接插入排序图 5.1.4希尔排序图5.1.5非递归的快速排序图5.1.6递归的快速排序图5.1.7堆排序5.2 测试数据图5.2.1 100个数据元素图5.2.2 1000个数据元素图5.2.3 10000个数据元素图5.2.4、10000