排序第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学生档案表学号年龄姓名性别男9900118王晓佳99002林一鹏19男99003谢宁17女9900418张丽娟女99005周涛20男女李小燕9900616
9．1 基本概念 9.1.1 排序介绍 排序（Sorting）是数据处理中一种很重要的运算， 同时也是很常用的运算，一般数据处理工作25%的 时间都在进行排序。简单地说，排序就是把一组记 录（元素）按照某个域的值的递增（即由小到大） 或递减（即由大到小）的次序重新排列的过程。 表9-1 学生档案表 学号 姓名 年龄 性别 99001 王晓佳 18 男 99002 林一鹏 19 男 99003 谢宁 17 女 99004 张丽娟 18 女 99005 周涛 20 男 99006 李小燕 16 女
例如，在表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-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.1.2基本概念1．排序码（Sort Key）作为排序依据的记录中的一个属性。它可以是任何一种可比的有序数据类型，它可以是记录的关键字，也可以是任何非关键字。如上例中的学生年龄。在此我们认为对任何一种记录都可找到一个取得它排序码的函数Skey(一个或几个关键字的组合）。2.有序表与无序表一组记录按排序码的递增或递减次序排列得到的结果被称之为有序表，相应地，把排序前的状态称为无序表。3.正序表与逆序表若有序表是按排序码升序排列的，则称为升序表或正序表，否则称为降序表或逆序表。不失普遍性，我们一般只讨论正序表
9.1.2 基本概念 1．排序码（Sort Key） 作为排序依据的记录中的一个属性。它可以是任何一种 可比的有序数据类型，它可以是记录的关键字，也可以 是任何非关键字。如上例中的学生年龄。在此我们认为 对任何一种记录都可找到一个取得它排序码的函数 Skey(一个或几个关键字的组合)。 2．有序表与无序表 一组记录按排序码的递增或递减次序排列得到的结果被 称之为有序表，相应地，把排序前的状态称为无序表。 3．正序表与逆序表 若有序表是按排序码升序排列的，则称为升序表或正序 表，否则称为降序表或逆序表。不失普遍性，我们一般 只讨论正序表