没有合适的资源?快使用搜索试试~ 我知道了~
实验五:内部排序.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 145 浏览量
2022-11-10
06:49:44
上传
评论
收藏 420KB PDF 举报
温馨提示
![preview](https://dl-preview.csdnimg.cn/86944083/0001-780a3780d536e46646efd783cf38119b_thumbnail.jpeg)
![preview-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/scale.ab9e0183.png)
试读
16页
。。。
资源推荐
资源详情
资源评论
![pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/octet-stream](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![gz](https://img-home.csdnimg.cn/images/20210720083447.png)
![xlsx](https://img-home.csdnimg.cn/images/20210720083732.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/release/download_crawler_static/86944083/bg1.jpg)
实验五 各种内部排序算法的实现及性能比较
5.1 背景知识
排序是计算机程序设计中的一种重要操作,它的功能
是将一个数据元素(或记录)的任意序列,重新排列成一
个按关键字有序的序列。
学习和研究各种排序方法是计算机领域的重要课题之
一。从第 6 章的搜索(查找)算法中可以看出,顺序表的
查找时间复杂度为 O(n),而建立在有序表基础上的折半
查找的时间复杂度为 O(log
2
n)。
内部排序 是指待排序列完全存放在内存中所进行
的排序过程,适合不太大的元素序列。
1.排序的定义
参见教科书 P
187
10.1 节基本概念。
2.排序方法
内部排序的方法很多,但就其全面性而言,很难提出
一种被认为是最好的方法,每一种方法都有其各自的优缺
点,适合在不同的环境(如记录的初始排列状态等)下使
用。如果按排序过程中依据的不同原则对内部排序方法进
行分类,则排序大致可分为插入排序、交换排序、选择排
序、归并排序、基数排序等 5 类;如果按内部排序过程中
所需要的工作量(时间复杂度)来区分,则可分为以下 3
![](https://csdnimg.cn/release/download_crawler_static/86944083/bg2.jpg)
类:
1)简单的排序方法,时间复杂度为 O(n
2
)的排序方法,
例如直接插入、直接选择和冒泡排序; 这些排序方法非常
容易理解和实现,但是它们的效率并不高,这在数据集比
较大时尤其明显。
2)先进的排序方法,时间复杂度为 O(nlogn)的排序方
法,例如快速排序、堆排序和归并排序。
3)基数排序:这是一种并非基于比较的排序,它借助
多关键字的排序思想,通过“分配”和“收集”的方法来
完成排序,时间复杂度为 O(n)。
通常(除了上面的基数排序),在排序过程中需要进行
下列两种基本操作:
1)比较两个记录关键字的大小
2)将记录从一个位置移动至另一个位置。
前一个操作对大多数排序方法来说是必要的,而后一
个操作可以通过改变记录的存储方式来予以避免。
可以从不同的角度描述排序算法的性能,主要有如下
几个:
1)排序算法的时间复杂度和空间复杂度
2)排序算法的稳定性
3)排序算法的简单性(代码编写的难易程度)
3.排序表数据结构
![](https://csdnimg.cn/release/download_crawler_static/86944083/bg3.jpg)
排序表是待排序记录的集合。在本次实验中,待排序
的一组记录存放在地址连续的一组存储单元上。类似于线
性表的顺序存储结构。
每个排序算法的实现都采用模板函数的方式,把实验
中所有的排序算法都放在 SortAlgorithm.h 文件中。
5.2 实验目的
1)掌握常见的排序方法和实现排序的算法。
2)能根据待排序记录的关键字的初始状态选择合适的
排序方法。
3)学会分析算法的基本方法,并计算算法的时间复杂
度。
4)学会比较排序算法的性能。
5.3 工具/准备工作
在开始实验前,请回顾教科书中有关排序的定义及常
见的内部排序算法。
需要一台计算机,其中装有 Microsoft Visual C++6.0
开发环境或 DevCpp 集成开发环境。
5.4 实验内容与步骤
5.4.1 基础知识
1)三种计算时间为 O(n
2
)的排序方法是:( )、
![](https://csdnimg.cn/release/download_crawler_static/86944083/bg4.jpg)
( )和( )。
2)对于快速排序是使用( )算法设计策
略开发的一种高效的交换排序。
3)( )排序方法不是基于比较的排序方法。
4)目前以比较为基础的内部排序的时间复杂度 T(n)
的范围是( ),其比较次数与待排序的记录的
初始状态无关的是( )。
5)对于部分有序列表,简单选择排序算法的性能比对
于随机列表的性能高,这句话是否正确?
6)对于部分有序列表,直接插入排序和冒泡排序算法
的性能比对于随机列表的性能高,这句话是否正确?
7)如果排序处理的是对象列表,这些对象表示包含着
多个不同类型的信息项的记录,例如学生对象。这时,排
序是基于这些记录中的某个关键域进行的。在排序过程中
如果移动整个数据对象,所需要的时间将长得令人无法忍
受。对于这些由大记录或对象组成的列表,可以使用间接
排序,即使用索引表来存放对象的位置,并移动对象的索
引(即下标或位置)而非对象本身。
8)数组(顺序存储结构)能够用来有效地存储堆,因
为堆是一种( )二叉树。
9)C++标准库<algorithm>中的 sort()函数模板使用了
( )排序。
剩余15页未读,继续阅读
资源评论
![avatar-default](https://csdnimg.cn/release/downloadcmsfe/public/img/lazyLogo2.1882d7f4.png)
![avatar](https://profile-avatar.csdnimg.cn/06779827608847128b637bead301d722_weixin_72426331.jpg!1)
คิดถึง643
- 粉丝: 3931
- 资源: 1万+
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![voice](https://csdnimg.cn/release/downloadcmsfe/public/img/voice.245cc511.png)
![center-task](https://csdnimg.cn/release/downloadcmsfe/public/img/center-task.c2eda91a.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![dialog-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/green-success.6a4acb44.png)