数据结构课程设计--排序算法

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

1、 目录目录 1 1 前言前言 1 2 2 工程概况工程概况 1 2.1 工程所用时. 1 2.2 项目负责人. 1 2.3 项目指导人. 1 3 3 正文正文 1 3.1 冒泡排序 2 3.1.1 冒泡排序基本思想 . 2 3.1.2 冒泡法的实现过程 2 3.1.3 冒泡法的改进 3 3.1.4 改进方法 3 3.1.5 冒泡法分析 . 3 3.1.5.1 算法的最好时间复杂度 3 3.1.5.2 算法的最坏时间复杂度 . 3 3.1.5.3 算法的平均时间复杂度 4 3.1.5.4 算法稳定性 4 3.2 希尔排序. 4 3.2.1 希尔排序 . 4 3.2.2 希尔排序算法基本思想 .

2、4 3.2.3 希尔排序的实现过程 . 4 3.2.4 希尔分析 5 3.2.5 时间性能 5 3.2.5.1 增量序列的选择 5 3.2.5.2 好的增量序列的共同特征 5 3.2.5.3 希尔排序的时间性能 5 3.3 快速排序算法. 6 3.3.1 快速排序 . 6 3.3.2 快速排序基本思想 . 6 3.3.3 快速排序的具体过程 . 6 3.3.4 算法设计 . 6 3.3.5 算法分析 7 4 4 致谢致谢 8 5 5 课程设计小结课程设计小结 8 6 6 参考文献参考文献 8 第 1 页 共 14 页 前言前言 随着计算机产业的飞速发展， 它已经深入到人类生活的各个领域， 计算

3、机的应用并不局 限与科学计算，更多地用于控制和管理及处理实际问题。与此相应，为了编写出一个好的程 序， 必须分析待处理的对象的特性以及各处理对象之间存在的关系。 数据结构就是在这种背 景中形成和发展的。 “数据结构” 作为计算机学科中一门综合性的专业基础课， 必须要以理论与实践相结合， 才能更好学习这门学科， 所以我们数据结构设置了课程设计这项理论与实践相结合的学习内 容。 数据结构课程设计要求同学独立完成一个较为完整的应用需求分析， 在完成设计课程设 计的过程中， 深化对数据结构排序算法课程的理解， 训练同学们综合运用所学知识处理实际 问题的能力， 强化面向对象的程序设计理念。 设计同学们的

4、程序设计水平和调试水平有大幅 度的提高。让同学更好了解数据结构，更好理解编程思想，是自己的程序得以运行，实现自 己的目的，解决实际问题。 工程概况工程概况 2.1 工程所用时 此次工程从 12 月 19 日开始，于 12 月 28 日结束，历时 10 天时间。 2.2 项目负责人 * 信息工程学院 计算机科学与技术 14-1 2.3 项目指导人 * 信息工程学院 讲师 正文正文 我此次课程设计是关于排序算法的。 其主要目的是排序是掌握三种排序算法， 掌握三种 排序方法的实现掌握三种排序算法的优劣分析及花费时间的计算。设计内容和要求利用 C 语言编程思想把随机函数产生的随机函数， 利用冒泡法排序

5、， 希尔排序算法及快速排序算法 进行排序，并在 C 语言上运行，比较这三种排序算法上级所耗费的时间。 计算机程序设计中的一种重要操作， 他的功能是讲一个数据元素的任意序列， 重新排列 第 2 页 共 14 页 成一个按关键字有序的序列。 所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。当待 排序记录的关键字都不相同时，排序结果是惟一的，否则排序结果不惟一。在待排序的文件 中， 若存在多个关键字相同的记录， 经过排序后这些具有相同关键字的记录之间的相对次序 保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生改变，则称 这种排序方法是不稳定的。 要注意

6、的是，排序算法的稳定性是针对所有输入实例而言的。 即在所有可能的输入实例中， 只要有一个实例使得算法不满足稳定性要求， 则该排序算法就 是不稳定的。 关于算法的描述是对要解决一个问题或要完成一项任务所采取的方法和步骤 的描述，包括需要什么数据采用什么结构、使用什么语句以及如何安排这些语句，在C语言 程序上实现所要完成的问题，达到排序的目的。 3.1 冒泡排序 指依次比较相邻的两个数，将小数放在前面，大数放在后面。由于在排序过程中 总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。 3.1.1 冒泡排序基本思想 在第一趟：首先比较第 1 个和第 2 个数，将小数放前，大数放后。然后比较第 2 个数和第 3 个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数 放前，大数放后。至此第一趟结束，将最大的数放到了最后。 在第二趟：仍从第一对数开始比较（因为可能由于第 2 个数和第 3 个数的交换， 使得第 1 个数不再小于第 2 个数） ，将小数放前，大数放后，一直比较到倒数第二个 数（倒数第一的位置上已经是最大的）