数据结构课程设计报告-内部排序算法的性能分析.doc

数 据 结 构课程设计报告设计题目: 内部排序算法的性能分析 学 校： 院 系： 专业班级： 学生姓名： 指导教师： 2012年5月17日 内部排序算法的性能分析 目录1. 设计内容 1 1.1问题描述 1 1.2设计要求 1 1.3开发环境 1 1.4研究思路 12. 设计步骤 3 2.1需求分析 3 2.2概要设计 3 2.3详细设计 5 2.4调试分析 12 2.5测试结果 153. 设计成果展示 16 3.1用户手册 16 3.2程序运行部分截图 164. 总结与心得体会 225.参考文献23附录关键代码 24 内部排序算法的性能分析 1.设计内容1.1问题描述设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数。1.2设计要求(1)对起泡排序、直接排序、折半排序、快速排序、希尔排序、归并排序算法进行比较；(2)待排序表的表长不小于100，表中数据随机产生，至少用5组不同数据作比较，比较指标有：关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动）；(3)输出比较结果。1.3开发环境VC+6.01.4研究思路 采用C语言中的rand()函数随机生成100-200个数，存入一个一维数组中，然后将数组中的值通过循环赋值给Sqlist L，注意L.r0.key不要赋值，因为在排序中L.r0.key时常作为一个哨兵，用来存放一些关键字。然后通过函数调用，分别进行直接插入排序，折半排序，希尔排序，起泡排序，快速排序，和归并排序，即：InsertSort(&L1);直接插入排序BInsertSort(&L2);折半排序ShellInsert(&L3,i);希尔排序Qipaosort(&L6);起泡排序Quicksort(&L4);快速排序MergeSort(&L5);归并排序通过以上函数的调用，可以将初始的每个Sqlist L，分别排序为一个从小到大的序列，然后通过循环操作，将每个经过排序后的序列输出至屏幕，并且将一些关键字比较次数，关键字移动次数输出至屏幕。接着进行写文件操作，并将该文件命名为“paixu.txt”将排序的结果通过文件的方式进行存储，并将关键字移动，关键字比较的信息写入文件，便于最后的对内部排序各种方法的分析与总结，可以以图和表的形式进行分析。22.设计步骤2.1需求分析2.1.1程序的基本功能：通过计算机随机生成100-200个随机数，利用直接插入排序，折半排序，希尔排序，起泡排序，快速排序，以及归并排序六种方法进行排序，并统计每一种排序的关键字移动次数，关键字参与比较次数，最后进行数据分析。2.1.2程序的实际意义及背景：排序是计算机程序设计中的一种重要操作。它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。内部排序方法很多，但我们无法确定哪一种方法是最好的，每一种方法都有各自的缺点与优点，适合在不同的环境下使用。本课程设计通过直接插入排序，折半排序，希尔排序，起泡排序，快速排序，以及归并排序六种方法的性能比较，让我们更好地掌握这些排序的基本思想及排序算法，加深我们队各种数据结构的逻辑结构，存储结构的理解。2.1.3本课程设计目标：用至少5组100200的随机数据对每种方法做测试与比较，最后通过图或者表的形式汇总数据，对这些内部排序算法进行性能分析。2.2概要设计2.2.1所需的ADT(抽象数据类型)：typedef int KeyType;/元素类型typedef structKeyType key;RedType;typedef structRedType rMAXSIZE+1;int length;Sqlist;/顺序表类型2.2.2原始数据：由c语言中的rand()函数随机生成，为了使随机生成的每组数据不同，我们需要在生成数据之前，获得一个种子，所谓种子，它的作用是使生成的每一组随机数均为不同的数据，若获得一个种子，那么每一组数据最后生成的都一样，就无法达到真正的随机，也无法对排序的性能进行分析。#define SIZE 100/其中100可以改为100200之间的任意整数，即/代表参与比较的随机数的数量int ASIZE;srand(unsigned) time(NULL); /生成随机数种子for (i=1;i=SIZE;i+)Ai-1=rand()%200;L1.length+;L2.length+;L3.length+;L4.length+;L5.length+;L6.length+;2.2.3输出数据：主程序通过屏幕显示以及文件存储的形式对排序的序列以及关键字移动次数，关键字参加比较次数等信息进行输出。主程序随机数的生成随机数以数组形式存储直接插入排序折半排序希尔排序起泡排序快速排序归并排序记录关键字比较和移动的次数输出随机生成的序列和每个经过排序后的序列，以及关键字比较移动次数将以上信息以文件的形式保存结束程序2.3详细设计2.3.1主程序设计：2.3.2系统模块划分以及模块功能：主要分为两个模块：1、主程序模块：int main()2、排序模块：A. InsertSort(&L1);直接插入排序B. BInsertSort(&L2);折半排序C. ShellInsert(&L3,i);希尔排序D. Qipaosort(&L6);起泡排序E. Quicksort(&L4);快速排序 void Qsort(Sqlist *L,int low,int high)F. MergeSort(&L5);归并排序 void Merge (RedType SR, RedType TR, int i, int m, int n) void MSort(RedType SR, RedType TR1, int s, int t)2.3.3六种排序的基本思想：1、直接插入排序待排序的记录放在数组R0n-1中排序过程中某一时刻，R被划分成两个子区间R0i-1 (有序和)Rin-1(无序)。直接插入的基本操作是将当前无序区的一个记录Ri插入到有序区R0i-1中适当的位置。2、折半排序：利用“折半查找”为查找方式的排序方法。3、希尔排序：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。4、起泡排序：相邻的两个元素进行比较，将小的调到前面，大的调到后面。5、快速排序：在待排序的数组的n个元素中取一个元素(一般取第一个)，将其移动到这样的位置：在其之前的元素的值都小于它，在其之后的元素都大于它，这样是一趟快速排序；然后对数组的两个部分进行同样的操作，直到每部分只有一个记录为止；总之，每趟使表的第一个元素放在适当位置，将表两分，再对两子表进行同样的递归划分，直至划分的子表长度为1。6、归并排序：将两个或两个以上的有序表组成一个新的有序表。2.3.4 部分算法流程图：1.直接插入排序流程图：输入随机无序数据L选取第一个数为关键字i0Y，dk-进行希尔排序N输出排序后序列L排序结束希尔排序算法流程图3.快速排序流程图(递归算法)：输入随机无序数据Llowr0 = L-rlow; / 用子表的第一个记录作枢轴记录 pivotkey = L-rlow.key; / 枢轴记录关键字 while (lowhigh) / 从表的两端交替地向中间扫描while (lowrhigh.key=pivotkey) B3+;-high;temp=L-rlow.key ;L-rlow.key=L-rhigh.key;L-rhigh.key=temp; Y3+;/ 将比枢轴记录小的记录移到低端while (lowrlow.keyrlow.key;L-rlow.key=L-rhigh.key;L-rhigh.key=temp; Y3+;/ 将比枢轴记录大的记录移到高端 L-rlow = L-r0; Y3+;/ 枢轴记录到位 return low; void Qsort(Sqlist *L,int low,int high)int pivotloc;int low1,high1;int j,k;low1=low;high1=high; if (low1length);2. 归并排序：void Merge (RedType SR, RedType TR, int i, int m, int n) / 将有序的SRi.m和SRm+1.n归并为有序的TRi.n int j,k; for (j=m+1, k=i; i=m & j=n; +k) / 将SR中记录由小到大地并入TR B4+; if (SRi.keySRj.key) TRk = SRi+; Y4+; else TRk = SRj+; Y4+; if (i=m) / TRk.n = SRi.m; 将剩余的SRi.m复制到TR while (k=n & i=m) TRk+=SRi+; Y4+; if (j=n) / 将剩余的SRj.n复制到TR while (k=n &j r, L-r, 1, L-length); / MergeSort3.关键头文件：#include4.写文件操作：fp=fopen(paixu.txt,a);/打开文件/fprintf(fp,-第%d次比较-,k);/k+;fprintf(fp,n);fprintf(fp,生成的随机数列为：n);for (i=1;i=SIZE;i+)fprintf(fp,%3d ,Ai-1);fprintf(fp,n);fprintf(fp,直接插入排序后的数列为：n);for(i=1;i=SIZE;i+)fprintf(fp,%3d ,L1.ri.key);fprintf(fp,n);fprintf(fp,n折半排序后的数列为：n);for(i=1;i=SIZE;i+)fprintf(fp,%3d ,L2.ri.key);fprintf(fp,n);fprintf(fp,n希尔排序后的数列为：n);for(i=1;i=SIZE;i+)fprintf(fp,%3d ,L3.ri.key);fprintf(fp,n);fprintf(fp,n起泡排序后的数列为：n);for(i=1;i=SIZE;i+)fprintf(fp,%3d ,L4.ri.key);fprintf(fp,n);fprintf(fp,n快速排序后的数列为：n);for(i=1;i=SIZE;i+)fprintf(fp,%3d ,L5.ri.key);fprintf(fp,n);fprintf(fp,n归并排序后的数列为：n);for(i=1;i=SIZE;i+)fprintf(fp,%3d ,L6.ri.key);fprintf(fp,n);fprintf(fp,各排序算法的关键字比较次数和移动次数的比较n);fprintf(fp,直接插入排序关键字比较次数和移动次数分别为：%5d%5d,B0,Y0);fprintf(fp,n);fprintf(fp,折半排序关键字比较次数和移动次数分别为： %5d%5d,B1,Y1);fprintf(fp,n);fprintf(fp,希尔排