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