麥据结构 李云清杨庆红揭安全
第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中
102插入排序 插入排序的基本方法是 将待排序文件中的记录,逐个地按其排序码值的 大小插入到目前已经排好序的若干个记录组成的文件中 的适当位置,并保持新文件有序。 10.21直接插入排序 直接插入排序算法的思路是:初始可认为文件中的 第1个记录己排好序,然后将第2个到第n个记录依次插 入已排序的记录组成的文件中。在对第个记录R进 插入时,R1,R2,…,R1已排序,将记录R的排序码 key;与已经排好序的排序码从右向左依次比较,找到R 应插入的位置,将该位置以后直到R1各记录顺序后移, 空出该位置让R插入
组记录的排序码分别为: 312,126,272,226,28,165,123 初始时将第1个排序码作为已经排好序的,把排好序 的数据记录放入中括号中,表示有序的文件,剩下 的在中括号外,如下所示 [312],126,272,226,28,165,123 设前3个记录的排序码已重新排列有序,构成一个含 有3个记录的有序文件: [126,272,312],226,28,165,123 现在要将第4个排序码226插入!
[126,272,312],226,28,165,123 现在要将第4个排序码226插入! 将待插入的排序码226和已经有序的最后一个排 序码312比较,因为待插入的排序码226小于312,所 以226肯定要置于312的前面,至于是否就是置于312 的前一个位置,此时还不能确定,需要继续向左比较 将所有大于待插入排序码226的那两个排序码 312和272依次后移一个位置,在空出的位置插入待 排序的排序码226,得一含有4个记录的有序文件: [126,226,272,312],28,165,123
需要注意的是,当待插入排序码小于所有已排序的 排序码时,如在插入第5个值28时 [126,226,272,312],28,165,123 算法设计的时候如处理? 方法之一:设置“哨
void insertsort(table*tab) for(i=2;i length;+)依次插入从第2个开始的所有元素 tab->[0]key=tab->r[].key;/设置哨兵,准备找插入位置 while(tab->ro]key]key)找插入位置并后移*/ tab->r+1]key=tab->]key;/后移* 1; 继续向前(左)查找 tab->+1key=tab->r0]key;/插入第个元素的副本,即前面设置的哨兵* 算法10.1直接插入排序算法