9.1 排序的基本概念

南山隐士 2022年07月31日 41 0

排序是计算机程序设计中一种非常重要的操作。要求能准确叙述记录序列按关键字排序的确切定义,结合实例理解稳定排序、不稳定排序,内部排序、外部排序等相关概念。

1.相关定义

(1)排序:对一组数据按由小到大的次序(升序)或由大到的小次序(降序)进行排列(不作特殊说明,本章均指升序排序)。

(2)记录序列按某个数据项(关键字)的大小排序。

n个记录的序列 { R1,R2,…,Rn },记录中某关键字序列{ K1,K2,…,Kn }。对该关键字序列进行排序,使其成为非减(升序)关系或非增(降序)关系{ Kp1,Kp2,…,Kpn },而相应的记录序列成为{ Rp1,Rp2,…,Rpn }。

若选定用于排序的关键字为主关键字,则排序结果唯一。

若选定用于排序的关键字为次关键字,则排序结果不唯一。

如表9-3所示的记录序列,左表中记录序列是按照学号由大到小排列的,如果按照平均成绩由低到高对上述记录序列排序,结果则为下表。

表9-3 记录排序


(3)稳定的排序算法和不稳定的排序算法

若关键字Ki=Kj,排序前相应的记录Ri排在Rj之前,对关键字k排序后Ri仍排在Rj之前,称该排序算法为稳定的排序算法。反之,若排序后Rj可能领先于Ri,称该排序算法为不稳定的排序算法。

(4)内部排序与外部排序

排序中,存放待排序数据的存储器不同,所采用的排序方法也不同。因此,排序方法分为两大类。若排序的数据量不大,在计算机内存可以容纳的情况下,排序过程完全在内存中进行,这样的排序称为内部排序。当排序数据量很大,需要借助于外存完成排序过程,这样的排序称为外部排序。

2.待排序记录序列的存储

用结构变量存放待排序的记录,以结构数组存放待排序的记录序列。为简便起见,设记录中只含一个关键字,且为整数。结构体变量的类型定义如下:

typedef struct

{

int key; /存放关键字的成员项/

…… /其他成员项/

} NODE;

NODE a[MAX]; /说明了一个长度为MAX 的结构数组/

Last Updated: 2022/07/31 23:25:24
9.2 插入排序 8小结