没有合适的资源?快使用搜索试试~ 我知道了~
实验七:内部排序指导书.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 35 浏览量
2022-11-10
06:49:09
上传
评论
收藏 199KB DOCX 举报
温馨提示
试读
12页
。。。
资源推荐
资源详情
资源评论
实验七 各种内部排序算法的实现及性能比较
7.1 背景知识
排序是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,
重新排列成一个按关键字有序的序列。
学习和研究各种排序方法是计算机领域的重要课题之一。从第6 章的搜索(查找)算法中可以
看出,顺序表的查找时间复杂度为 O(n),而建立在有序表基础上的折半查找的时间复杂度为
O(log n)。
2
内部排序 是指待排序列完全存放在内存中所进行的排序过程,适合不太大的元素序列。
1.排序的定义
参见教科书 P 10.1 节基本概念。
187
2.排序方法
内部排序的方法很多,但就其全面性而言,很难提出一种被认为是最好的方法,每一种方法都
有其各自的优缺点,适合在不同的环境(如记录的初始排列状态等)下使用。如果按排序过程中依
据的不同原则对内部排序方法进行分类,则排序大致可分为插入排序、交换排序、选择排序、归并
排序、基数排序等 5 类;如果按内部排序过程中所需要的工作量(时间复杂度)来区分,则可分为
以下 3 类:
1)简单的排序方法,时间复杂度为 O(n )的排序方法,例如直接插入、直接选择和冒泡排序; 这
2
些排序方法非常容易理解和实现,但是它们的效率并不高,这在数据集比较大时尤其明显。
2)先进的排序方法,时间复杂度为O(nlogn)的排序方法,例如快速排序、堆排序和归并排序。
3)基数排序:这是一种并非基于比较的排序,它借助多关键字的排序思想,通过“分配”和
“收集”的方法来完成排序,时间复杂度为O(n)。
通常(除了上面的基数排序),在排序过程中需要进行下列两种基本操作:
1)比较两个记录关键字的大小
2)将记录从一个位置移动至另一个位置。
前一个操作对大多数排序方法来说是必要的,而后一个操作可以通过改变记录的存储方式来予
以避免。
可以从不同的角度描述排序算法的性能,主要有如下几个:
1)排序算法的时间复杂度和空间复杂度
2)排序算法的稳定性
3)排序算法的简单性(代码编写的难易程度)
3.排序表数据结构
排序表是待排序记录的集合。在本次实验中,待排序的一组记录存放在地址连续的一组存储单
元上。类似于线性表的顺序存储结构。
每个排序算法的实现都采用模板函数的方式,把实验中所有的排序算法都放在 SortAlgorithm.h
文件中。
7.2 实验目的
1)掌握常见的排序方法和实现排序的算法。
2)能根据待排序记录的关键字的初始状态选择合适的排序方法。
3)学会分析算法的基本方法,并计算算法的时间复杂度。
4)学会比较排序算法的性能。
7.3 工具/准备工作
在开始实验前,请回顾教科书中有关排序的定义及常见的内部排序算法。
需要一台计算机,其中装有 Microsoft Visual C++6.0开发环境或 DevCpp 集成开发环境。
7.4 实验内容与步骤
7.4.1 基础知识
2
1)三种计算时间为 O(n )的排序方法是:(
2)对于快速排序是使用( )算法设计策略开发的一种高效的交换排序。
3)( )排序方法不是基于比较的排序方法。
4)目前以比较为基础的内部排序的时间复杂度T(n)的范围是(
待排序的记录的初始状态无关的是( )。
)、(
)和(
)。
),其比较次数与
5)对于部分有序列表,简单选择排序算法的性能比对于随机列表的性能高,这句话是否正确?
6)对于部分有序列表,直接插入排序和冒泡排序算法的性能比对于随机列表的性能高,这句
话是否正确?
7)如果排序处理的是对象列表,这些对象表示包含着多个不同类型的信息项的记录,例如学
生对象。这时,排序是基于这些记录中的某个关键域进行的。在排序过程中如果移动整个数据对象,
所需要的时间将长得令人无法忍受。对于这些由大记录或对象组成的列表,可以使用间接排序,即
使用索引表来存放对象的位置,并移动对象的索引(即下标或位置)而非对象本身。
8)数组(顺序存储结构)能够用来有效地存储堆,因为堆是一种(
9)C++标准库<algorithm>中的 sort()函数模板使用了( )排序。
)二叉树。
10)根据数据项存放在内存还是外存,排序算法能够分为( )和( )两种。
7.4.2 各种排序算法的实现
1、选择排序
选择排序的基本思想是对列表或者列表的一部分进行多次扫描,每次选出一个元素将其放到正
确位置。
1)简单选择排序
每次选择总是从未排序序列中选出最小元素并把其放在未排序序列的起始位置上。每选择一次
会使未排序序列元素个数减一,已排序序列元素个数增一。共需要n-1 趟的选择。初始时,未排序
序列元素个数为 n。
简单选择排序算法描述请参考教科书 P 程序 10.1。
188
该算法的最好、最坏和平均情况的时间复杂度为O(n )。且为不稳定的排序方法。
2
2)堆排序
教科书介绍了堆,它是实现优先权队列的有效的数据结构。堆还可用于排序,这就是堆排序。
可以直接使用优先权队列实现排序,先将序列中的每个元素入优先权队列,之后再依次出队列,
得到的结果即是有序序列。 (教科书上的优先权队列
priority_queue 是大顶堆。)
PrioQueue 是小顶堆 ,STL 的适配器类
同学们可以自己编程序进行测试。
有关 STL中的栈和队列的相关内容请参考:
http://hi.baidu.com/eizi/blog/item/1e0c7c61fcec42d18db10df5.html
堆排序的基本思想如下:
第一步:为了得到非递减的排序序列,首先构造一个大顶堆。
第二步:for (i=n-1;i>0;i--) / /每循环一次进行一个根叶交换
1) 交换 a[i]和 a[0]
2) 使用向下调整算法,把 a[0]~a[i-1]重新调整成大顶堆
具体的算法实现请参考教科书 P 的程序 10.7和程序 10.8。
196
该算法的最好、最坏和平均情况的时间复杂度为O(nlog n)。且为不稳定的排序方法。
2
3)树排序
我们可以利用二叉查找树完成排序,把这种排序方法称为树排序。只需要把列表元素插入到初
始为空的二叉查找树 BSTree中,然后使用中序遍历来把元素复制到列表中。
算法描述如下:
template <class T>
void TreeSort(T A[],int n)
{
BSTree<T> tree; //构造一棵空树
for(int i=0;i<n;i++)
tree.Insert(A[i]);
int i=0;
tree.InOrder(int &i) //对中序遍历进行适当修改,
//对某个结点访问也就是把结点的值赋给 A[i]后再 i++
}
同学们可以自己编程序进行测试。
2、插入排序
1)直接插入排序
直接插入排序的思想非常简单,将序列中第一个元素作为一个有序序列,然后将剩下的n-1个
元素按关键字大小依次插入该有序序列,每插入一个元素后依然保持该序列有序,经过n-1趟排序
后即成为有序序列。
直接插入排序算法请参考 P 的程序 10.2。
189
直接插入排序算法的最坏情况出现在当列表按相反方向排列的时候。时间复杂为 O(n )。最好
2
情况为序列已经有序,时间复杂度为 O(n)。该排序算法是稳定的排序方法。
对于短列表(包含 20 个左右的元素)和部分有序列表,在我们讨论的所有排序算法中,实验
结果表明直接插入排序的性能最佳。
2)折半插入排序
如果我们使用折半查找而不是顺序查找来在排好序的子列表a[0],a[1],„,a[i-1]中找出下一
项 a[i]应该插入的位置。那么该算法称为折半插入排序。
请编写折半插入排序算法并编程实现:
template <class T>
void BInsertSort(int A[],int n)
{
剩余11页未读,继续阅读
资源评论
คิดถึง643
- 粉丝: 3908
- 资源: 1万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功