麥据结构 李云清杨庆红揭安全
第10章内排序 排序是数据处理过程中经常使用的一种重要的运 算,排序的方法有很多种,本章主要讨论内排序的各 种算法,并对每个排序算法的时间和空间复杂性以及 算法的稳定性等进行了讨论 10.1排序的基本概念 假设一个文件是由n个记录R1,R2,…,Rn组成 所谓排序就是以记录中某个(或几个)字段值不减(或 不增)的次序将这n个记录重新排列,称该字段为排 序码。能唯一标识一个记录的字段称为关键码,关 键码可以作为排序码,但排序码不一定要是关键码
按排序过程中使用到的存储介质来分,可以将排 序分成两大类:内排序和外排序。 内排序是指在排序过程中所有数据均放在内存中 处理,不需要使用外存的排序方法。而对于数据量很 大的文件,在内存不足的情况下,则还需要使用外存, 这种排序方法称为外排序。 排序码相同的记录,若经过排序后,这些记录 仍保持原来的相对次序不变,称这个排序算法是稳 定的。否则,称为不稳定的排序算法
评价排序算法优劣的标准: 首先考虑算法执行所需的时间,这主要是用执行 过程中的比较次数和移动次数来度量 其次考虑算法执行所需要的附加空间 当然,保证算法的正确性是不言而喻的,可读性等 也是要考虑的因素
排序算法如未作特别的说明,使用的有关定义如下: /常见排序算法的头文件,文件名 table.h*/ # define maXsize100/文件中记录个数的最大值 typedef int keytype;/*定义排序码类型为整数类型* typedef struct[ keytype key 为了方便,ro]一般不用 于存放排序码,在一些排序 此处还可以定义记录中除算法中它可以用来作为中间 frecordty pe 记录单元存放临时数据。 length typedef struct[ 域是待排序的记录个数,它 必须不大于 MAXSIZE,这样, recordtype「[MAⅩS|ZE+1 第1~| ength个记录的排序码 int length; 待侍排分别存于 Jtable 待排序r1key- r[length]. key中
为了方便，r[0]一般不用 于存放排序码，在一些排序 算法中它可以用来作为中间 单元存放临时数据。length 域是待排序的记录个数，它 必须不大于MAXSIZE，这样， 第1~length个记录的排序码 分别存于 r[1].key~r[length].key中