扫码获取更多资源

●排序的基本概念

排序

给定一组记录序列｛r】，r2,…，rQ，其相应的关键字序列为k2,…，虹｝,将这组记 录排列成顺序为曲，5 …，匸3的一个序列，使得相应的关键字满足kqx・・・Wksn (升序)或者ksi〉ks2 2・・・2ksn(降序)，此过程称为排序(Sorting) o简言之，排序就是将一个 记录的任意序列重新排列成一个按关键字有序的序列。

趟

在排序过程中，将待排序的记录序列扫描一遍称为一趟(Pass)。在排序操作中，深刻理 解趟的含义能够更好地掌握排序方法的思想和过程。

排序方法的稳定性

假定在待排序的记录序列中，存在多个具有相同关键字的记录，如果经过排序，这些记 录的相对次序保持不变，即在原序列中蛆=虹，且ri在与之前，而在排序后的序列中r;仍在 与之前测这种排序方法是稳定的(Stable);否则是不稳定的(Unstable) o

对于不稳定的排序方法，只要举出一个实例，即可说明其不稳定性；而对于稳定的排序 方法，必须对其进行分析从而得到稳定的特性。

需要注意的是,排序方法是否稳定是由具体算法决定的，不稳定算法在某种条件下可以 变为稳定算法，而稳定算法在某种条件下也可以变为不稳定算法。

排序方法的分类

由于待排序记录数量不同，使得排序过程中涉及的存储器不同。如果按排序过程中待

(1) 按排序是否建立在关键字比较的基础上来区分，可以将排序方法分为基于比较的 排序和不基于比较的排序。基于比较的排序主要通过关键字之间的比较和记录的移动这两 种操作来实现；而不基于比较的排序是根据待排序数据的特点依据多关键字排序的思路对 单逻辑关键字进行排序，通常没有大量的关键字之间的比较和记录的移动操作。

(2) 按排序过程中依据的不同原则来区分，可以将排序方法大致分为插入排序、交换排 序、选择排序、归并排序和基数排序。

(3) 按排序过程中所需要的工作量来区分，可以将排序方法分为简单排序法，其时间复 杂度为0(/)；先进排序法，其时间复杂度为O(nlogm)；基数排序法，其时间复杂度为 O(dXn)(d为单逻辑关键字中关键字的个数)。

排序的基本操作

通常，在排序过程中需要进行两种基本操作：

(1) 比较：即比较两个记录关键字大小。该操作对大多数排序方法来说都是必要的。

(2) 移动：将记录从一个位置移动至另一个位置。该操作可以通过改变记录的存储方 式来予以避免。

待排序记录序列的存储方式

通常，待排序记录序列有3种存储方式。

(1) 以顺序表存储待排序记录序列。待排序记录存储在一组地址连续的存储单元中， 类似于线性表的顺序存储结构，在序列中相邻的两个记录，其存储位置也相邻。在这种存储 方式中，记录之间的次序关系由其存储位置决定，实现排序必须移动记录。

(2) 以静态链表存储待排序记录序列。待排序记录存储在一个静态链表中，在这种存 储方式中，记录之间的次序关系由指针指示，实现排序不需要移动记录，仅需要修改指针即 可。该存储方式下的排序又称为链表排序。

(3) 以顺序表存储待排序记录序列，并另设一个指示各个记录存储位置的地址向量。 在这种存储方式中，实现排序不需要移动记录本身，而移动地址向量中这些记录的“地址”, 在排序之后再按照地址向量中的值调整记录的存储位置。该存储方式下的排序又称为地址 排序。

排序的性能分析

排序的性能分析主要从两个方面考虑：一个是时间复杂度，另一个是空间复杂度。

时间复杂度

排序的执行时间随待排序记录的数量变化而变化的度量，称为排序的时间复杂度。大 多数排序方法的时间开销主要是关键字之间的比较和记录的移动，因此高效率的排序方法 应该具有尽可能少的关键字比较次数和尽可能少的记录移动次数。

联系我们：