内部排序算法比较讲解.doc

数据结构实验报告 实习6 存储管理、查找和排序 题目:内部排序算法比较 班级：1403011班 姓名：付尧 学号：14030110030 完成日期：2016.1.10 一．需求分析 (1)对起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、归并排序算法进行比较。 (2)待排序的元素的关键字为整数，其中数据要用伪随机产生程序产生，并且至少用5组的输入数据做比较，再使用各种算法对其进行排序，记录其排序时间，再汇总比较。 (3)演示程序以人机对话的形式进行，每次测试完毕显示各种比较指标值，比较次数、移动次数和排序时间的列表，并用条形图即星号表示出来，以便比较各种排序的优劣。 二．概要设计 1. 基本操作： (1) 输入要排序的数据数目 (2) 抽象数据类型定义 typedef struct { int key; }ElemType; //关键字 typedef struct { ElemType *elem; int length; }SqList;//分配顺序存储结构 (3) 存储结构：本程序采用了线性表的顺序存储结构。 (4) 算法设计： 简单选择排序：运用顺序表。时间复杂度O(n2)，空间复杂度O(1)。 起泡排序：时间复杂度O(n2)，空间复杂度O(1) 直接插入排序：时间复杂度O(n2)，空间复杂度O(1) 希尔排序：时间复杂度O(n1.3)，空间复杂度O(1) 快速排序：时间复杂度O(nlog2n)，空间复杂度O(nlog2n) 归并排序：时间复杂度O(nlog2n)，空间复杂度O(n) 2． 本程序包含8个模块： (1)伪随机产生数据模块：本程序要求数据是要用伪随机产生程序产生，再用不同排序算法进行排序。 (2)简单选择排序模块：运用简单选择排序法对伪随机产生的数据进行排序。 (3) 起泡排序模块：运用起泡排序法对伪随机产生的数据进行排序。 (4)直接插入排序模块：运用直接插入排序法对伪随机产生的数据进行排序。 (5)希尔排序模块：运用希尔排序法对伪随机产生的数据进行排序。 (6)快速排序：运用快速排序法对伪随机产生的数据进行排序。 (7)归并排序：运用归并排序法对伪随机产生的数据进行排序。 (8)条形图表示比较结果：统计6种排序算法的比较结果，用条形图表示出来。 三．调试分析 （1）本题采用结构体储存数据，使相关信息紧密相联系，便于编辑和输出。 （2）通过这道题，让我深入理解了内部排序算法，获益良多。调试编码过程中产生的小错误，让我的编程习惯有所改善。 四．用户使用说明 （1）本程序的运行环境为VS2010。 （2）进入演示程序后可得到结果。 五．测试结果 点击运行，首先出现的是要输入伪随机产生数据的数目，如图9所示。 图9 输入界面 输入数据个数然后回车，可显示出不同排序算法的比较次数、移动次数和排序用时。如图10所示。 图10 显示比较结果界面 显示比较次数的条形图。如图11所示。 图11 比较次数条形图界面 显示移动次数条形图。如图12所示 图12 移动次数条形图界面 显示排序用时条形图。如图13所示 图13 排序用时条形图界面 六、附录 #includestdio.h #includestdlib.h #includestring.h #includemath.h #includetime.h #define LIST_INIT_SIZE 30000 int bj1,yd1,n,com,mov; long int A[5],B[5]; double t0,t1,t2,t3,t4,t5,C[5]; clock_t start_t,end_t; typedef struct { int key; }ElemType; typedef struct { ElemType *elem; int length; }SqList; void addlist(SqList L) { int i; a: printf(请输入你要输入的个数:); scanf(%d,n); if(n20000) { printf(超出范围重新输入!!!\n); goto a; } L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem)exit(0); L.length=0; for(i=1;in+1;i++) { b: L.elem[i].key=rand(); if(L.elem[i].key20000)goto b; ++L.length; } } void SelectSort(SqList L)