内部算法性能分析 第1章 前 言
1.3研究方向
排序算法其种类繁多，但还是有一些未解次的问题，例如：选择排序，快速排序，希尔排序，堆排序仍然面临排序后的不稳定性；从而还面临一种稳定的算法也可由不稳定的算法来实现；冒泡排序很容易实现，但是它的时间复杂度和移动次数的问题仍然存在；更让人不可思议的是有些排序这两种缺点都存在；同样每一种排序算法都有它的优缺点，适合于不同的环境。因此，在实际应用中，应根据具体情况进行选择。首先，考虑排序对稳定性的要求，若要求稳定，则只能在稳定的排序方法中选取，否则可以在所有的方法中选取；其次要考虑待排序的序列记录数目n，若n较大则可以在改进的方法中选取，否则在简单方法中选取；然后再考虑其他因素。本文主要是通过排序来从中发现的稳定性、比较次数以及移动次数等问题，从而从性能上分析得出不足并加以改进。
1.4研究方法
基于Visual C++ 6.0平台编程是当今程序者的青睐，它有着强大的性能、完全丰富的工具及高速的处理速度和完备的兼容性。不仅可以简化编程的设计并且算法应用灵活，使应用程序的开发更为简便。C++是为开发大型程序而研制的，它比C语言困难得多，它功能丰富、表达能力强、使用灵活方便、应用面广、目标程序效率高、可移植性好，既具有高级语言的优点，又具有低级语言的许多特点，完全适合于编写系统软件；本人就利用上述C++开发软件编写了《内部排序算法性能分析系统》，采用人机互动的操作模式，系统经过显示主界面功能，然后用户的需要操作，实现了两种排序相互之间的优缺点，从而从中获得一些性能分析结论让人们更好应用各种排序。
1.5结构与安排
本文主要是介绍六种排序的性能分析，首先“前言”对研究背景和研究目的作了简单的介绍；其次“系统功能分析”对本系的说明和讲解；再次“总体设计”对本系统做了一个简要引导，并且通过“总体设计”对该系统的运行懂得差不多了；“详细设计”就是对系统有了详细的设计过程，更进一步知道设计原理；“排序算法的改进” 介绍传统算法的不足，经过设想对原算法加以改进“系统实现及数据测试”不但让我们知道了系统的界面和一些操作的实施，让你知道整个算法的设计并且加以理解。
2
内部算法性能分析 第2章 系统功能分析
第2章 系统功能分析
2.1 需求分析及实现目标
2.1.1应用现状及存在的问题
随着社会的发展，计算机科学技术应用又迈进了一大步，然而在很多的应用过程中不时产生很多错误或延迟，尤其是在钢铁厂、天气预报的预测、火箭的发射等一些大型的场所，这无疑处理器在处理的过程中不能出一些差错，因此就要对那些已编制好的程序的算法要求比较严谨、排序就是其中之一。很多人在运用的过程中对其算法不够了解或者考虑不周，因此给处理器造成了不必的误时。就拿火箭发射来说，如果排序方法性能低下，将是非常危险的。我们将会看到有几个排序算法能够提供某种保证机制，可以消除在最差情况下不可接受的执行性能。
另外存在一个比较大的问题就是排序的稳定性。稳定排序方法保持相等元素的相关顺序。例如，假设有一个学生数组，其中的每一项由学生的姓和其品质总分数组成，根据品质总分数排序。如果排序方法稳定，并且（”balan”,28）开始时位于比(“wang”,28)小的索引位置，排序后(“balan”,28)仍然位于比(“wang”,28)小的索引位置。稳定性可以简化工程开发。例如，假设上面提到的数组已经根据排好序了，有一个根据品质总分数排序的应用程序调用，对于拥有同样品质总分数的学生，他们的顺序还是按字母顺序。稳定排序不需要附加其他确保相同品质总分数的学生按字母顺序排列的工作就可以完成了。因此，对于程序员来说这是必备的重要技能，同时掌握它是他们当前一项急迫的任务。 2.1.2 实现任务
排序数据是由系统随机产生，再通过用户根据自已所需的进行对这六种排序的操作，简洁清晰、容易理解，提高了对该六种排序性能的应用。
用户只需按界面上的提示操作。
这六种排序的性能分析由系统自动的给予分析并且可以看到整个的排序过程(如：移动的次数、比较的次数以及稳定性好坏)
在系统随机产生数据是用户最好是多采用几组数据进行比较这样的正确率要高，同时测试系统的性能好坏。
3
内部算法性能分析 第2章 系统功能分析
2.2可行性分析
所谓可行性分析就是用最小的代价在尽可能短的时间内确定问题是否能够解决。这步工作的主要是要进行一次大大压缩简化了的系统分析和设计的过程，也就是在较高层次上以比较抽象的方式进行系统分析和设计的过程。可行性研究的最根本任务是对以后的行动方针提出建议，以避免时间、资源、人力和金钱的浪费，推荐一个较好的解决方案，并且为工程制定一个初步的计划。 2.2.1技术可行性
本系统采用人机操作进行管理，用visual C++ 6.0进行前台设计、系统随机产生数据，用户通过界面操作，系统自动给予合理分析，由于visual C++ 6.0功能强大、使用的灵活、良好的可扩展性、以及广泛实际应用，充分说明本系统在技术方面的可行性。 2.2.2 工具可行性
软件方面：
信息时代对于软件的应用已不是人们的难题，人们在日常办公中用的计算机操作的系统等都属于软件部分。
硬件方面：
计算机普及到今天，人们对于它的拥有已不少见，它的硬件设备完全能够满足人们的需求，而价格也能被人们所接受。 2.2.3 经济可行性
这是个超小型的性能分析系统，从投入的人力，财力与物力来讲是非常之小的，只要一台电脑，一台打印机，这个系统就可以搞起来，考虑到学校里有电脑，现只要购置一台打印机就可以了。从节省人力方面，可以让管理人员从繁与复杂的工作中解脱出来，做更多的工作，可以给读者提高到更深的一个层次。 2.2.4 操作可行性
本系统设计清晰，有良好的用户接口，操作简洁，完全可以给用户解决，并达到操作过程中的直观、方便、实用、安全等要求，因此操作方面具有可行性。
4
内部算法性能分析 第3章 总体设计
第3章 总体设计
3.1设计需求及描述
3.1.1设计问题描述
设计一个测试程序比较起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法的关键字比较次数和移动次数以取得直观感受。待排序表的表长不小于10，表中数据随机产生，至少用5组不同数据作比较，比较指标有：关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动）。最后输出比较结果.
3.1.2 设计需求分析
用数组S来存放系统随机产生的100个数据，并放到R数组中，数据由程序随机产生，用户只需查看结果。
利用全局变量times和changes来分别统计起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法的比较次数和移动次数，然后输出结果，并在每一次统计之后，将times和changes都赋值为0。
在主函数中调用用户自定义函数，输出比较结果。
本程序是对几种内部排序算法的关键字进行性能分析的程序，它分为以下几个部分：a、建立数组；b、调用函数求比较和移动次数；c、输出结果。 3.1.3 系统设计的实质功能
用户启动该系统进入主菜单，在主菜单中有三个菜单命令，可以按照用户的意愿来选择他想要的命令
当你选择“排序内部操作过程”菜单时，即可进入一下子菜单，你可以看到这六种排序的内部排序过程，并且可以知道这六种排序具体的移动次数、比较次数以及稳定性的好坏。
当你选择“排序性能分析”菜单时，马上进入下一级子菜单，你可以知道这六种排序之间的一些性能相关的知识，这一级菜单是用户来安排，如果不知道那两种排序的性能那种占优势好一些，你可以输入排序的编号，然后系统给你分析，给出结论。
5
内部算法性能分析 第3章 总体设计
3.2 设计原理与设计内容
3.2.1系统总体结构 内部排序算法性能分析 系统总体结构如图4.1所示：
图3.1 系统总体结构
冒泡排序 希尔排序 直接插入排序 堆排序 简单选择排序 快速排序 冒泡性能分析 希尔性能分析 插入性能分析 选择性能分析 快速性能分析 堆性能分析 排序过程模块 性能分析模块 3.2.2“内部操作过程”菜单设计原理如图所示。
Point()开 始 Switch()进行判断 Bubblesort（）函数进行直接排序 partition()函数进行快速排序 Shllinsert()函数进行希尔排序 Selectsort()函数进行简单选择排序 Heapsort()函数进行堆排序 Insertsort()函数进行直接排序 子函数结束 图3.2“内部操作过程”菜单
6