第10章_内排序.pdf

李云清杨庆红揭安全

第第1010章章内排序内排序
排序是数据处理过程中经常使用的一种重要的运
算,排序的方法有很多种,本章主要讨论内排序的各
种算法,并对每个排序算法的时间和空间复杂性以及
算法的稳定性等进行了讨论。
1010..11 排排序序的基的基本概念本概念
假设一个文件是由n个记录R1,R2,…,Rn组成,
所谓排序就是以记录中某个(或几个)字段值不减(或
不增)的次序将这n个记录重新排列,称该字段为排
序码。能唯一标识一个记录的字段称为关键码,关
键码可以作为排序码,但排序码不一定要是关键码。

按排序过程中使用到的存储介质来分,可以将排
序分成两大类:内排序和外排序。
内排序是指在排序过程中所有数据均放在内存中
处理,不需要使用外存的排序方法。而对于数据量很
大的文件,在内存不足的情况下,则还需要使用外存,
这种排序方法称为外排序。
排序码相同的记录,若经过排序后,这些记录
仍保持原来的相对次序不变,称这个排序算法是稳
定的。否则,称为不稳定的排序算法。

评价排序算法优劣的标准:
首先考虑算法执行所需的时间,这主要是用执行
过程中的比较次数和移动次数来度量;
其次考虑算法执行所需要的附加空间。
当然,保证算法的正确性是不言而喻的,可读性等
也是要考虑的因素。

排序算法如未作特别的说明,使用的有关定义如下:
/*常见排序算法的头文件,*/
#define MAXSIZE 100 /*文件中记录个数的最大值*/
typedef int keytype; /*定义排序码类型为整数类型*/
typedef struct{
为了方便, 一般不用
keytype key; r[0]
于存放排序码,在一些排序
/*此处还可以定义记录中除排序码算法中它可以外的其它域用*/来作为中间
}recordtype; /*记录类型单元的定存放临时义*/ 数据。length
typedef struct{ 域是待排序的记录个数,它
必须不大于MAXSIZE,这样,
recordtype r[MAXSIZE+1];
第1~length个记录的排序码
int length; /*待排序文件中记录的个数分别存于*/
}table; /*待排序文件r[1]*y/~ r[length].key中

1010..22 插入插入排序排序
插入排序的基本方法是:
将待排序文件中的记录, 逐个地按其排序码值的
大小插入到目前已经排好序的若干个记录组成的文件中
的适当位置,并保持新文件有序。
直接插直接插入入排序排序
直接插入排序算法的思路是:初始可认为文件中的
第1个记录己排好序,然后将第2个到第n个记录依次插
入已排序的记录组成的文件中。在对第i个记录Ri进行
插入时,R1,R2,…,Ri-1已排序,将记录Ri的排序码
keyi与已经排好序的排序码从右向左依次比较,找到Ri
应插入的位置,将该位置以后直到Ri-1各记录顺序后移,
空出该位置让Ri插入。

一组记录的排序码分别为:
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
算法设计的时候如处理?
方法方法之之一一::设设置置