第10章挑秀 学司要点 理解和熟悉各种内部排序的基本思想和过程 掌握内部排序算法的时间复杂度的分析方法和结 论 要求能根据各种内部排序方法的优缺点及不同场 合选择合适的排序方法
学习要点 第10章 排序 ◼ 理解和熟悉各种内部排序的基本思想和过程 ◼ 掌握内部排序算法的时间复杂度的分析方法和结 论 ◼ 要求能根据各种内部排序方法的优缺点及不同场 合选择合适的排序方法
10.1基本概念 排序就是把一组记录（元素）按照某个域的值的递增（即由 小到大)或递减（即由大到小）的次序重新排列的过程。 一} 般情况下，假设含n个记录的序列为 (R1,R2,,Rn) 其相应关键字序列为 (K1,K2,,Kn) 需确定一种排列，使关键字满足如下的递增的关系 KK2.≤Kn 则按此关系将记录序列重新排列为(R,R2,,Rn)的操 作称之为排序
10.1 基本概念 排序就是把一组记录(元素)按照某个域的值的递增(即由 小到大)或递减(即由大到小)的次序重新排列的过程。 一般情况下，假设含n个记录的序列为 （R1 , R2 , …, Rn） 其相应关键字序列为 （K1 , K2 , …, Kn） 需确定一种排列，使关键字满足如下的递增的关系 Ki1 ≤Ki2 ≤…≤Kin 则按此关系将记录序列重新排列为(Ri1 , Ri2 , …, Rin)的操 作称之为排序
10.1基本概念 在排序的过程中也要引入关键字的概念。所谓关键字是 指在一个记录中可以标识该数据项的值，它是排序运算的 重要依据。关键字的选取应根据需要而定，比如在学生档 案表中，可选择“学号”为关键字来识别学生，也可选择 “年龄”为关键字对学生排序。 表10-1学生档案表 学号 姓名 年龄 性别 990001 王晓佳 18 男 990002 林一鹏 19 男 990003 谢宁 17 女 990004 张丽娟 18 女 990005 周涛 20 男 990006 李小燕 16 女
表10-1 学生档案表 学号 姓名 年龄 性别 990001 王晓佳 18 男 990002 林一鹏 19 男 990003 谢宁 17 女 990004 张丽娟 18 女 990005 周涛 20 男 990006 李小燕 16 女 在排序的过程中也要引入关键字的概念。所谓关键字是 指在一个记录中可以标识该数据项的值，它是排序运算的 重要依据。关键字的选取应根据需要而定，比如在学生档 案表中，可选择“学号”为关键字来识别学生，也可选择 “年龄”为关键字对学生排序。 10.1 基本概念
10.1基本概念 在上表中，若以每个记录的学号为关键字，可按排序码年龄 的递增（由小到大）排序，则所有记录的排序结果可简记为： {99006,16),(99003,17),(99001,18),(99004,18),(99002,19),(99005,20}; 也可能为： {99006,16),(99003,17),(99004,18),(99001,18),(99002,19),(99005,20}: 这两个结果都是按年龄的递增排序结果。 若按排序码姓名来进行递增排序，则得到的排序结果为： (99006,李小燕)，(99002，林一鹏)，(99001，王晓佳)，(99003，谢宁) (99004,张丽娟)，(99005，周涛)} 当然，我们还可以按排序码性别来进行递增排序， 在此不再 作进一步的分析
在上表中，若以每个记录的学号为关键字，可按排序码年龄 的递增(由小到大)排序，则所有记录的排序结果可简记为： {(99006,16),(99003,17),(99001,18),(99004,18),(99002,19),(99005,20)}； 也可能为： {(99006,16),(99003,17),(99004,18),(99001,18),(99002,19),(99005,20)}； 这两个结果都是按年龄的递增排序结果。 若按排序码姓名来进行递增排序，则得到的排序结果为： {(99006,李小燕),(99002,林一鹏),(99001,王晓佳),(99003,谢宁) (99004,张丽娟),(99005,周涛)} 当然，我们还可以按排序码性别来进行递增排序，在此不再 作进一步的分析。 10.1 基本概念
10.1基本概念 排序的分类 按照排序过程中使用内、外存的不同，将排序方法分 为内部排序和外部排序。 ”内部排序：如果待排序的记录放在计算机内存中进行排 序，整修排序过程不需要访问外存便能完成，则此类排 序称为一。 >内排序分类：插入排序、交换排序、选择排序、归并 排序和分配排序。 外部排序：如果待排序的记录数量比较大，排序期间文 件的全部记录不能同时存放在计算机的内存里，排序过 程中需要不断地进行内存和外存之间的数据交换，则此 类排序称为~
◼ 排序的分类 按照排序过程中使用内、外存的不同，将排序方法分 为内部排序和外部排序。 ❖ 内部排序：如果待排序的记录放在计算机内存中进行排 序，整修排序过程不需要访问外存便能完成，则此类排 序称为~ 。 ➢ 内排序分类：插入排序、交换排序、选择排序、归并 排序和分配排序。 ❖ 外部排序：如果待排序的记录数量比较大，排序期间文 件的全部记录不能同时存放在计算机的内存里，排序过 程中需要不断地进行内存和外存之间的数据交换，则此 类排序称为~ 。 10.1 基本概念