数据结构内部排序算法比较

发布 2021-05-30 13:27:28 阅读 8957

目录。摘要 1

1绪论 12系统分析 1

2.1 功能需求 1

2.2数据需求 1

2.3 性能需求 2

3总体设计 2

3.1系统设计方案 2

3.2功能模块设计 2

4详细设计 3

4.1 数据结构定义 3

4.2伪随机产生数据模块 4

4.3简单选择排序模块 6

4.4起泡排序模块 7

4.5直接插入排序模块 8

4.6希尔排序模块 9

4.7快速排序模块 10

4.8归并排序模块 11

4.9条形图模块 12

5调试与测试 13

5.1 调试 13

5.2 测试 13

6结论 14

结束语 14

参考文献 15

附录1-用户手册 16

附录2-源程序 18

随着科技的快速发展,越来越多的企业不再浪费人力财力去计算一些统计性结果,而是应用一些简单的程序或系统来完成这些任务。随着学习数据结构课程的深入,了解了不同排序算法的不同排序方法,每种排序对数据的比较次数、移动次数和排序用时都是不同的,本程序实现了六种内部排序算法的比较,并用条形图直观的显示出各种算法的优劣。运用伪随机产生的数据,调用六种排序算法,记录其比较次数、移动次数和排序时间,再分别用条形图(星号表示)表示出来。

1)对起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、归并排序算法进行比较。

2)待排序的元素的关键字为整数,其中数据要用伪随机产生程序产生,并且至少用5组的输入数据做比较,再使用各种算法对其进行排序,记录其排序时间,再汇总比较。

3)演示程序以人机对话的形式进行,每次测试完毕显示各种比较指标值,比较次数、移动次数和排序时间的列表,并用条形图即星号表示出来,以便比较各种排序的优劣。

抽象数据类型:线性表、排序算法。

(1) 输入数据:需要比较的数据数目。

2) 输出数据:不同算法的比较次数、移动次数、排序时间的数据以及对应的条形图。

在运行本程序时,只要按照正确的操作方法不会出现无法运行的情况,系统稳定性好,安全,可靠,响应速度由需比较的数字数目多少来决定。

(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)

根据分析整个程序主要划分为8个功能模块,分别执行要求中的功能。1个产生伪随机数据模块、6个内部排序算法模块以及1个形成条形图模块。功能模块图如图1所示。

图1功能模块图。

1)伪随机产生数据模块:本程序要求数据是要用伪随机产生程序产生,再用不同排序算法进行排序。

2)简单选择排序模块:运用简单选择排序法对伪随机产生的数据进行排序。

3) 起泡排序模块:运用起泡排序法对伪随机产生的数据进行排序。

4)直接插入排序模块:运用直接插入排序法对伪随机产生的数据进行排序。

5)希尔排序模块:运用希尔排序法对伪随机产生的数据进行排序。

6)快速排序:运用快速排序法对伪随机产生的数据进行排序。

7)归并排序:运用归并排序法对伪随机产生的数据进行排序。

8)条形图表示比较结果:统计6种排序算法的比较结果,用条形图表示出来。

typedef struct

int key;

elemtype; /关键字。

typedef struct

elemtype *elem;

int length;

sqlist;//分配顺序存储结构。

伪随机产生数据模块可实现伪随机产生不同数目的数据以供排序,运用顺序存储结构来实现的。该模块具体实现程序流程如图2所示。

图2 伪随机产生数据模块。

简单选择排序模块可实现用简单排序法对产生的数据进行排序。该模块具体实现程序流程如图3所示。

图3 简单选择模块。

起泡排序模块可实现运用起泡排序法对数据进行排序,该模块具体实现程序流程如图4所示。

图4 起泡排序模块。

直接插入排序模块可实现运用直接插入排序法对数据进行排序,该模块具体实现程序流程如图5所示。

图5 直接插入排序模块。

希尔排序模块可实现运用希尔排序法对数据进行排序,该模块具体实现程序流程如图6所示。

图6 希尔排序模块。

快速排序模块可实现用快速排序法对数据进行排序,该模块具体实现程序流程如图7所示。

图7 快速排序模块。

归并排序模块可实现用归并排序法对数据进行排序,该模块具体实现程序流程如图8所示。

