设被排序的数据是由一组元素组成的表，每个元素由若干个数据项组成，在排序的过程中用关键字标识元素。

1.排序的定义

排序是计算机程序设计中的重要操作，它将一组数据元素的任意序列，排列成按关键字有序的序列。其确切定义如下：

设n个数据元素的序列为{R1，R2，…，Rn}，其关键字序列为{k1，k2，…，kn}，排序就是确定下标1，2，3，…，n的一种排列p1，p2，p3，…，pn，使表中元素相应的关键字满足非递减（或非递增）的关系使{R1，R2，…，Rn}成为一个按关键字有序的序列这种操作被称为排序。

当数据元素Ri（1≤i≤n）的关键字ki为主关键字时，排序的结果是唯一的；当数据元素Ri（1≤i≤n）的关键字ki为次关键字时，排序结果可能不唯一。如果在待排序的表中存在多个关键字相同的数据元素，排序后这些具有相同关键字的元素之间的相对次序保持不变，则称这种排序方法是稳定的。若具有相同关键字的数据元素之间的相对次序发生变化，则称这种排序方法是不稳定的。(www.daowen.com)

2.排序的分类

由于待排序数据元素的数量不同，使排序的过程涉及不同的存储器，可将排序分为内部排序和外部排序两大类。内部排序是待排序数据元素全部存储在计算机内存中进行的排序过程；外部排序是待排序数据元素的数量较大，以致内存不能一次容纳全部数据元素，需要借助外存才能完成排序的过程。内部排序是外部排序的基础，本章讨论内部排序方法。

3.数据组织

为简单起见，本章假设关键字类型为整型，采用顺序表存储结构。数据元素和顺序表的类定义如下：