8.1　基本概念

排序是我们生活中经常会面对的问题，是计算机程序设计中的一种重要操作。在排序中结点（数据元素）称为“记录”，记录的集合称为“文件”，内存中的文件也常称为“线性表”。下面介绍关于排序的相关概念。

1.排序

排序的定义如下：假设含n个记录的序列为｛R1，R2，…，Rn｝，其相应的关键字序列为｛K1，K2，…，Kn｝，需确定1，2，…，n的一种排列P1，P2，…，Pn，使其相应的关键字满足如下的非递减（或非递增）关系Kp1≤Kp2≤…≤Kpn（或Ki1≥Ki2≥…≥Kin），序列成为一个按关键字有序的序列｛Rp1，Rp2，…，Rpn｝，这样一种操作称为排序。

上述排序定义中的关键字Ki可以是记录Ri（i＝1，2，…，n）的主关键字，也可以是记录Ri的次关键字，甚至是若干数据项的组合。若Ki是主关键字，则任何一个记录的无序序列经排序后得到的结果是唯一的；若Ki是次关键字，则排序的结果不唯一，因为待排序的记录序列中可能存在两个或两个以上关键字相等的记录。

文件是被排序的对象，它由一组记录组成。记录则由若干个数据项（或域）组成。其中有一项可用来标识一个记录，称为关键字项。该数据项的值称为关键字（key）。

关键字是数据元素中的某个数据项。如果某个数据项可以唯一地确定一个数据元素，就将其称为主关键字；否则，称为次关键字。用来作排序运算依据的关键字可以是数字类型，也可以是字符类型。关键字的选取应根据问题的要求而定。

2.稳定排序与不稳定排序

假设Ki＝Kj（1≤i≤n，1≤j≤n，i＜＞j），且在排序前的序列中Ri领先于Rj（即i＜j）。若在排序后的序列中Ri仍领先于Rj，则称所用的排序方法是稳定的；反之，若可能使排序后的序列中Rj仍领先于Ri，则称所用的排序方法是不稳定的。即若待排序文件中有关键字相等的记录，排序后，其前后相对次序与排序前未发生变化，这种排序称为“稳定”排序，否则是“不稳定”排序。

所谓稳定排序，就是相等的两个数排序前是什么顺序，排序后也是什么顺序。比如a＝1，b＝3，c＝1，a、b、c这3个数进行排序，a本来在c前面，如果能保证排序后，a还是在c前面，就是稳定排序，否则就是不稳定排序。

再如，序列3，15，8［1］，8［2］，6，9，若排序后得3，6，8［1］，8［2］，9，15，则为稳定的排序；若排序后得3，6，8［2］，8［1］，9，15，则为不稳定的排序。

稳定排序有：冒泡排序、插入排序、归并排序、基数排序。

不稳定排序有：选择排序、快速排序、希尔排序、堆排序。

稳定排序与不稳定排序表示所用的排序方法，并不说明哪种方法好与差。

3.内部排序和外部排序

待排序的记录数量不同，使得排序过程中涉及的存储器不同，根据在排序过程中待排序的所有数据元素是否全部被放置在内存中，可将排序方法分为内部排序和外部排序两大类。

内部排序是指在排序的整个过程中，待排序的所有数据元素全部被放置在内存中；外部排序是指由于待排序的数据元素个数太多，不能同时放置在内存，而需要将一部分数据元素放置在内存，另一部分数据元素放置在外设上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。

本章只讨论常用的内部排序方法。

4.内部排序的方法

内部排序的方法很多，但就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合在不同的环境（如记录的初始排列状态等）下使用。如果按排序过程中依据的不同原则对内部排序方法进行分类，则大致可分为插入排序、交换排序、选择排序、归并排序和基数排序五类；如果按内部排序过程中所需的工作量来区分，则可分为三类：①简单的排序方法，其时间复杂度为O（n2），时间效率低；②先进的排序方法，其时间复杂度为O（nlog2n），时间效率高；③基数排序，其时间复杂度为O（d×n），时间效率高。

本章仅就每一类介绍一两个典型算法，在学习本章内容时除了掌握算法本身以外，更重要的是了解该算法在进行排序时所依据的原则，以利于学习和创造更加新的算法。

5.排序算法分析

（1）排序算法的基本操作

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

①比较两个关键字的大小；

②改变指向记录的指针或移动记录本身。

前一个操作对大多数排序方法来说都是必要的，而后一个操作的实现依赖于待排序记录的存储方式，可以通过改变记录的存储方式来予以避免。

（2）待排序记录的常用存储方式

①以顺序表（或直接用向量）作为存储结构。

待排序的一组记录存放在地址连续的一组存储单元上，类似于线性表的顺序存储结构，在序列中相邻的两个记录Ri和Rj＋1（j＝1，2，…，n－1），它们的存储位置也相邻。

排序过程：对记录本身进行物理重排（即通过关键字之间的比较判定，将记录移到合适的位置），即直接移动记录。

②以链表作为存储结构。

一组待排序记录存放在静态链表中，记录之间的次序关系由指针指示，则实现排序不需要移动记录，仅需修改指针即可。

排序过程：无须移动记录，仅需修改指针。通常将这类排序称为链表（或链式）排序。

③用顺序的方式存储待排序的记录，但同时建立一个辅助表（如包括关键字和指向记录位置的指针组成的索引表）。

待排序的记录本身存储在地址连续的存储单元内，同时另设一个指示各个记录存储位置的地址向量，在排序过程中不移动记录本身，而移动地址向量中这些记录的“地址”，在排序结束后再按照地址向量中的值调整记录的存储位置。

排序过程：只需对辅助表的表目进行物理重排（即只移动辅助表的表目，而不移动记录本身）。适用于难以在链表上实现，仍需避免排序过程中移动记录的排序方法。

在第二种存储方式下实现的排序又称（链）表排序，在第三种存储方式下实现的排序又称地址排序。

6.排序算法的效率

评价排序算法的效率主要有两点：一是在数据量规模一定的条件下，算法执行所消耗的平均时间，对于排序操作，时间主要消耗在关键字之间的比较和数据元素的移动上，因此我们可以认为高效率的排序算法应该是尽可能少的比较次数和尽可能少的数据元素移动次数；二是执行算法所需要的辅助存储空间，辅助存储空间是指在数据量规模一定的条件下，除了存放待排序数据元素占用的存储空间之外，执行算法所需要的其他存储空间，理想的空间效率是算法执行期间所需要的辅助空间与待排序的数据量无关。

在本章的讨论中，设待排序的一组记录以上述第一种方式存储，且为了讨论方便，设记录的关键字均为整数。即在以后讨论的大部分算法中，待排记录的数据类型设为：

注意：若关键字类型没有比较算符，则可事先定义宏或函数来表示比较运算。