数据结构课程设计----内部排序算法性能分析

《数据结构课程设计----内部排序算法性能分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、课程名称：数据结构本科学生课程设计（论文）题目内部排序算法性能分析姓名学号7680学部计算机科学与技术专业、年级计科1003指导教师2011年12月24日摘要排序是计算机科学中基本的研究课题之一,其目的是方便记录的查找、插入和删除.通过描述冒泡、选择、插入、堆和快速6种排序算法，内部排序其算法灵活方便，因此成为了程序算法中一个必不可少的应用，所以在应用之前要经过严谨的思考才不会出错，不会造成计算机运算速度的延迟，才会完全发挥内部排序的性能。内部排序的方法种类繁多，但就其全面性能而言，很难提出一种被认为是最好的方法。但就其全面性能而言，很难提出一种被认为是最

2、好的方法，每一种方法都有各自的优缺点，适合不同的环境（如记录的初始排序列状态等）下使用。如果安排序过程中依据的不同原则对内部排序方法进行分类，则大致可分为插入排序、交换排序，选择排序，归并排序和计数排序等五类；如果按内部排序过程中所需要的工作量来区分，则可分为3类：（1）简单的排序方法，该时间复杂度为O(n*n)；（2）先进的排序方法，该时间复杂度为O（nlogn）；（3）基数排序，其时间复杂度为O（d*n）；主要介绍非常实用而算法又容易接受的的这六类排序。由于很多人在使用的过程中，不知道那种排序适合他们的程度设计，因此导致该算法没有得到充分的应用，起泡排

3、序最简单的排序，很容易写出代码，但运算时间复杂度稍长一些；直接排序能够很快的最大和最小的数据，但假如数据较多，操作比较繁琐；简单选择排序稳定比较次数与起泡排序一样，则相对之还要慢；快速排序速度快，数据移动少，平均性能比较好，但是性能不稳定；希尔排序是插入算法的改进，由于多次的插入造成了其稳定性不好；堆排序在最坏情况下时间复杂度也为O(nlogn)，并且它仅需一个记录大小供交换用的辅助存储空间，但在记录数较少时不提倡使用；但本文主要介绍这6类排序（起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序）一些优点和缺陷，对缺陷加以改进。通过对传统算法的性

4、能分析，发现其中的缺陷，对算法的设想来弥补中间的不足，以致算法的性能有所提高。关键字:数据结构、内部排序、算法改进、性能分析目录第1章前言11.1分析问题11.2研究背景11.3研究方向21.4研究方法21.5结构与安排2第2章系统功能分析32.1需求分析及实现目标32.1.1应用现状及存在的问题32.1.2实现任务32.2可行性分析42.2.1技术可行性42.2.2工具可行性42.2.3经济可行性42.2.4操作可行性4第3章总体设计53.1设计需求及描述53.1.1设计问题描述53.1.2设计需求分析53.1.3系统设计的实质功能53.2设计原理与设计

5、内容63.2.1系统总体结构63.2.2“内部操作过程”菜单设计原理如图所示。63.2.2“排序性能分析”菜单设计原理73.2.3设计内容7第4章详细设计94.1冒泡排序94.2直接插入排序104.3希尔排序114.4简单选择排序134.5快速排序144.6堆排序164.7六种排序方法讨论18第5章排序算法的改进205.1双向冒泡排序算法205.2双倍快速排序的算法215.3选择排序的算法225.4堆排序的改进算法24第六章系统实现及数据测试296.1主界面296.2“排序内部操作过程”菜单296.2.1当用户输入0-6的数字时则会随意的进入下一级子菜单3

6、06.2.2输入“2”进行“希尔”排序306.3“性能分析”菜单316.3.1当用户输入“1”时进行“插入与希尔”排序之间的性能分析比较316.3.2当用户输入“1”时进行“插入与冒泡”排序之间的性能分析比较32总结33参考文献34内部算法性能分析第1章前言第1章前言1.1分析问题排序是指将一个数据元素序列排列成一个有序列的过程。排序是计算机的一个重要的领域，并广泛应用于数据处理、情报检索、商业金融及企业管理等许多方面。资料表明，在当今计算机系统中，花费在排序上的时间占了系统运行的时间的很大比重。相当多的计算机中，有50%以上的CPU时间是用在排序数据上的

7、。因此为了提高计算机系统的工作效率，研究和发展更有效的排序算法的十分重要的。目前人们已经提出了许多不同的排序算法，然而如果在不适应的场合的应用，那么其平均时间(averageTime)和最差时间(worstTime)就会不理想，其排序算效率就会大大的降低，如国防系统和生命支持系统，如果排序方法性能低下，将会令我们大大的失望。另外用来衡量排序算法的标准是稳定性，在那些比较复杂的排序中其稳定性不是很好，容易程序出错，就这样造成我们计算机的运算时间加长和内存地址的浪费。1.2研究背景由于排序是数据结构中的重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种

8、排序算法的时间消耗对于实际应用当中很有必要通过分析实际结合算法的特