概述
概述
排序
排序
：
：
将一组杂乱无章的数据按一定的规律顺
将一组杂乱无章的数据按一定的规律顺
次排列起来。
次排列起来。
数据表
数据表
(
(
datalist
datalist
)
)
:
:
它是待排序数据对象的有限
它是待排序数据对象的有限
集合。
集合。
关键码
关键码
(
(
key
key
)
)
:
:
通常数据对象有多个
通常数据对象有多个
属性域
属性域
，
，
即多个数据成员组成，其中有一个属性域可用
即多个数据成员组成，其中有一个属性域可用
来区分对象，作为排序依据。该域即为关键码。
来区分对象，作为排序依据。该域即为关键码。
每个数据表用哪个属性域作为关键码，要视具
每个数据表用哪个属性域作为关键码，要视具
体的应用需要而定。即使是同一个表，在解决
体的应用需要而定。即使是同一个表，在解决
不同问题的场合也可能取不同的域做关键码。
不同问题的场合也可能取不同的域做关键码。
主关键码
主关键码
:
:
如果在数据表中各个对象的关键码
如果在数据表中各个对象的关键码
互不相同，这种关键码即主关键码。按照主关键
互不相同，这种关键码即主关键码。按照主关键
码进行排序，排序的结果是唯一的。
码进行排序，排序的结果是唯一的。
次关键码
次关键码
:
:
数据表中有些对象的关键码可能相
数据表中有些对象的关键码可能相
同，这种关键码称为次关键码。按照次关键码进
同，这种关键码称为次关键码。按照次关键码进
行排序，排序的结果可能不唯一。
行排序，排序的结果可能不唯一。
排序算法的稳定性
排序算法的稳定性
:
:
如果在对象序列中有两个对
如果在对象序列中有两个对
象
象
r
r
[
[
i
i
]
]
和
和
r
r
[
[
j
j
]
]
，它们的关键码
，它们的关键码
k
k
[
[
i
i
]
]
== k
== k
[
[
j
j
]
]
，且在排
，且在排
序之前，对象
序之前，对象
r
r
[
[
i
i
]
]
排在
排在
r
r
[
[
j
j
]
]
前面。如果在排序之后，
前面。如果在排序之后，
对象
对象
r
r
[
[
i
i
]
]
仍在对象
仍在对象
r
r
[
[
j
j
]
]
的前面，则称这个排序方法
的前面，则称这个排序方法
是稳定的，否则称这个排序方法是不稳定的。
是稳定的，否则称这个排序方法是不稳定的。
内排序与外排序
内排序与外排序
:
:
内排序是指在排序期间数据
内排序是指在排序期间数据
对象全部存放在内存的排序；外排序是指在排
对象全部存放在内存的排序；外排序是指在排
序期间全部对象个数太多，不能同时存放在内
序期间全部对象个数太多，不能同时存放在内
存，必须根据排序过程的要求，不断在内、外
存，必须根据排序过程的要求，不断在内、外
存之间移动的排序。
存之间移动的排序。
排序的时间开销
排序的时间开销
:
:
排序的时间开销是衡量算法
排序的时间开销是衡量算法
好坏的最重要的标志。
好坏的最重要的标志。
排序的时间开销可用算
排序的时间开销可用算
法执行中的
法执行中的
数据比较次数
数据比较次数
与
与
数据移动次数
数据移动次数
来衡
来衡
量
量
。各节给出算法运行时间代价的大略估算一
。各节给出算法运行时间代价的大略估算一
般都
般都
按平均情况
按平均情况
进行估算。对于那些
进行估算。对于那些
受对象关
受对象关
键码序列初始排列及对象个数影响较大的
键码序列初始排列及对象个数影响较大的
，
，
需
需
要
要
按最好情况
按最好情况
和
和
最坏情况
最坏情况
进行估算
进行估算
。
。
静态排序
静态排序
:
:
排序的过程是对数据对象本身进
排序的过程是对数据对象本身进
行物理地重排，经过比较和判断，将对象移
行物理地重排，经过比较和判断，将对象移
到合适的位置。这时，数据对象一般都存放
到合适的位置。这时，数据对象一般都存放
在一个顺序的表中。
在一个顺序的表中。
动态排序
动态排序
:
:
给每个对象增加一个链接指针，
给每个对象增加一个链接指针，
在排序的过程中不移动对象或传送数据，仅
在排序的过程中不移动对象或传送数据，仅
通过修改链接指针来改变对象之间的逻辑顺
通过修改链接指针来改变对象之间的逻辑顺
序，从而达到排序的目的。
序，从而达到排序的目的。
算法执行时所需的附加存储
算法执行时所需的附加存储
:
:
评价算法好坏
评价算法好坏
的另一标准。
的另一标准。
静态排序过程中所用到的数据表类定义，体
静态排序过程中所用到的数据表类定义，体
现了抽象数据类型的思想。
现了抽象数据类型的思想。
