第三章排序
第 1 页
学写的义 早期的计算机约有一半的时间花在排序操作上,虽然随着 计算机速度的提高,排序操作不再像早期那样占用计算机过多 的时间,但它仍然是信息处理中最常用,也是最重要的运算之 实际上,在计算机科学中,排序仍然是组织数据最基本的运 算,许多程序和软件均以它作为一个中间步骤。因此,人们设 计了大量的排序算法以满足不同的需求。 计算机图灵奖获得者,著名计算机科学家DE. Knuth在他的 著《 Art of Computer Programming》中列举分析了25中经典 排序方法,并且指出,这只是现有方法中的“一小部分
第 2 页 ◆学习的意义： 早期的计算机约有一半的时间花在排序操作上，虽然随着 计算机速度的提高，排序操作不再像早期那样占用计算机过多 的时间，但它仍然是信息处理中最常用，也是最重要的运算之 一。 实际上，在计算机科学中，排序仍然是组织数据最基本的运 算，许多程序和软件均以它作为一个中间步骤。因此，人们设 计了大量的排序算法以满足不同的需求。 计算机图灵奖获得者，著名计算机科学家D.E.Knuth在他的 巨著《Art of Computer Programming》中列举分析了25中经典 排序方法，并且指出，这只是现有方法中的“一小部分
团今金墨庐容 31排序的基本概念 32简单的排序方法 321插入排序 3.2.2起泡排序 33先进的排序方法 3.3.1快速排序 332归并排序 333堆排序 3.4基数排序 3.4各种排序方法的综合比较
第 3 页 3.1 排序的基本概念 3.2 简单的排序方法 3.2.1 插入排序 3.2.2 起泡排序 3.3 先进的排序方法 3.3.1 快速排序 3.3.2 归并排序 3.3.3 堆排序 3.4 基数排序 3.4 各种排序方法的综合比较 ◆主要内容：
3.1排序的基本概念 在很多情况下,相对于无序表而言,使用有序表可以提 高算法效率,因为有序表可以充分利用其有序性采用一些效 率较高的算法,例如,在进行数据元素的查找时,采用有序 表比无序表效率要高很多。 如何得到有序表?我们可以在构造顺序表的时候依顺序表 的有序性进行数据元素的插入,从而求得有序表。 更多的时候,我们需要对一个无序的顺序表进行“排序 将它转化为“有序”的顺序表
第 4 页 在很多情况下，相对于无序表而言，使用有序表可以提 高算法效率，因为有序表可以充分利用其有序性采用一些效 率较高的算法，例如，在进行数据元素的查找时，采用有序 表比无序表效率要高很多。 如何得到有序表？我们可以在构造顺序表的时候依顺序表 的有序性进行数据元素的插入，从而求得有序表。 更多的时候，我们需要对一个无序的顺序表进行“排序” ，将它转化为“有序”的顺序表。 3. 1 排序的基本概念
3.1排序的基本概念 排序的定义 排序是按关键字的非递减或非递增顺序对一组记录重新进行整 队(或)排列的操作 例1、高考考生信息管理系统提供了将考生按总分排序、按单科排序的功 能 例2、数学中的数列(1,13,15,17,19,姓名电话号吗 例3、英文字母表(A,B,C,D,E.Z) 例4、某单位的电话号码簿。 蔡颖 63214444 陈红 63217777 刘建平 63216666 王小林 63218888 张力 63215555
第 5 页 排序 是按关键字的非递减或非递增顺序对一组记录重新进行整 队(或)排列的操作. 姓名 电话号码 蔡颖 63214444 陈红 63217777 刘建平 63216666 王小林 63218888 张力 63215555 ... 3. 1 排序的基本概念 例1、高考考生信息管理系统提供了将考生按总分排序、按单科排序的功 能； 例2、数学中的数列（11，13，15，17，19，21） 例3、英文字母表（A, B, C, D, E Z ）。 例4、某单位的电话号码簿。 排序的定义
排序的形式化描述 假设含有n个记录的序列为 ri,r2, 3,.,rn 它们的关键字相应为: 112,139 对记录序列进行排序就是确定序号1,2,3,n的一种排列: P1P2P3…5Pn 使其相应的关键字满足非递减或非递增的关系 kp k 也就是使记录序列重新排列成为一个按关键字有序的序列 {n1∈nn3…∈rmn}
第 6 页 排序的形式化描述 假设含有n个记录的序列为： {r1 ,r2 ,r3 ,…,rn} 它们的关键字相应为： {k1 ,k2 ,k3 ,…,kn } 对记录序列进行排序就是确定序号1,2,3,…,n的一种排列： p1 ,p2 ,p3 ,…,pn 使其相应的关键字满足非递减或非递增的关系 kp1≤ kp2 ≤ kp3。。。 ≤ kpn 也就是使记录序列重新排列成为一个按关键字有序的序列 1 2 3 { ... } p p p pn r r r r
排序分类 什么叫内部排序?什么叫外部排序? 若整个排序过程不需要访问外存便能完成,则称此 类排序问题为内部排序;称为内部排序; 反之,若参加排序的记录数量很大,整个序列的排 序过程不可能在内存中完成,则称此类排序问题为外部 排序。 注:外部排序时,要将数据分批调入内存来排序,中间 结果还要及时放入外存,显然外部排序要复杂得多。次
第 7 页 排序分类 什么叫内部排序？什么叫外部排序？ 若整个排序过程不需要访问外存便能完成，则称此 类排序问题为内部排序；称为内部排序； 反之，若参加排序的记录数量很大，整个序列的排 序过程不可能在内存中完成，则称此类排序问题为外部 排序。 注：外部排序时，要将数据分批调入内存来排序，中间 结果还要及时放入外存，显然外部排序要复杂得多
内部排序的算法有哪些? 按排序的规则不同,可分为5类: 插入排序 交换排序(重点是快速排序) 选择排序 归并排序 基数排序 按排序算法的时间复杂度不同,可分为3类 简单的排序算法:时间效率低,O(m2) 先进的排序算法:时间效率高,O(mlog2n) 基数排序算算法:时间效率高,O(d×n =关键字的位数(长度)
第 8 页 内部排序的算法有哪些？ ——按排序的规则不同，可分为5类： • 插入排序 • 交换排序（重点是快速排序） • 选择排序 • 归并排序 • 基数排序 d＝关键字的位数(长度) ——按排序算法的时间复杂度不同，可分为3类： •简单的排序算法：时间效率低，O(n2 ) •先进的排序算法: 时间效率高，O( nlog2n ) •基数排序算算法：时间效率高，O( d×n)
按稳定性分类: 在待排记录序列中,任何两个关键字相同的记录,用某种排序方法 排序后相对位置不变,则称这种排序方法是稳定的,否则称为不稳定 的。 例设49,38,65,97,76,13,27,49是待排序列 排序后:13,27,38,49,49,65,76,97—稳定 排序后:13,27,38,49,49,65,76,97不稳定 稳性排序的应用: 例股票交易系统考虑一种股票交易(清华紫光)) 1)顾客输入:股东帐号、股票代码、申购价格、数量,股票交易系统将 用户申购请求插入申购队列队尾 2)股票交易系统按如下原则交易 A)申购价高者先成交 B)申购价相同者按申购时间先后顺序成交
第 9 页 按稳定性分类： 在待排记录序列中，任何两个关键字相同的记录，用某种排序方法 排序后相对位置不变，则称这种排序方法是稳定的，否则称为不稳定 的。 例 设 49,38,65,97,76,13,27,49 是待排序列 排序后:13,27,38,49,49,65,76,97 —— 稳定 排序后:13,27,38,49,49,65,76,97——不稳定 稳性排序的应用： 例 股票交易系统 考虑一种股票交易(清华紫光)） 1）顾客输入：股东帐号、股票代码、申购价格、数量，股票交易系统将 用户申购请求插入申购队列队尾； 2）股票交易系统按如下原则交易： A）申购价高者先成交 B）申购价相同者按申购时间先后顺序成交
如何实现股票交易系统? 申购队列:用线性表表示 交易前:将申购队列按申购价排序,显然为满足原则交易 B),要求排序方法是稳定的 申购队列(09,10),(06,10.5),(033,9.8),(051,10) 排序后:((06,10.5),(09,10),(051,10),(033,9.8)
第 10 页 如何实现股票交易系统 ？ 申购队列：用线性表表示 交易前：将申购队列按申购价排序，显然为满足原则交易 B），要求排序方法是稳定的 申购队列（09,10),(06,10.5),(033,9.8),(051,10)) 排序后：((06,10.5),(09,10),(051,10),(033,9.8))