文档介绍：第8章排序
排序的概念及种类
插入法排序的各种具体实现方法及算法分析
选择法排序的各种具体方法的实现及时间性能分析
交换法排序的具体实现及性能分析
归并排序和基数排序的各自实现算法
2017/12/5
1
本章导读
排序是日常工作和软件设计中常用的运算之一。为了提高查询速度需要将无序序列按照一定的顺序组织成有序序列。由于需要排序的数据表的基本特性可能存在差异,使得排序方法也不同。如何合理地组织数据的逻辑顺序,按照何种方式排出的序列最有效?这是本章要讨论的主题。本章主要介绍排序的概念及几种最常见的排序方法,讨论其性能和特点,并在此基础上进一步讨论各种方法的适用场合,以便在实际应用中能根据具体的问题选择合适的排序方法。通过本章学习,读者应该掌握以下几项内容:
排序的概念及种类
插入法排序的各种具体实现方法及算法分析
选择法排序的各种具体方法的实现及时间性能分析
交换法排序的具体实现及性能分析
归并排序和基数排序的各自实现算法
2017/12/5
2
排序的基本概念
排序及其分类
排序(sorting)又称分类,是数据处理领域中一种很常用的运算。排序就是把一组记录或数据元素的无序序列按照某个关键字值(关键字)递增或递减的次序重新排列的过程。排序的主要目的就是实现快速查找。日常生活中通过排序以后进行检索的例子屡见不鲜。如电话簿、病历、档案室中的档案、图书馆和各种词典的目录表等,几乎都需要对有序数据进行操作。
2017/12/5
3
假设含有n个记录的序列为:
{R1,R2 ,…,Rn} (8-1)
其相应的关键字序列为:
{K1,K2 ,…,Kn}
需确定1,2, …,n的一种排序p1,p2, …,pn,使其
相应的关键字满足如下关系:
Kp1≤Kp2≤…≤Kpn (8-2)
即使得式(8-1)的序列成为一个按关键字有序的序列
{R p1,R p2 ,…,Rpn} (8-3)
这个将原有表中任意顺序的记录变成一个按关键字有序排列的过程称为排序。
2017/12/5
4
增排序和减排序:如果排序的结果是按关键字从小到大的次序排列的,就是增排序,否则就是减排序。
稳定排序和不稳定排序:假设Ki=Kj(1≤i≤n,1≤j≤n,i≠j),且在排序前的序列中Ri领先于Rj(即i<j)。若在排序后的排序中Ri仍领先于Rj,即那些具有相同关键字的记录,经过排序后它们的相对次序仍然保持不变,则称这种排序方法是稳定的;反之,若Rj领先于Ri,则称所用的方法是不稳定的。
2017/12/5
5
(3) 内部排序与外部排序:在排序中,若数据表中的所有记录的排列过程都是在内存中进行的,称为内部排序。由于待排序的记录数量太多,在排序过程中不能同时把全部记录放在内存,需要不断地通过在内存和外存之间交换数据元素来完成整个排序的过程,称为外部排序。在外部排序情况下,只有部分记录进入内存,在内存中进行内部排序,待排序完成后再交换到外部存储器中加以保存。然后再将其它待排序的记录调入内存继续排序。这一过程需要反复进行,直到全部记录排出次序为止。显然,内部排序是外部排序的基础,本章先介绍内部排序的各种方法,最后再讨论外部排序。
2017/12/5
6
排序算法的效率分析
与许多算法一样,对各种排序算法性能的评价主要从两个方面来考虑,一是时间性能;二是空间性能。
1. 时间复杂度分析
排序算法的时间复杂度可用排序过程中记录之间关键字的比较次数与记录的移动次数来衡量。在本章各节中讨论算法的时间复杂度时,一般都按平均时间复杂度进行估算;对于那些受数据表中记录的初始排列及记录数目影响较大的算法,按最好情况和最坏情况分别进行估算。
2017/12/5
7
排序算法的空间复杂度是指算法在执行时所需的附加存储空间,也就是用来临时存储数据的内存使用情况。
在以后的排序算法中,若无特别说明,均假定待排序的记录序列采用顺序表结构来存储,即数组存储方式,并假定是按关键字递增方式排序。为简单起见,假设关键字类型为整型。待排序的顺序表类型的类型定义如下:
typedef int KeyType //定义关键字类型
typedef struct dataType //记录类型
{ keytype key; //关键字项
elemtype otherelement; //其他数据项
}RecType;
2017/12/5
8
插入排序
插入排序的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子表中的适当位置,直到全部记录插入完成为止。也就是说,将待序列表分成左右两部分,左边为有序表(有序