排序的形式化描述 假设含有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))