第9章排序 数据结构(C++描述)
第9章 排序 数据结构（C++描述）
目录 9.1基本概念 9.2插入排序 9.3交换排序 9.4选择排序 9.5归并排序 9.6分配排序 退出
目录 9．1 基本概念 9．2 插入排序 9．3 交换排序 9．4 选择排序 9．5 归并排序 *9. 6 分配排序 退出
9.1基本概念 9.1.1排序介绍 排序( Sorting)是数据处理中一种很重要的运算, 同时也是很常用的运算,一般数据处理工作25%的 时间都在进行排序。简单地说,排序就是把一组记 录(元素)按照某个域的值的递增(即由小到大) 或递减(即由大到小)的次序重新排列的过程 表9-1学生档案表 学号 姓名 年龄 性别 99001 王晓佳 18 男 99002 林一鹏 男 99003 谢宁 17 女 99004 张丽娟 18 99005 周涛 男 99006 李小燕 女
9．1 基本概念 9.1.1 排序介绍 排序（Sorting）是数据处理中一种很重要的运算， 同时也是很常用的运算，一般数据处理工作25%的 时间都在进行排序。简单地说，排序就是把一组记 录（元素）按照某个域的值的递增（即由小到大） 或递减（即由大到小）的次序重新排列的过程。 表9-1 学生档案表 学号 姓名 年龄 性别 99001 王晓佳 18 男 99002 林一鹏 19 男 99003 谢宁 17 女 99004 张丽娟 18 女 99005 周涛 20 男 99006 李小燕 16 女
?例如,在表9-1中,若以每个记录的学号为关键字,按 x排序码年龄的递增(由小到大)排序,则所有记录的排 序结果可简记为: y((990,16),(9903,17),(990,18) (99004,18),(99002,19),(99005,20)}; 也可能为 (99006,16),(99003,17),(99004,18) (99001,18),(99002,19),(99005,20)}; 这两个结果都是表9-1按年龄的递增排序结果。若按排序 码姓名来进行递增排序,则得到的排序结果为: (99006,李小燕),(990,林一鹏),(99001, 王晓佳),(99003,谢宁),(9004,张丽娟), (99005,周涛)} 当然,我们还可以按排序码性别来进行递增排序,在此 不再作进一步的分析
例如，在表9-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）}； 这两个结果都是表9-1按年龄的递增排序结果。若按排序 码姓名来进行递增排序，则得到的排序结果为： {（99006，李小燕），（99002，林一鹏），（99001， 王晓佳），（99003，谢宁），（99004，张丽娟）， （99005，周涛）} 当然，我们还可以按排序码性别来进行递增排序，在此 不再作进一步的分析
飞它?9.12基本概念 1.排序码( Sort Key) 作为排序依据的记录中的一个属性。它可以是任何一种 可比的有序数据类型,它可以是记录的关键字,也可以 是任何非关键字。如上例中的学生年龄。在此我们认为 对任何一种记录都可找到一个取得它排序码的函数 Skey(一个或个关键字的组合)。 2.有序表与无序表 组记录按排序码的递增或递减次序排列得到的结果被 称之为有序表,相应地,把排序前的状态称为无序表。 3.正序表与逆序表 若有序表是按排序码升序排列的,则称为升序表或正序 表,否则称为降序表或逆序表。不失普遍性,我们一般 只讨论正序表
9.1.2 基本概念 1．排序码（Sort Key） 作为排序依据的记录中的一个属性。它可以是任何一种 可比的有序数据类型，它可以是记录的关键字，也可以 是任何非关键字。如上例中的学生年龄。在此我们认为 对任何一种记录都可找到一个取得它排序码的函数 Skey(一个或个关键字的组合)。 2．有序表与无序表 一组记录按排序码的递增或递减次序排列得到的结果被 称之为有序表，相应地，把排序前的状态称为无序表。 3．正序表与逆序表 若有序表是按排序码升序排列的，则称为升序表或正序 表，否则称为降序表或逆序表。不失普遍性，我们一般 只讨论正序表