内部排序算法的比较分析与实现.doc-资料库

第1页 / 共29页

第2页 / 共29页

第3页 / 共29页

第4页 / 共29页

第5页 / 共29页

第6页 / 共29页

第7页 / 共29页

第8页 / 共29页

李镜子《内部排序算法的比较分析与实现》第１页共 29 页内部排序算法的比较分析与实现学生姓名：李镜子指导老师：肖增良摘要该程序是用 C 语言设计、实现一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受：在程序中随机生成 N 个数据，对这些数进行多种方法的排序，所用的这些排序方法都是在数据结构课中学习过的比如：插入排序、快速排序、冒泡排序等，而且还要对各个排序做出相应的比较。演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”下，用户可由键盘输入待排序表的表长和不同的测试数据的数组，每次测试完毕，列表显示各种比较指标值。最后对结果作出简单分析，包括对各组数据得出结果波动大小给予解析。关键词内部排序；C 语言；比较次数；关键字 1 引言 1.1 课题背景随着信息时代的到来，各种信息日益丰富，信息迅速膨胀，加之学校规模的扩大，对学生成绩信息的管理已经成为学校中重要的一环。在信息化未到来之前，都是采用人工管理学生成绩的相关信息。但是随着市场经济的飞速发展，各种信息越来越繁杂。人工管理学生成绩信息已经远远不能满足学校的需求。特别是对一些规模大的学校来说，实现对学生成绩高效、准确的管理是十分重要的。人工管理不仅速度慢而且容易出错。这些大大的降低了学校管理的效率，甚至会因一些错误造成不必要的麻烦。所以通过建立一个完整，透明，一致，高效，易查的学生成绩管理系统可以实现对学生成绩的有效管理，大大的提高学校的管理效率。数据结构是指相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。数据的逻辑结构(logical structure)是指数据元素之间逻辑关系的整体。所谓逻辑关系是指数据元素之间的关联方式或邻接关系。根据数据元素之间逻辑关系的不同，数据结构分为四类：集合；线性结构；树结构；图结构。数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式。为了区别于数据的存储结构，常

李镜子《内部排序算法的比较分析与实现》第２页共 29 页常将数据的逻辑结构称为数据结构。数据的存储结构(storage structure)又称为物理结构，是数据及其逻辑结构在计算机中的表示，换言之，存储结构除了数据元素之外，必须隐式或显示地存储数据元素之间的逻辑关系。通常有两种存储结构：顺序存储结构和链接存储结构[1]。线性表是一种最基本、最简单的数据结构，简称表，是具有零个或多个具有相同类型的数据元素的优先序列，这些数据元素之间仅具有单一的前驱和后继关系。线性表中的元素具有抽象（即不确定）的数据类型，在设计具体的应用程序时，数据元素的抽象类型将被具体的数据类型所取代。线性表的存储结构主要有顺序存储结构和链接存储结构（即顺序表和单链表）[1]。以顺序表为存储结构 typedef struct { int key; int K[5]; int next; /*关键字*/ /*关键字的数字组合*/ /*下一个元素的位置*/ }RedType; 定义存储结构的数据元素。 typedef struct { r[MAXSIZE+1]; RedType int length; /*数据元素数组*/ /*数据元素的个数*/ }SqList; 定义指向存储结构的数据类型包括存储结构的数组和数据元素的个数。结构如图 1.1 所示：图 1.1 顺序表的结构图文件是程序设计中的一个重要概念。所谓“文件”，一般是指存储在外部介质上的数据的集合。一批数据是以文件的形式存放在外部介质上的。操作系统是以文件为单位对数据进行管理的。要向外部介质上存储数据也必须先建立一个文件（以文件名为标识），才能向它输出数据。对用户来说，常用到的文件有两大类，一类是程序文件（program file）,

