|
排序(sort)或分类 所谓排序就是要整理文件中的记录使之按关键字递增(或递减)次序排列起来其确切定义如下 输入n个记录R R …R n 其相应的关键字分别为K K …K n 输出R il R i …R in 使得K i ≤K i ≤…≤K in (或K i ≥K i ≥…≥K in ) 被排序对象文件 被排序的对象文件由一组记录组成 记录则由若干个数据项(或域)组成其中有一项可用来标识一个记录称为关键字项该数据项的值称为关键字(Key) 注意 在不易产生混淆时将关键字项简称为关键字 排序运算的依据关键字 用来作排序运算依据的关键字可以是数字类型也可以是字符类型 关键字的选取应根据问题的要求而定 【例】在高考成绩统计中将每个考生作为一个记录每条记录包含准考证号姓名各科的分数和总分数等项内容若要惟一地标识 一个考生的记录则必须用准考证号作为关键字若要按照考生的总分数排名次则需用总分数作为关键字 排序的稳定性 当待排序记录的关键字均不相同时排序结果是惟一的否则排序结果不唯一 在待排序的文件中若存在多个关键字相同的记录经过排序后这些具有相同关键字的记录之间的相对次序保持不变该排序方 法是 稳定的 ;若具有相同关键字的记录之间的相对次序发生变化则称这种排序方法是 不稳定的 注意 排序算法的稳定性是针对所有输入实例而言的即在所有可能的输入实例中只要有一个实例使得算法不满足稳定性要求则该 排序算法就是不稳定的 排序方法的分类 按是否涉及数据的内外存交换分 在排序过程中若整个文件都是放在内存中处理排序时不涉及数据的内外存交换则称之为 内部排序 (简称内排序);反之 若排序过程中要进行数据的内外存交换则称之为 外部排序 注意 ① 内排序适用于记录个数不很多的小文件 ② 外排序则适用于记录个数太多不能一次将其全部记录放人内存的大文件 按策略划分内部排序方法 可以分为五类插入排序选择排序交换排序归并排序和分配排序 |
