排序是数据结构的一种重要运算。

本章的5.1节至5.6节介绍内排序的各种方法，5.7节介绍外排序方法。

此外，堆排序也是一种典型的选择排序，有关堆排序的算法将在第8章中介绍。

5.1基本概念

在讨论排序的概念之前，首先引入排序码的概念。

排序码是结点中的一个或多个字段，其值作为排序运算中的依据。

排序码可以是关键码，这时的排序是按关键码对文件进行排序的；

排序码也可以不是关键码，这时可能有多个结点的排序码具有相同的值，因而排序结果可能不唯一。

排序码的数据类型既可以是正数，也可以是实数或字符串，甚至是复杂的组合数据类型

排序的基本概念