《第13周内排序第1讲-排序的概念.pdf》由会员分享，可在线阅读，更多相关《第13周内排序第1讲-排序的概念.pdf（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第10章章 内内 排排 序序 说明说明：排序数据中可以存在相同关键字的记录。本章仅排序数据中可以存在相同关键字的记录。本章仅 考虑考虑递增递增排序。排序。 1、排序、排序的定义的定义 所谓排序所谓排序，是整理，是整理表中的记录，使之按关键字递增（或递减）表中的记录，使之按关键字递增（或递减） 有序排列：有序排列： 排序排序 n个记录，个记录，R0,R1,Rn-1，其相应的关键字分别为，其相应的关键字分别为 k0,k1,kn-1 Ri,0,Ri,1,Ri,n-1，使得递增，使得递增ki,0ki,1ki,n-1（或（或 递减递减ki,0ki,1 ki,n-1） 在排序过程中，若整个表都是放在内存
2、中处理，排序时不涉在排序过程中，若整个表都是放在内存中处理，排序时不涉 及数据的内、外存交换，则称之为及数据的内、外存交换，则称之为内排序内排序； 反之，若排序过程中要进行数据的内、外存交换，则称之为反之，若排序过程中要进行数据的内、外存交换，则称之为 外排序外排序。 2、内、内排序和外排序排序和外排序 文件文件 内存内存 3、内、内排序的分类排序的分类 内排序内排序 基于比较的排序算法基于比较的排序算法 不基于比较的排序算法不基于比较的排序算法 插入排序插入排序 交换排序交换排序 选择排序选择排序 归并排序归并排序 基数排序基数排序 基于比较基于比较的内排序的内排序算法最快有多快算法最快有多
3、快 ？ 假设假设有有3个记录个记录(R1,R2,R3)，对应的关键字为，对应的关键字为(k1,k2,k3)。 初始数据初始数据序列有序列有 3! = 6 种种情况：情况： 1，2，3 1，3，2 2，1，3 2，3，1 3，1，2 3，2，1 n个记录，初始数据序列有个记录，初始数据序列有n!种情况种情况 以以(R1,R2,R3) =（2,3,1）为）为例，例，一种基于一种基于比较的排序方法比较的排序方法： R1 R2 R3 2 3 1 R1 R2为为真，不交换真，不交换 R1 R2 R3 2 3 1 R2 R3 为假，为假， R2 、 R2 交换交换 R1 R3 R2 2 1 3 R1 R3
4、 为假，为假， R1 、 R2 交换交换 R3 R1 R2 1 2 3 总共总共3次关键字比较次关键字比较 k1k2 (R1,R2,R3) k2k3 (R1,R2,R3) (R1,R2,R3) k1k3 (R1,R3,R2) (R1,R3,R2) (R3,R1,R2) 是是 是是 否否 是是 否否 k1k3 (R2,R1,R3) (R2,R1,R3) k2k3 (R2,R3,R1) (R2,R3,R1) (R3,R2,R1) 是是 否否 是是 否否 否否 所有可能的初始序列的排序过程构成一个所有可能的初始序列的排序过程构成一个决策树决策树： 决策树是一棵有决策树是一棵有n!个叶节点的二叉树。个
5、叶节点的二叉树。 决策树决策树可以近似看成是一颗高度为可以近似看成是一颗高度为h，叶节点个数为，叶节点个数为n!的的满二叉树满二叉树。 叶节点层，叶节点层，n!个节点个节点 h 叶节点个数叶节点个数=n! 总节点个数总节点个数=2n!- -1 h=log2(总节点个数总节点个数+1)=log2(n!) nlog2n 平均关键字比较次数平均关键字比较次数=h- -1 移动次数也是同样的数量级，即这样的算法移动次数也是同样的数量级，即这样的算法最坏时间复杂度最坏时间复杂度为为O(nlog2n)。 同样可以证明同样可以证明平均时间复杂度也为平均时间复杂度也为O(nlog2n)。 n个记录采用个记录采
6、用基于比较的基于比较的排序方法：排序方法： 最好的平均最好的平均时间复杂度为时间复杂度为O(nlog2n) 。 最好最好情况是排序序列正序，此时的时间复杂度为情况是排序序列正序，此时的时间复杂度为O(n)。 结论：结论： 当当待排序记录的关键字均不相同时，排序的待排序记录的关键字均不相同时，排序的结果结果是是唯一唯一的。的。 4、内、内排序算法的稳定性排序算法的稳定性 2 4 3 1 5 1 2 3 4 5 张 三 张 三 李 四 李 四 王 五 王 五 刘 六 刘 六 陈 七 陈 七 张 三 张 三 李 四 李 四 王 五 王 五 刘 六 刘 六 陈 七 陈 七 如果待排序的表如果待排序的表
7、中，存在中，存在有多个关键字相同的有多个关键字相同的记录，经过记录，经过排序后这些排序后这些 具有相同关键字的记录之间的具有相同关键字的记录之间的相对次序保持相对次序保持不变不变，则，则称这种排序方法是称这种排序方法是稳稳 定定的。的。 反之反之，若，若具有相同关键字的记录之间的具有相同关键字的记录之间的相对次序发生相对次序发生变化变化，则，则称这种称这种 排序方法是排序方法是不稳定不稳定的。的。 34 31 5 1 2 335 34 31 5 1 2 335 若待排序的表中元素已按关键字排好序，称此表中元素为若待排序的表中元素已按关键字排好序，称此表中元素为正序正序； 反之，若待排序的表中元
8、素的关键字顺序正好和排好序的顺序相反，反之，若待排序的表中元素的关键字顺序正好和排好序的顺序相反， 称此表中元素为称此表中元素为反序反序。 5、正序、正序和反序和反序 有一些排序算法与初始序列的正序或反序有关，另一些排序算法有一些排序算法与初始序列的正序或反序有关，另一些排序算法 与初始序列的情况无关。与初始序列的情况无关。 typedef int KeyType; /定义关键字类型定义关键字类型 typedef struct/记录类型记录类型 KeyType key;/关键字项关键字项 InfoType data;/其他数据项其他数据项,类型为类型为InfoType RecType;/排序的记录类型定义排序的记录类型定义 待排序的顺序表的数据元素类型定义如下：待排序的顺序表的数据元素类型定义如下： 6、 内排序内排序数据的组织数据的组织 本讲完本讲完