课程名称：数据结构
本科学生课程设计（论文）
题 目 内部排序算法性能分析 姓 名 阳 明 学 号 104328318117680 学 部 计算机科学与技术 专业、年级 计科1003 指 导 教 师 刘 琼
2011年12月24日
湖南涉外经济学院本科课程设计（论文）
摘 要
排序是计算机科学中基本的研究课题之一,其目的是方便记录的查找、插入和删除.通过描述冒泡、选择、插入、堆和快速6种排序算法，内部排序其算法灵活方便，因此成为了程序算法中一个必不可少的应用，所以在应用之前要经过严谨的思考才不会出错，不会造成计算机运算速度的延迟，才会完全发挥内部排序的性能。
内部排序的方法种类繁多，但就其全面性能而言，很难提出一种被认为是最好的方法。但就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合不同的环境（如记录的初始排序列状态等）下使用。如果安排序过程中依据的不同原则对内部排序方法进行分类，则大致可分为插入排序、交换排序，选择排序，归并排序和计数排序等五类；如果按内部排序过程中所需要的工作量来区分，则可分为3类：（1）简单的排序方法，该时间复杂度为O(n*n)；（2）先进的排序方法，该时间复杂度为O（nlogn）；（3）基数排序，其时间复杂度为O（d*n）；主要介绍非常实用而算法又容易接受的的这六类排序。
由于很多人在使用的过程中，不知道那种排序适合他们的程度设计，因此导致该算法没有得到充分的应用，起泡排序最简单的排序，很容易写出代码，但运算时间复杂度稍长一些；直接排序能够很快的最大和最小的数据，但假如数据较多，操作比较繁琐；简单选择排序稳定比较次数与起泡排序一样，则相对之还要慢；快速排序速度快，数据移动少，平均性能比较好，但是性能不稳定；希尔排序是插入算法的改进，由于多次的插入造成了其稳定性不好；堆排序在最坏情况下时间复杂度也为O(nlogn)，并且它仅需一个记录大小供交换用的辅助存储空间，但在记录数较少时不提倡使用；
但本文主要介绍这6类排序（起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序）一些优点和缺陷，对缺陷加以改进。通过对传统算法的性能分析，发现其中的缺陷，对算法的设想来弥补中间的不足，以致算法的性能有所提高。
关键字: 数据结构、内部排序、算法改进、性能分析
目 录
第1章 前 言.............................................................................................................. 1 1.1分析问题............................................................................................................. 1 1.2研究背景.............................................................................................................. 1 1.3研究方向.............................................................................................................. 2 1.4研究方法.............................................................................................................. 2 1.5结构与安排.......................................................................................................... 2 第2章 系统功能分析.................................................................................................. 3 2.1 需求分析及实现目标 ......................................................................................... 3 2.1.1应用现状及存在的问题............................................................................. 3 2.1.2 实现任务.................................................................................................... 3 2.2可行性分析.......................................................................................................... 4 2.2.1技术可行性................................................................................................. 4 2.2.2 工具可行性................................................................................................ 4 2.2.3 经济可行性................................................................................................ 4 2.2.4 操作可行性................................................................................................ 4 第3章 总体设计.......................................................................................................... 5 3.1设计需求及描述.................................................................................................. 5 3.1.1设计问题描述............................................................................................. 5 3.1.2 设计需求分析.......................................................................................... 5 3.1.3 系统设计的实质功能................................................................................ 5 3.2 设计原理与设计内容 ......................................................................................... 6 3.2.1系统总体结构............................................................................................. 6 3.2.2“内部操作过程”菜单设计原理如图所示。.......................................... 6 3.2.2“排序性能分析”菜单设计原理.............................................................. 7 3.2.3设计内容..................................................................................................... 7 第4章 详细设计.......................................................................................................... 9 4.1冒泡排序.............................................................................................................. 9 4.2直接插入排序.................................................................................................... 10 4.3希尔排序............................................................................................................ 11 4.4简单选择排序.................................................................................................... 13 4.5快速排序............................................................................................................ 14 4.6堆排序................................................................................................................ 16
4.7六种排序方法讨论............................................................................................ 18 第5章 排序算法的改进............................................................................................ 20 5.1双向冒泡排序算法............................................................................................ 20 5.2双倍快速排序的算法........................................................................................ 21 5.3选择排序的算法................................................................................................ 22 5.4 堆排序的改进算法 ........................................................................................... 24 第六章 系统实现及数据测试.................................................................................... 29 6.1主界面................................................................................................................ 29 6.2“排序内部操作过程”菜单............................................................................. 29 6.2.1当用户输入0-6的数字时则会随意的进入下一级子菜单................... 30 6.2.2输入“2”进行“希尔”排序................................................................. 30 6.3“性能分析”菜单............................................................................................. 31 6.3.1当用户输入“1”时进行“插入与希尔”排序之间的性能分析比较. 31 6.3.2当用户输入“1”时进行“插入与冒泡”排序之间的性能分析比较. 32 总 结.......................................................................................................................... 33 参考文献...................................................................................................................... 34
内部算法性能分析 第1章 前 言
第1章 前 言
1.1分析问题
排序是指将一个数据元素序列排列成一个有序列的过程。排序是计算机的一个重要的领域，并广泛应用于数据处理、情报检索、商业金融及企业管理等许多方面。资料表明，在当今计算机系统中，花费在排序上的时间占了系统运行的时间的很大比重。相当多的计算机中，有50%以上的CPU时间是用在排序数据上的。因此为了提高计算机系统的工作效率，研究和发展更有效的排序算法的十分重要的。
目前人们已经提出了许多不同的排序算法，然而如果在不适应的场合的应用，那么其平均时间(averageTime)和最差时间(worstTime)就会不理想，其排序算效率就会大大的降低，如国防系统和生命支持系统，如果排序方法性能低下，将会令我们大大的失望。另外用来衡量排序算法的标准是稳定性，在那些比较复杂的排序中其稳定性不是很好，容易程序出错，就这样造成我们计算机的运算时间加长和内存地址的浪费。
1.2研究背景
由于排序是数据结构中的重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排序算法的时间消耗对于实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序等，以关键码的比较次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况，排序表的数据是多种不一样的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图来表示。
然而在本文中我们将选择其中最基本也是最常用的6种内部排序（直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序）进行讨论，介绍它们的基本思想和实现过程，分析各种算法的时间、空间复杂性、比较次数、移动次数以及稳定性，以期读者能够掌握这些算法及其特点中，在实际应用中能够结合具体问题设计出正确而高效率的数据排序程序。
1