图8 归并排序模块。

条形图模块可用星号显示出各种算法排序的比较结果,该模块具体实现程序流程如图9所示。

图9 条形图模块。

调试过程主要是运行编制好的程序,然后遇到错误后根据系统的提示,找到相关的问题所在。本系统调试过程中遇到的主要问题、原因和解决方法如下面介绍。

1)问题:用条形图表示时,不能根据数据而表示出星号的多少。

解决办法:选择要表示的数据最小的一种排序作为基数,每种排序所要比较的数据可运用数**算计算出是基数的多少倍,从而输出几个星号。

2)问题:输入数据数目为2个时程序运行错误。

原因:待比较的数据为2个时,作为基数的那种排序的数据为0,不能做分母,所以会出现运行错误。

解决方法:输入较大的数,使要用条形图表示出来的数据不为0即可。

软件测试是软件生存期中的一个重要阶段,是软件质量保证的关键步骤从用户的角度来看,普遍希望通过软件测试暴露软件中隐藏的错误和缺陷,所以软件测试应该是“为了发现错误而执行程序的过程”。或者说,软件测试应该根据软件开发各阶段的规格说明和程序的内部结构而精心设计一批测试用例(即输入数据及其预期的输出结果),并利用这些测试用例去运行程序,以发现程序错误或缺陷。过度测试则会浪费许多宝贵的资源。

到测试后期,即使找到了错误,然而付出了过高的代价。

测试数据过程如下。

(1) 输入功能测试。

输入数据1:100

预期结果:输出各排序算法的比较次数、移动次数和排序用时,随后输出数据比较所对应的条形图。

运行结果:输出各排序算法的比较次数、移动次数和排序用时,随后输出数据比较所对应的条形图。

说明:预期和运行结果相同。

输入数据2:25000

预期结果:输出各排序算法的比较次数、移动次数和排序用时,随后输出数据比较所对应的条形图。

运行结果:超出范围重新输入!

说明:不能输入比25000大的数。

2)输出功能测试。

输入数据1:200

预期结果:输出各排序算法的比较次数、移动次数和排序用时,随后输出数据比较所对应的条形图。

运行结果:输出各排序算法的比较次数、移动次数和排序用时,随后输出数据比较所对应的条形图。

说明::预期和运行结果相同。

输入数据2:4

预期结果:输出各排序算法的比较次数、移动次数和排序用时,随后输出数据比较所对应的条形图。

运行结果:在输出移动次数比较的条形图时出现运行错误。

说明:不能输入比5小的数。

经过这一段时间的程序设计,该课设任务书中题目所要求的功能也都一一实现。可以伪随机产生不同的数据,六种内部排序算法对其数据进行排序,记录比较次数、移动次数和排序用时,并用条形图直观的表示出不同算法的优劣。不过本程序还可以添加细节,例如:

可输出个选择排序方法的菜单,挑选不同排序方法对数据进行比较,也可以再循环选择并用条形图表示出来。

数据结构内部排序比较分析

数据结构实训报告。实验名称 数据结构。题目 内部排序比较。专业班级 姓名 学号 实验日期 一 实验目的 通过随机数据比较各内部排序算法的关键字比较次数和关键字移动的次数,以取得直观感受。训练学生综合设计算法能力。二 实验要求 待排序长度不小于100,数据可有随机函数产生,用五组不同输入数据做比较,比...

数据结构课设 排序算法比较

6 排序算法比较 必做 设计要求 利用随机函数产生n个随机整数 n 500,1000,1500,2500,30000 利用直接插入排序 折半插入排序,起泡排序 快速排序 选择排序堆排序,基数排序七种排序方法。可添加其它排序方法 进行排序 结果为由小到大的顺序 并统计每一种排序所耗费的时间。各个函数均...

数据结构中各种排序算法比较

1快速排序 quicksort 快速排序是一个就地排序,分而治之,大规模递归的算法。从本质上来说,它是归并排序的就地版本。快速排序可以由下面四步组成。1 如果不多于1个数据,直接返回。2 一般选择序列最左边的值作为支点数据。3 将序列分成2部分,一部分都大于支点数据,另外一部分都小于支点数据。4 对...