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

《数据结构课程设计----内部排序算法性能分析》由会员分享，可在线阅读，更多相关《数据结构课程设计----内部排序算法性能分析（38页珍藏版）》请在毕设资料网上搜索。

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

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

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

4、排序）一些优点和缺陷，对缺陷加以改 进。通过对传统算法的性能分析，发现其中的缺陷，对算法的设想来 弥补中间的不足，以致算法的性能有所提高。 关键字: 数据结构、内部排序、算法改进、性能分析 目目 录录 第 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