第八章排序 甚本概念 排序的定义 二、内部排序 三、内部排序方法的分类 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 第八章 排序 一、排序的定义 二、内部排序 三、内部排序方法的分类 基本概念
排序基本概念 排序(sort)或分类 所谓排序,就是要整理文件中的记录,使 之按关键字递增(或递减)次序排列起来。其确 切定义如下: 的关键字分别为,…。,其相应 输入:n个记录R1,R2,…,R 输出:R1,R12,…,R,使得 K1≤K12≤≤Kn。(或K≥K12≥,K1) 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 一 排序基本概念 排序（sort）或分类 所谓排序，就是要整理文件中的记录, 使 之按关键字递增(或递减)次序排列起来。其确 切定义如下： 输入：n个记录R1，R2，…，Rn，其相应 的关键字分别为K1，K2，…，Kn。 输出：Ril，Ri2，…，Rin，使得 Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)
1.被排序对象一文件 被排序的对象-文件由一组记录组成。 记录则由若干个数据项(或域)组成。其中 有一项可用来标识一个记录,称为关键字项。 该数据项的值称为关键字(Key) 注意:在不易产生混淆时,将关键字项简称 为关键字。 2.排序运算的依据一关键字 用来作排序运算依据的关键字,可以是数字 类型,也可以是字符类型。 关键字的选取应根据问题的要求而定。 <心 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 1．被排序对象--文件 被排序的对象--文件由一组记录组成。 记录则由若干个数据项(或域)组成。其中 有一项可用来标识一个记录，称为关键字项。 该数据项的值称为关键字(Key)。 注意： 在不易产生混淆时，将关键字项简称 为关键字。 2．排序运算的依据--关键字 用来作排序运算依据的关键字，可以是数字 类型，也可以是字符类型。 关键字的选取应根据问题的要求而定
【例】在高考成绩统计中将每个考生作为一个 记录。每条记录包含准考证号、姓名、各科的 分数和总分数等项内容。若要惟一地标识一个 考生的记录,则必须用"准考证号"作为关键字 若要按照考生的总分数排名次,则需用"总分 数"作为关键字。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 【例】在高考成绩统计中将每个考生作为一个 记录。每条记录包含准考证号、姓名、各科的 分数和总分数等项内容。若要惟一地标识一个 考生的记录，则必须用"准考证号"作为关键字。 若要按照考生的总分数排名次，则需用"总分 数"作为关键字
排序的稳定性 当待排序记录的关键字均不相同时,排序结 果是惟一的,否则排序结果不唯 在待排序的文件中,若存在多个关键字相同 的记录,经过排序后这些具有相同关键字的记 录之间的相对次序保持不变,该排序方法是稳 定的;若具有相同关键字的记录之间的相对次 序发生变化,则称这种排序方法是不稳定的。 注意 排序算法的稳定性是针对所有输入实例而 言的。即在所有可能的输入实例中,只要有 个实例使得算法不满足稳定性要求,则该排序 算法就是不稳定的。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 排序的稳定性 当待排序记录的关键字均不相同时，排序结 果是惟一的，否则排序结果不唯一。 在待排序的文件中，若存在多个关键字相同 的记录，经过排序后这些具有相同关键字的记 录之间的相对次序保持不变，该排序方法是稳 定的；若具有相同关键字的记录之间的相对次 序发生变化，则称这种排序方法是不稳定的。 注意： 排序算法的稳定性是针对所有输入实例而 言的。即在所有可能的输入实例中，只要有一 个实例使得算法不满足稳定性要求，则该排序 算法就是不稳定的