1. 什么是排序？

   排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。

   例如：将下列关键字序列

   52, 49, 80, 36, 14, 58, 61, 23, 97, 75

   调整为

   14, 23, 36, 49, 52, 58, 61 ,75, 80, 97

   一般情况下，

   假设含n个记录的序列为

   { R₁, R₂, …， R_n }

   其相应的关键字序列为

   { K₁, K₂, …，K_n }

   这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系

   Kp₁≤Kp₂≤…≤Kp_n

   按此固有关系将式(1)的记录序列重新排列为

   { Rp₁, Rp₂, …，Rp_n }

   的操作称作排序。

2. 内部排序和外部排序

   若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；

   反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。

   在本章内先讨论内部排序的各种方法，然后介绍外部排序的基本过程。

3. 内部排序的方法

内部排序的过程是一个逐步扩大记录的有序序列长度的过程。在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。

使有序区中记录的数目增加一个或几个的操作称为一趟排序。

逐步扩大记录有序序列长度的方法大致有下列几类：

1. 插入类

   将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度；

2. 交换类

   通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度;

3. 选择类

   从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度;

4. 归并类

   通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度;

5. 其它方法