什么是"排序"？简单说，排序是将无序的记录序列调整为有序记录序列的一种操作。例如，将下列记录序列
　　{ 52, 49, 80, 36, 14, 58, 61, 23, 97, 75 }

　调整为序列
　　{ 14, 23, 36, 49, 52, 58, 61, 75, 80, 97 }

　一般情况下，对排序的定义为：
　　假设含有n个记录的序列为：
　　　{ ,,…, } 　　　　　　　(10-1)

　它们的关键字相应为
　　　{ ,,…, }

　　对式（10-1）的记录序列进行排序就是要确定序号1，2，…，n的一种排列
　　　,,…,，

　　使其相应的关键字满足如下的非递减（或非递增）的关系：
　　　　　　　(10-2)

　　也就是使式(10-1)的记录序列重新排列成一个按关键字有序的序列
　　　　　(10-3)

　　当待排序记录中的关键字 (i=1,2,…,n)都不相同时，则任何一个记录的无序序列经排序后得到的结果是唯一的；反之，若待排序的序列中存在两个或两个以上关键字相等的记录，则排序所得到的结果不唯一。假设 = (1≤i≤n,1≤j≤n,i≠j)，且在排序前的序列中 领先于 (即i<j)。若在排序后的序列中 仍领先于 ，则称所用的排序方法是稳定的；反之，若可能使排序后的序列中 领先于 ，则称所用的排序方法是不稳定的。在某些有特殊要求的应用问题中需要考虑所用排序方法的稳定性的问题。

　　根据在排序过程中涉及的存储器不同，可将排序方法分为两大类：（1）内部排序：在排序进行的过程中不使用计算机外部存储器的排序过程。2）外部排序：在排序进行的过程中需要对外存进行访问的排序过程。本章仅讨论各种内部排序的方法。

　　内部排序的过程是一个逐步扩大记录的"有序序列"区域的长度的过程。大多数排序方法在排序过程中将出现如动画所示"有序"和"无序"两个区域 动画，其中有序区内的记录已按关键字非递减有序排列，而无序区内为待排记录，通常称"使有序区中记录数目增加一个或几个"的操作过程为"一趟排序"。按何种策略扩大有序区域将导致不同的排序方法。例如在无序区域中选取一个关键字最小记录加到有序区域中的排序方法称为"选择类"的排序法，除此之外还有插入类、交换类、归并类和计数类等排序方法。本章仅就各类介绍一二个典型算法。

　　待排序的记录序列可以用顺序表表示，也可以用链表表示。本章讨论的排序算法一律以如右说明的顺序表为操作对象。
  
　　从第9章的讨论可见，有序表比顺序表的查找效率高，在第2章的讨论中也曾提到，对于进行并、交和差的集合，用有序表表示时其运算的时间复杂度要比线性表低一个数量级。如何将顺序表变成有序表？排序为常用的方法。

　　从排序的本意而言，排序可以对单个关键字进行，也可以对多个关键字的组合进行，可统称排序时所依赖的准绳为"排序码"。为讨论方便起，本章约定排序只对单个关键字进行，并约定排序结果为记录按关键字"非递减"的顺序进行排列。

　
　
　
　
　

　

　const MAXSIZE = 20; // 假设的顺序表最大长度
　typedef struct {
　　RcdType r[MAXSIZE+1];
　　// r[0]闲置或作为判别标志的"哨兵"单元
　　int length; 　　　// 顺序表长度
　} SqList；　　　　　// 顺序表类型

其中记录类型定义为：
　typedef struct {
　　KeyType key; 　　　　　// 关键字项
　　InfoType otherinfo;　　 // 其它数据项　
　} RcdType; // 记录类型并设定关键字为整型
　typedef int KeyType;