李镜子《内部排序算法的比较分析与实现》第３页共 29 页如 C++的源程序文件、目标文件、可执行文件等。一类是数据文件，在程序运行时，常常需要将一些数据（运行的最终结果或中间数据）输出到磁盘上存放起来，以后需要时再从磁盘中输入到计算机内存。这种磁盘文件就是数据文件。程序中的输入和输出的对象就是数据文件[2]。 1.2 问题描述设计、实现一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受，对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较，他们的时间复杂度分别为 O(n2)、O(n2)、O(n2)、O(nlog2n)、O(n1.3)、O(nlog2n)。演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”下，用户可由键盘输入待排序表的表长和不同的测试数据的数组，每次测试完毕，列表显示各种比较指标值。最后对结果作出简单分析，包括对各组数据得出结果波动大小给予解析。 2.1 相关原理 2 需求分析 (1)直接插入排序（Straight Insertion Sort）[1]是一种最简单的排序方法，它的基本操作是将一个纪录插入到已排好序的有序表中，从而得到一个新的、纪录数增 1 的有序表。 (2)希尔排序（shell’s sort）[2]又称“缩小增量排序”，它也是一种属插入排序类的方法，但在时间效率上较前述排序方法有较大改进。它的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。希尔排序的一个特点是：子序列的构成不是简单的“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列。 (3)冒泡排序（bubble sort）[3]的过程很简单。首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。依次类推，直至第 n-1 个记录和第 n 个记录的关键字进行比较为止。上述过程称做第一趟冒泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上。然后进行第二趟冒泡排序，对前 n-1 个记录进行同样操作，其结果是使关键字次大的记录被安置到第 n-1 个记录的位置上。一般地，第 i 趟冒泡排序是从 L.r[1]到 L.[n-i+1]

李镜子《内部排序算法的比较分析与实现》第４页共 29 页依次比较相邻两个记录的关键字，并在“逆序”是交换相邻记录，其结果是这 n-i+1 个记录中关键字最大的纪录被交换到第 n-i+1 的位置上。整个冒泡排序过程需进行 k（1<=k

李镜子《内部排序算法的比较分析与实现》第５页共 29 页程序输出的是对六种排序做的一些比较，即输出六种排序各排序过程中所比较的数据的个数，交换的数据的次数，和排序完成所用的时间。六种排序依次在计算机终端上显示，便于用户观察。输入值的范围等价于程序中随机生成的数据的个数，即待排序表的表长不小于 100，至少要用 5 组不同的输入数据体比较，比较的指标为：有关键字参加的比较次数和关键字的移动次数（关键字交换计为 3 次的移动），在该程序中，随机生成的数据个数被初始化为了 10000，数据越大就越容易比较。 2.3 任务功能亲自动手结合数据机构相关知识，利用 C 语言设计、实现内部排序算法的性能分析系统：输入 N 个随机整数，对这些数进行多种方法进行排序，并对这些排序做比较，在屏幕上输出每种排序方法所比较的次数，交换的次数，和用掉的时间。任意性：系统首先生成 10000 个随机整数，然后分别用不同的排序方法对其进行升序排序，给出每种方法的比较次数或所用时间。友好性：界面要友好，输入有提示，尽量展示人性化；可读性：源程序代码清晰、有层次；健壮性：用户输入非法数据时，系统要及时给出警告信息；按要求画出程序流程图、编写程序代码、运行测试。 2.4 运行环境 (1)WINDOWS2000/XP 系统 (2)TC 或 VC 编译环境 2.5 开发工具 C 语言与数据结构 3.1 程序所需的抽象数据类型 typedef struct StudentData 3 概要设计

李镜子《内部排序算法的比较分析与实现》第６页共 29 页 { int num; //存放关键字，如零时变量，还有哨兵 }Data; typedef struct LinkList { int Length; //存放随机数的个数 Data Record[MAXSIZE];//用数组存放所有的随机数 }LinkList 3.2 系统功能模块 (1)外部功能模块图内部排序排序的比较 rando mnu mbers 随机生成数据 Setlin klist 初始化链表 Shells ort 希尔排序 Quick Sort 快速排序 Heap Sort 堆排序 Bubbl eSort 冒泡排序 SelSo rt 选择排序 Comp are 比较所有排序 (2)主函数功能模块图图 3.1 外部功能模块图主函数 main（）

李镜子《内部排序算法的比较分析与实现》第７页共 29 页图 3.2 主函数功能模块图 4 详细设计 4.1 整个程序的流程图开始界面 Compare 比较各排序

李镜子《内部排序算法的比较分析与实现》第８页共 29 页图 4.1 整个程序的流程图 4.2 具体代码实现 (1) 直接插入排序直接插入排序的基本思想是：从初始有序的子集合开始，不断地把新的数据元素插入到已排列有序的子集合的合适位置上，使子集合中数据元素的个数不断增多，当子集合等于集合时，直接插入排序算法结束。直接插入排序的基本思想是：顺序地把待插入的数据元素按其关键字的大小插入到已排序数据元素子集合的适当位置。子集合的数据元素个数从只有一个数据元素开始逐次增

资料库

内部排序算法的比较分析与实现.doc

相关推荐

开发技术

热门标签

最新资料